排序算法可以称得上是我的盲点, 曾几何时当我知道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; }
选择排序