javascript中可能用得到的全部的排序算法

//先将交换元素部分抽象出来
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;
}

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;
}

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;
}

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;
}

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;
}

//形参增加步数gap(实际上就相当于gap替换了原来的数字1)
function directInsertionSort(array, gap) {
 gap = (gap == undefined) "htmlcode">

function shellSort(array){
 var length = array.length, gap = length1, current, i, j;
 while(gap > 0){
 directInsertionSort(array, gap); //按指定步长进行直接插入排序
 gap = gap1;
 }
 return array;
}


同样以数组[5,4,3,2,1] 举例"希尔排序" src="/UploadFiles/2021-04-02/2020030521082561.png">
对比上述直接插入排序和折半插入排序, 数组元素的移动次数由14次减少为7次. 通过拆分原数组为粒度更小的子数组, 希尔排序进一步提高了排序的效率.
不仅如此, 以上步长设置为了 {N/2, (N/2)/2, …, 1}. 该序列即希尔增量, 其它的增量序列 还有Hibbard：{1, 3, …, 2^k-1}. 通过合理调节步长, 还能进一步提升排序效率. 实际上已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…). 该序列中的项或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1. 具体请戳 希尔排序-维基百科 .

Tips: 我们知道, 单次直接插入排序是稳定的, 它不会改变相同元素之间的相对顺序, 但在多次不同的插入排序过程中, 相同的元素可能在各自的插入排序中移动, 可能导致相同元素相对顺序发生变化. 因此, 希尔排序并不稳定.

归并排序
归并排序建立在归并操作之上, 它采取分而治之的思想, 将数组拆分为两个子数组, 分别排序, 最后才将两个子数组合并; 拆分的两个子数组, 再继续递归拆分为更小的子数组, 进而分别排序, 直到数组长度为1, 直接返回该数组为止.

Tips: 归并排序严格按照从左往右(或从右往左)的顺序去合并子数组, 它并不会改变相同元素之间的相对顺序, 因此它也是一种稳定的排序算法.

如下是动图效果:

归并排序可通过两种方式实现:

  
自上而下的递归
  
自下而上的迭代

如下是算法实现(方式1:递归):


function mergeSort(array) { //采用自上而下的递归方法
 var length = array.length;
 if(length < 2) {
 return array;
 }
 var m = (length  1),
 left = array.slice(0, m),
 right = array.slice(m); //拆分为两个子数组
 return merge(mergeSort(left), mergeSort(right));//子数组继续递归拆分,然后再合并
}
function merge(left, right){ //合并两个子数组
 var result = [];
 while (left.length && right.length) {
 var item = left[0] <= right[0] "htmlcode">

function computeMaxCallStackSize() {
 try {
 return 1 + computeMaxCallStackSize();
 } catch (e) {
 // Call stack overflow
 return 1;
 }
}
var time = computeMaxCallStackSize();
console.log(time);


为此, ES6规范中提出了尾调优化的思想: 如果一个函数的最后一步也是一个函数调用, 那么该函数所需要的栈空间将被释放, 它将直接进入到下次调用中, 最终调用栈里只保留最后一次的调用记录.
虽然ES6规范如此诱人, 然而目前并没有浏览器支持尾调优化, 相信在不久的将来, 尾调优化就会得到主流浏览器的支持.
以下是其算法复杂度:


  
    
      平均时间复杂度
      最好情况
      最坏情况
      空间复杂度
    
  
  
    
      O(nlog"快速排序" src="/UploadFiles/2021-04-02/2020030521082663.gif">
如下是算法实现:


function quickSort(array, left, right) {
 var partitionIndex,
 left = typeof left == 'number' "external nofollow" href="https://louiszhai.github.io/2016/12/23/sort/#respond">1 (即堆顶)和无序区的最后一个记录K[n]交换, 由此得到新的无序区K[1..n-1]和有序区K[n], 且满足K[1..n-1].keys≤K[n].key
  
交换K1 和 K[n] 后, 堆顶可能违反堆性质, 因此需将K[1..n-1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止.

如下是动图效果:

如下是算法实现:


function heapAdjust(array, i, length) {//堆调整
 var left = 2 * i + 1,
 right = 2 * i + 2,
 largest = i;
 if (left < length && array[largest] < array[left]) {
 largest = left;
 }
 if (right < length && array[largest] < array[right]) {
 largest = right;
 }
 if (largest != i) {
 swap(i, largest, array);
 heapAdjust(array, largest, length);
 }
}
function heapSort(array) {
 //建立大顶堆
 length = array.length;
 for (var i = length1; i >= 0; i--) {
 heapAdjust(array, i, length);
 }
 //调换第一个与最后一个元素,重新调整为大顶堆
 for (var i = length - 1; i > 0; i--) {
 swap(0, i, array);
 heapAdjust(array, 0, --length);
 }
 return array;
}


以上, ①建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
②调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);
③堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn).

Tips: 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.

计数排序
计数排序几乎是唯一一个不基于比较的排序算法, 该算法于1954年由 Harold H. Seward 提出. 使用它处理一定范围内的整数排序时, 时间复杂度为O(n+k), 其中k是整数的范围, 它几乎比任何基于比较的排序算法都要快( 只有当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序, 如归并排序和堆排序).
使用计数排序需要满足如下条件:

  
待排序的序列全部为整数
  
排序需要额外的存储空间

算法的基本思想:

计数排序利用了一个特性, 对于数组的某个元素, 一旦知道了有多少个其它元素比它小(假设为m个), 那么就可以确定出该元素的正确位置(第m+1位)


  
获取待排序数组A的最大值, 最小值.
  
将最大值与最小值的差值+1作为长度新建计数数组B，并将相同元素的数量作为值存入计数数组.
  
对计数数组B累加计数, 存储不同值的初始下标.
  
从原数组A挨个取值, 赋值给一个新的数组C相应的下标, 最终返回数组C.


注意: 如果原数组A是包含若干个对象的数组，需要基于对象的某个属性进行排序，那么算法开始时，需要将原数组A处理为一个只包含对象属性值的简单数组simpleA, 接下来便基于simpleA进行计数、累加计数, 其它同上.

如下是动图效果:

如下是算法实现:


function countSort(array, keyName){
 var length = array.length,
 output = new Array(length),
 max,
 min,
 simpleArray = keyName "htmlcode">

var a = [2, 1, 1, 3, 2, 1, 4, 2],
 b = [
 {id: 2, s:'a'}, 
 {id: 1, s: 'b'}, 
 {id: 1, s: 'c'}, 
 {id: 3, s: 'd'}, 
 {id: 2, s: 'e'}, 
 {id: 1, s: 'f'}, 
 {id: 4, s: 'g'}, 
 {id: 2, s: 'h'}
 ];
countSort(a); // [1, 1, 1, 2, 2, 2, 3, 4]
countSort(b, 'id'); // [{id:1,s:'b'},{id:1,s:'c'},{id:1,s:'f'},{id:2,s:'a'},{id:2,s:'e'},{id:2,s:'h'},{id:3,s:'d'},{id:4,s:'g'}]



Tips: 计数排序不改变相同元素之间原本相对的顺序, 因此它是稳定的排序算法.

桶排序
桶排序即所谓的箱排序, 它是将数组分配到有限数量的桶子里. 每个桶里再各自排序(因此有可能使用别的排序算法或以递归方式继续桶排序). 当每个桶里的元素个数趋于一致时, 桶排序只需花费O(n)的时间. 桶排序通过空间换时间的方式提高了效率, 因此它需要额外的存储空间(即桶的空间).
算法的基本思想:
桶排序的核心就在于怎么把元素平均分配到每个桶里, 合理的分配将大大提高排序的效率.
如下是算法实现:


function bucketSort(array, bucketSize) {
 if (array.length === 0) {
 return array;
 }

 var i = 1,
 min = array[0],
 max = min;
 while (i++ < array.length) {
 if (array[i] < min) {
 min = array[i]; //输入数据的最小值
 } else if (array[i] > max) {
 max = array[i]; //输入数据的最大值
 }
 }

 //桶的初始化
 bucketSize = bucketSize || 5; //设置桶的默认大小为5
 var bucketCount = ~~((max - min) / bucketSize) + 1, //桶的个数
 buckets = new Array(bucketCount); //创建桶
 for (i = 0; i < buckets.length; i++) {
 buckets[i] = []; //初始化桶
 }

 //将数据分配到各个桶中,这里直接按照数据值的分布来分配,一定范围内均匀分布的数据效率最为高效
 for (i = 0; i < array.length; i++) {
 buckets[~~((array[i] - min) / bucketSize)].push(array[i]);
 }

 array.length = 0;
 for (i = 0; i < buckets.length; i++) {
 quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序
 for (var j = 0; j < buckets[i].length; j++) {
 array.push(buckets[i][j]); //将已排序的数据写回数组中
 }
 }
 return array;
}



Tips: 桶排序本身是稳定的排序, 因此它的稳定性与桶内排序的稳定性保持一致.

实际上, 桶也只是一个抽象的概念, 它的思想与归并排序,快速排序等类似, 都是通过将大量数据分配到N个不同的容器中, 分别排序, 最后再合并数据. 这种方式大大减少了排序时整体的遍历次数, 提高了算法效率.
基数排序
基数排序源于老式穿孔机, 排序器每次只能看到一个列. 它是基于元素值的每个位上的字符来排序的. 对于数字而言就是分别基于个位, 十位, 百位 或千位等等数字来排序. (不明白不要紧, 我也不懂, 请接着往下读)
按照优先从高位或低位来排序有两种实现方案:

  
MSD: 由高位为基底, 先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列. MSD方式适用于位数多的序列.
  
LSD: 由低位为基底, 先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列. LSD方式适用于位数少的序列.

如下是LSD的动图效果:

如下是算法实现:


function radixSort(array, max) {
 var buckets = [],
 unit = 10,
 base = 1;
 for (var i = 0; i < max; i++, base *= 10, unit *= 10) {
 for(var j = 0; j < array.length; j++) {
 var index = ~~((array[j] % unit) / base);//依次过滤出个位,十位等等数字
 if(buckets[index] == null) {
 buckets[index] = []; //初始化桶
 }
 buckets[index].push(array[j]);//往不同桶里添加数据
 }
 var pos = 0,
 value;
 for(var j = 0, length = buckets.length; j < length; j++) {
 if(buckets[j] != null) {
 while ((value = buckets[j].shift()) != null) {
  array[pos++] = value; //将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
 }
 }
 }
 }
 return array;
}


以上算法, 如果用来比较时间, 先按日排序, 再按月排序, 最后按年排序, 仅需排序三次.
基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序.

Tips: 基数排序不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

小结
各种排序性能对比如下:


  
    
      排序类型
      平均情况
      最好情况
      最坏情况
      辅助空间
      稳定性
    
  
  
    
      冒泡排序
      O(n²)
      O(n)
      O(n²)
      O(1)
      稳定
    
    
      选择排序
      O(n²)
      O(n²)
      O(n²)
      O(1)
      不稳定
    
    
      直接插入排序
      O(n²)
      O(n)
      O(n²)
      O(1)
      稳定
    
    
      折半插入排序
      O(n²)
      O(n)
      O(n²)
      O(1)
      稳定
    
    
      希尔排序
      O(n^1.3)
      O(nlogn)
      O(n²)
      O(1)
      不稳定
    
    
      归并排序
      O(nlog"external nofollow" target="_blank" href="http://visualgo.net/">http://visualgo.net/ 提供图片支持. 特别感谢 不是小羊的肖恩 在简书上发布的 JS家的排序算法 提供的讲解.

        

            
上一篇：Vue状态模式实现窗口停靠功能(灵动、自由, 管理后台Admin界面)
            
下一篇：js的Object.assign用法示例分析