导读
排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道冒泡啊?!), 要知道学习一门技术最好的时间是三年前, 但愿我现在补习还来得及(捂脸).
因此本篇重拾了出镜概率比较高的十来种排序算法, 逐一分析其排序思想, 并批注注意事项. 欢迎对算法提出改进和讨论.
冒泡排序
冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.
Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.
由于有两层循环, 因此可以有四种实现方式.
| 方案 | 外层循环 | 内层循环 |
|---|---|---|
| 1 | 正序 | 正序 |
| 2 | 正序 | 逆序 |
| 3 | 逆序 | 正序 |
| 4 | 逆序 | 逆序 |
四种不同循环方向, 实现方式略有差异.
如下是动图效果(对应于方案1: 内/外层循环均是正序遍历.
如下是上图的算法实现(对应方案一: 内/外层循环均是正序遍历).
//先将交换元素部分抽象出来
function swap(i,j,array){
var temp = array[j];
array[j] = array[i];
array[i] = temp;
}
function bubbleSort(array) {
var length = array.length, isSwap;
for (var i = 0; i < length; i++) { //正序
isSwap = false;
for (var j = 0; j < length - 1 - i; j++) { //正序
array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
}
if(!isSwap)
break;
}
return array;
}
以上, 排序的特点就是: 靠后的元素位置先确定.
方案二: 外循环正序遍历, 内循环逆序遍历, 代码如下:
function bubbleSort(array) {
var length = array.length, isSwap;
for (var i = 0; i < length; i++) { //正序
isSwap = false;
for (var j = length - 1; j >= i+1; j--) { //逆序
array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
}
if(!isSwap)
break;
}
return array;
}
以上, 靠前的元素位置先确定.
方案三: 外循环逆序遍历, 内循环正序遍历, 代码如下:
function bubbleSort(array) {
var length = array.length, isSwap;
for (var i = length - 1; i >= 0; i--) { //逆序
isSwap = false;
for (var j = 0; j < i; j++) { //正序
array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
}
if(!isSwap)
break;
}
return array;
}
以上, 由于内循环是正序遍历, 因此靠后的元素位置先确定.
方案四: 外循环逆序遍历, 内循环逆序遍历, 代码如下:
function bubbleSort(array) {
var length = array.length, isSwap;
for (var i = length - 1; i >= 0; i--) { //逆序
isSwap = false;
for (var j = length - 1; j >= length - 1 - i; j--) { //逆序
array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
}
if(!isSwap)
break;
}
return array;
}
以上, 由于内循环是逆序遍历, 因此靠前的元素位置先确定.
以下是其算法复杂度:
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n) | O(n²) | O(1) |
冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).
双向冒泡排序
双向冒泡排序是冒泡排序的一个简易升级版, 又称鸡尾酒排序. 冒泡排序是从低到高(或者从高到低)单向排序, 双向冒泡排序顾名思义就是从两个方向分别排序(通常, 先从低到高, 然后从高到低). 因此它比冒泡排序性能稍好一些.
如下是算法实现:
function bothwayBubbleSort(array){
var tail = array.length-1, i, isSwap = false;
for(i = 0; i < tail; tail--){
for(var j = tail; j > i; j--){ //第一轮, 先将最小的数据冒泡到前面
array[j-1] > array[j] && (isSwap = true) && swap(j,j-1,array);
}
i++;
for(j = i; j < tail; j++){ //第二轮, 将最大的数据冒泡到后面
array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
}
}
return array;
}
选择排序
从算法逻辑上看, 选择排序是一种简单且直观的排序算法. 它也是两层循环. 内层循环就像工人一样, 它是真正做事情的, 内层循环每执行一遍, 将选出本次待排序的元素中最小(或最大)的一个, 存放在数组的起始位置. 而 外层循环则像老板一样, 它告诉内层循环你需要不停的工作, 直到工作完成(也就是全部的元素排序完成).
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) .
如下是算法实现:
function binaryInsertionSort(array){
var current, i, j, low, high, m;
for(i = 1; i < array.length; i++){
low = 0;
high = i - 1;
current = array[i];
while(low <= high){ //步骤1&2:折半查找
m = (low + high)>>1;
if(array[i] >= array[m]){//值相同时, 切换到高半区，保证稳定性
low = m + 1; //插入点在高半区
}else{
high = m - 1; //插入点在低半区
}
}
for(j = i; j > low; j--){ //步骤3:插入位置之后的元素全部后移一位
array[j] = array[j-1];
}
array[low] = current; //步骤4:插入该元素
}
return array;
}
为了便于对比, 同样以数组 [5,4,3,2,1] 举例
