从算法逻辑上看, 选择排序是一种简单且直观的排序算法. 它也是两层循环. 内层循环就像工人一样, 它是真正做事情的, 内层循环每执行一遍, 将选出本次待排序的元素中最小(或最大)的一个, 存放在数组的起始位置. 而 外层循环则像老板一样, 它告诉内层循环你需要不停的工作, 直到工作完成(也就是全部的元素排序完成).
Tips: 选择排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 比如数组[2,2,1,3], 正向排序时, 第一个数字2将与数字1交换, 那么两个数字2之间的顺序将和原来的顺序不一致, 虽然它们的值相同, 但它们相对的顺序却发生了变化. 我们将这种现象称作 不稳定性 .
如下是动图效果:
如下是上图的算法实现:
function selectSort(array) { var length = array.length, min; for (var i = 0; i < length - 1; i++) { min = i; for (var j = i + 1; j < length; j++) { array[j] < array[min] && (min = j); //记住最小数的下标 } min!=i && swap(i,min,array); } return array; }
以下是其算法复杂度:
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(n²)
O(n²)
O(n²)
O(1)
选择排序的简单和直观名副其实, 这也造就了它”出了名的慢性子”, 无论是哪种情况, 哪怕原数组已排序完成, 它也将花费将近n²/2次遍历来确认一遍. 即便是这样, 它的排序结果也还是不稳定的. 唯一值得高兴的是, 它并不耗费额外的内存空间.
插入排序插入排序的设计初衷是往有序的数组中快速插入一个新的元素. 它的算法思想是: 把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.
插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序 , 希尔排序 .
直接插入排序它的基本思想是: 将待排序的元素按照大小顺序, 依次插入到一个已经排好序的数组之中, 直到所有的元素都插入进去.
如下是动图效果:
如下是上图的算法实现:
function directInsertionSort(array) { var length = array.length, index, current; for (var i = 1; i < length; i++) { index = i - 1; //待比较元素的下标 current = array[i]; //当前元素 while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大 array[index+1] = array[index]; //将待比较元素后移一位 index--; //游标前移一位 //console.log(array); } if(index+1 != i){ //避免同一个元素赋值给自身 array[index+1] = current; //将当前元素插入预留空位 //console.log(array); } } return array; }
为了更好的观察到直接插入排序的实现过程, 我们不妨将上述代码中的注释部分加入. 以数组 [5,4,3,2,1] 为例, 如下便是原数组的演化过程.
可见, 数组的各个元素, 从后往前, 只要比前面的元素小, 都依次插入到了合理的位置.
Tips: 由于直接插入排序每次只移动一个元素的位置, 并不会改变值相同的元素之间的排序, 因此它是一种稳定排序.
折半插入排序折半插入排序是直接插入排序的升级版. 鉴于插入排序第一部分为已排好序的数组, 我们不必按顺序依次寻找插入点, 只需比较它们的中间值与待插入元素的大小即可.
Tips: 同直接插入排序类似, 折半插入排序每次交换的是相邻的且值为不同的元素, 它并不会改变值相同的元素之间的顺序. 因此它是稳定的.
算法基本思想是:
取0 ~ i-1的中间点( m = (i-1)>>1 ), array[i] 与 array[m] 进行比较, 若array[i] < array[m] , 则说明待插入的元素array[i] 应该处于数组的 0 ~ m 索引之间; 反之, 则说明它应该处于数组的 m ~ i-1 索引之间.
重复步骤1, 每次缩小一半的查找范围, 直至找到插入的位置.
将数组中插入位置之后的元素全部后移一位.
在指定位置插入第 i 个元素.
注: x>>1 是位运算中的右移运算, 表示右移一位, 等同于x除以2再取整, 即 x>>1 == Math.floor(x/2) .
如下是算法实现: