javascript中可能用得到的全部的排序算法
导读
排序算法可以称得上是我的盲点,曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时,我的内心是奔溃的(啥是快排,我只知道冒泡啊?!),要知道学习一门技术最好的时间是三年前,但愿我现在补习还来得及(捂脸).
因此本篇重拾了出镜概率比较高的十来种排序算法,逐一分析其排序思想,并批注注意事项.欢迎对算法提出改进和讨论.
冒泡排序
冒泡排序需要两个嵌套的循环.其中,外层循环移动游标;内层循环遍历游标及之后(或之前)的元素,通过两两交换的方式,每次只确保该内循环结束位置排序正确,然后内层循环周期结束,交由外层循环往后(或前)移动游标,随即开始下一轮内层循环,以此类推,直至循环结束.
Tips:由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置,它并不改变相同元素之间的相对顺序,因此它是稳定的排序算法.
由于有两层循环,因此可以有四种实现方式.
| 方案 | 外层循环 | 内层循环 |
|---|---|---|
| 1 | 正序 | 正序 |
| 2 | 正序 | 逆序 |
| 3 | 逆序 | 正序 |
| 4 | 逆序 | 逆序 |
四种不同循环方向,实现方式略有差异.
如下是动图效果(对应于方案1:内/外层循环均是正序遍历.
如下是上图的算法实现(对应方案一:内/外层循环均是正序遍历).
//先将交换元素部分抽象出来
functionswap(i,j,array){
vartemp=array[j];
array[j]=array[i];
array[i]=temp;
}
functionbubbleSort(array){
varlength=array.length,isSwap;
for(vari=0;iarray[j+1]&&(isSwap=true)&&swap(j,j+1,array);
}
if(!isSwap)
break;
}
returnarray;
}
以上,排序的特点就是:靠后的元素位置先确定.
方案二:外循环正序遍历,内循环逆序遍历,代码如下:
functionbubbleSort(array){
varlength=array.length,isSwap;
for(vari=0;i=i+1;j--){//逆序
array[j]
以上,靠前的元素位置先确定.
方案三:外循环逆序遍历,内循环正序遍历,代码如下:
functionbubbleSort(array){
varlength=array.length,isSwap;
for(vari=length-1;i>=0;i--){//逆序
isSwap=false;
for(varj=0;jarray[j+1]&&(isSwap=true)&&swap(j,j+1,array);
}
if(!isSwap)
break;
}
returnarray;
}
以上,由于内循环是正序遍历,因此靠后的元素位置先确定.
方案四:外循环逆序遍历,内循环逆序遍历,代码如下:
functionbubbleSort(array){
varlength=array.length,isSwap;
for(vari=length-1;i>=0;i--){//逆序
isSwap=false;
for(varj=length-1;j>=length-1-i;j--){//逆序
array[j]
以上,由于内循环是逆序遍历,因此靠前的元素位置先确定.
以下是其算法复杂度:
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(n²)
O(n)
O(n²)
O(1)
冒泡排序是最容易实现的排序,最坏的情况是每次都需要交换,共需遍历并交换将近n²/2次,时间复杂度为O(n²).最佳的情况是内循环遍历一次后发现排序是对的,因此退出循环,时间复杂度为O(n).平均来讲,时间复杂度为O(n²).由于冒泡排序中只有缓存的temp变量需要内存空间,因此空间复杂度为常量O(1).
双向冒泡排序
双向冒泡排序是冒泡排序的一个简易升级版,又称鸡尾酒排序.冒泡排序是从低到高(或者从高到低)单向排序,双向冒泡排序顾名思义就是从两个方向分别排序(通常,先从低到高,然后从高到低).因此它比冒泡排序性能稍好一些.
如下是算法实现:
functionbothwayBubbleSort(array){
vartail=array.length-1,i,isSwap=false;
for(i=0;ii;j--){//第一轮,先将最小的数据冒泡到前面
array[j-1]>array[j]&&(isSwap=true)&&swap(j,j-1,array);
}
i++;
for(j=i;jarray[j+1]&&(isSwap=true)&&swap(j,j+1,array);
}
}
returnarray;
}
选择排序
从算法逻辑上看,选择排序是一种简单且直观的排序算法.它也是两层循环.内层循环就像工人一样,它是真正做事情的,内层循环每执行一遍,将选出本次待排序的元素中最小(或最大)的一个,存放在数组的起始位置.而外层循环则像老板一样,它告诉内层循环你需要不停的工作,直到工作完成(也就是全部的元素排序完成).
Tips:选择排序每次交换的元素都有可能不是相邻的,因此它有可能打破原来值为相同的元素之间的顺序.比如数组[2,2,1,3],正向排序时,第一个数字2将与数字1交换,那么两个数字2之间的顺序将和原来的顺序不一致,虽然它们的值相同,但它们相对的顺序却发生了变化.我们将这种现象称作不稳定性.
如下是动图效果:
如下是上图的算法实现:
functionselectSort(array){
varlength=array.length,min;
for(vari=0;i
以下是其算法复杂度:
平均时间复杂度
最好情况
最坏情况
空间复杂度
O(n²)
O(n²)
O(n²)
O(1)
选择排序的简单和直观名副其实,这也造就了它”出了名的慢性子”,无论是哪种情况,哪怕原数组已排序完成,它也将花费将近n²/2次遍历来确认一遍.即便是这样,它的排序结果也还是不稳定的.唯一值得高兴的是,它并不耗费额外的内存空间.
插入排序
插入排序的设计初衷是往有序的数组中快速插入一个新的元素.它的算法思想是:把要排序的数组分为了两个部分,一部分是数组的全部元素(除去待插入的元素),另一部分是待插入的元素;先将第一部分排序完成,然后再插入这个元素.其中第一部分的排序也是通过再次拆分为两部分来进行的.
插入排序由于操作不尽相同,可分为直接插入排序,折半插入排序(又称二分插入排序),链表插入排序,希尔排序.
直接插入排序
它的基本思想是:将待排序的元素按照大小顺序,依次插入到一个已经排好序的数组之中,直到所有的元素都插入进去.
如下是动图效果:
如下是上图的算法实现:
functiondirectInsertionSort(array){
varlength=array.length,index,current;
for(vari=1;i=0&&array[index]>current){//前置条件之一:待比较元素比当前元素大
array[index+1]=array[index];//将待比较元素后移一位
index--;//游标前移一位
//console.log(array);
}
if(index+1!=i){//避免同一个元素赋值给自身
array[index+1]=current;//将当前元素插入预留空位
//console.log(array);
}
}
returnarray;
}
为了更好的观察到直接插入排序的实现过程,我们不妨将上述代码中的注释部分加入.以数组[5,4,3,2,1]为例,如下便是原数组的演化过程.
可见,数组的各个元素,从后往前,只要比前面的元素小,都依次插入到了合理的位置.
Tips:由于直接插入排序每次只移动一个元素的位置,并不会改变值相同的元素之间的排序,因此它是一种稳定排序.
折半插入排序
折半插入排序是直接插入排序的升级版.鉴于插入排序第一部分为已排好序的数组,我们不必按顺序依次寻找插入点,只需比较它们的中间值与待插入元素的大小即可.
Tips:同直接插入排序类似,折半插入排序每次交换的是相邻的且值为不同的元素,它并不会改变值相同的元素之间的顺序.因此它是稳定的.
算法基本思想是:
- 取0~i-1的中间点( m=(i-1)>>1 ),array[i]与array[m]进行比较,若array[i]
- 重复步骤1,每次缩小一半的查找范围,直至找到插入的位置.
- 将数组中插入位置之后的元素全部后移一位.
- 在指定位置插入第i个元素.
注:x>>1是位运算中的右移运算,表示右移一位,等同于x除以2再取整,即x>>1==Math.floor(x/2).
如下是算法实现:
functionbinaryInsertionSort(array){
varcurrent,i,j,low,high,m;
for(i=1;i>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:插入该元素
}
returnarray;
}
为了便于对比,同样以数组[5,4,3,2,1]举例