JS排序算法

本篇有7k+字, 系统梳理了js中排序算法相关的知识, 希望您能喜欢.

1、冒泡排序
冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。
假设一共有n项,那么一共需要n-1趟,第一趟需要交换n-1次,但是第一趟结束后,最后一项基本确定就是最大项了,所以第二次需要交换n-2次,第i次交换n-i次。
澳门威斯尼人平台登录 1

什么是算法

高德纳在《计算机程序设计艺术》里对算法的归纳:
书籍推荐:《数据结构与算法分析》

  1. 输入:一个算法必须有零个或以上输入量
  2. 输出:一个算法应有一个或以上的输出量
  3. 明确性:算法的描述必须无歧义,实际运行结果是确定的
  4. 有限性:必须在有限个步骤内结束
  5. 有效性:又称可行性。能过被执行者实现

排序算法可视化网站推荐:
https://visualgo.net/zh/sorting

冒泡排序:

在平时的工作中呢也用不到太多的算法,但是私认为算法还是挺锻炼一个程序员的逻辑思维的,写一下会的几种算法吧

原文:JS中可能用得到的全部的排序算法

这种排序最好情况下时间复杂度是O(n),一般情况下时间复杂度是O(n²),最差情况下也是O(n²)。


这里是代码演示: 

问题

数组 array 含有 N 个正整数,
输入量为 array,
请将 array 中的数字从小到大排列,
输出量为排好序的数组。

例如

var array = [5, 2, 4, 6, 8]
function sort(){
   // body
}
sort(array)  == [2, 4, 5, 6, 8]

vararray =
[{“name”:”aa”,index:100},{“name”:”aa”,index:200},{“name”:”aa”,index:300}];

冒泡排序:

导读

冒泡排序(Bubble Sort)

第一个数字开始,每一个数字与自身相邻的后一位数字比较,如果后一位数字较小,则互换位置,否则不换,第一次所有数字都比较完毕后(比较
n-1 次即可完成),最后一位数字是最大的,依此类推(第二次比较 n-2
次),直到完成排序(最后剩余2个数字比较1次即可)

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
排序步骤如下:
第i 9 次 5,2,6,8,3,1,4,0,7,9  // 第一轮比较结束后,较大的互换位置,9最大,在最后面,比较次数8次
第i 8 次 2,5,6,3,1,4,0,7,8,9  // 第二轮比较结束后8最大,较大的互换位置,在最后面,比较次数7次,依次类推
第i 7 次 2,5,3,1,4,0,6,7,8,9
第i 6 次 2,3,1,4,0,5,6,7,8,9
第i 5 次 2,1,3,0,4,5,6,7,8,9
第i 4 次 1,2,0,3,4,5,6,7,8,9
第i 3 次 1,0,2,3,4,5,6,7,8,9
第i 2 次 0,1,2,3,4,5,6,7,8,9
第i 1 次 0,1,2,3,4,5,6,7,8,9

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(bubbleSort(arr));

function bubbleSort(array){
    var temp;  // 获取临时参数
    // 最外层比较 i 次
    for(var i = array.length - 1; 0 < i; i--){
        // 确定内层循环边界
        for(var j = 0; j < i; j++){
            // 如果后一个数字较小,则调换位置
            if (array[j] > array[j+1]) {  
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            } 
        console.log('第j ' + i + '  ' + j + ' 次 ' + array)       
        }
    console.log('第i ' + i + ' 次 ' + array)
    }
    return array;
}

varlen = array.length;

function bubbleSort(arr){
        for(var i=0;i<arr.length;i++){
            for(var j=0;j<arr.length-i;j++){
                if(arr[j]>arr[j+1]){
                    var num = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = num;
                }
            }
            console.log(arr);
        }
        return arr
    }
    var num = [1,2,1,3,7,4,9,0];
    console.log(bubbleSort(num));

排序算法可以称得上是我的盲点,
曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时,
我的内心是奔溃的(啥是快排, 我只知道冒泡啊?!),
要知道学习一门技术最好的时间是三年前, 但愿我现在补习还来得及.

2、选择排序
选择排序是找到最小的一项,然后和第一项交换位置,然后找到第二小的和第二项交换,依次类推,一共需要n-1次。
澳门威斯尼人平台登录 2

选择排序(Select Sort)

第一个数字开始(开始时认为第一个数字为最小数字),第一个数字与所有的数字比较,获得数组中最小的数字,最小的数字与第一个数字互换位置,则最小的在第一个,然后第二个数字开始,重复第一次的流程,直到剩余最后一个数字,则剩余的数字为最大的数字而且出现在末尾,最小的数字在第一个,排序完成

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步骤如下:
第i 0 次 8,5,2,6,9,3,1,4,0,7  // 第一轮比较结束后,0最小,与8互换位置
第i 1 次 0,5,2,6,9,3,1,4,8,7  // 第二轮比较结束后,1最小,与5互换位置
第i 2 次 0,1,2,6,9,3,5,4,8,7
第i 3 次 0,1,2,6,9,3,5,4,8,7
第i 4 次 0,1,2,3,9,6,5,4,8,7
第i 5 次 0,1,2,3,4,6,5,9,8,7
第i 6 次 0,1,2,3,4,5,6,9,8,7
第i 7 次 0,1,2,3,4,5,6,9,8,7
第i 8 次 0,1,2,3,4,5,6,7,8,9

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(selectSort(arr));

function selectSort(array){
    var temp,
        minIndex,
        minValue;
    for(var i = 0; i < array.length - 1; i++){
        minIndex = i;
        minValue = array[minIndex];
        for(var j = i + 1; j < length; j++){
            // 如果当前最小值大于数组中的数字,则数组中的数字为最小,获取其下标和值
            if(minValue > array[j]){
                minIndex = j;
                minValue = array[minIndex];
            }
            // console.log('第j ' + j + ' 次 ' + array);
        }
        console.log('第i ' + i + ' 次 ' + array);
        // 将最小值和当前开始比较多数字位置互换
        temp = array[i];
        array[i] = minValue;
        array[minIndex] = temp;
    }
    return array;
}    

for(vari =0; i < len -1; i++) {//-1
是为了j+1不会发生数组越界,且不会和自己比较

解析一下:

因此本篇重拾了出镜概率比较高的十来种排序算法, 逐一分析其排序思想,
并批注注意事项. 欢迎对算法提出改进和讨论.

选择排序在所有情况下空间复杂度都是O(n²)。

代码演示:

插入排序(Insertion Sort)

类似于扑克牌摸牌,得到一个数字,大于此数字放在右侧,小于此数字放在左侧,如果左侧或者右侧有多个数字,则依次进行比较,直到找到合适位置,依次类推,以下面示例代码中数组为例:

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步骤如下
[ 5, 8, 2, 6, 9, 3, 1, 4, 0, 7 ]  // 第一轮比较结束后,5和8互换位置
[ 2, 5, 8, 6, 9, 3, 1, 4, 0, 7 ]  // 第二轮比较结束后,2小于5、8,所以与5、8分别互换位置
[ 2, 5, 6, 8, 9, 3, 1, 4, 0, 7 ]  // 第三轮比较结束后,6大于5,小于8,所以与8互换位置,依次类推
[ 2, 5, 6, 8, 9, 3, 1, 4, 0, 7 ]
[ 2, 3, 5, 6, 8, 9, 1, 4, 0, 7 ]
[ 1, 2, 3, 5, 6, 8, 9, 4, 0, 7 ]
[ 1, 2, 3, 4, 5, 6, 8, 9, 0, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 8, 9, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(inserterSort(arr));

function inserterSort(array) {
    // 
    var temp;
    for (var i = 1; i < array.length; i++) {
        for (var j = i; j > 0; j--) {
            // 如果前一个比当前数字大,则交换位置
           if (array[j-1] > array[j]) {
            temp = array[j-1];
            array[j-1] = array[j];
            array[j] = temp;
            // 如果前一个比当前数字小,不做变动,退出循环
           } else {
            break;
           }
        }
    }
    return array
}

for(varj =0; j < len – i -1;j++) {

·第一遍外循环i=0时,j也是0,j<arr.length-i的话呢,就是遍历整个数组,里面的if判断呢就是两两比较,arr[j]和arr[j+1]哪个大,然后把大的放在后面,这样就把数组中最大的那个家伙放到的数组末尾啦

冒泡排序

归并排序(Merge Sort)

领导算法,得到一个数组时,将数组一分为二(一直分半,直到剩余1个或者2个数字),对其分别排序,然后再放到一起排序,直到完成,以下面示例代码中的数组为例:

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
排序步骤如下
第一次划分:[8, 5, 2, 6, 9]; [3, 1, 4, 0, 7]
第二次划分:[8, 5, 2]; [6, 9]; [3, 1,4]; [0, 7]
第三次划分:[8, 5]; [2]; [6, 9]; [3, 1]; [4]; [0, 7]
第一次排序:[5, 8]; [2]; [6, 9]; [1, 3]; [4]; [0, 7]
第二次排序:[2, 5, 8]; [6, 9]; [1, 3, 4]; [0, 7]
第三次排序:[2, 5, 6, 8, 9]; [0, 1, 3, 4, 7]
第三次排序:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(mergeSort(arr));

function mergeSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    var pivot = Math.floor(arr.length / 2);  // 每次获取中间位置为基准位置
    var left = arr.slice(0, pivot);  // 将原有数组一分为二
    var right = arr.slice(pivot);

    function merge(left, right){
        var result = [];
        while (left.length > 0 && right.length > 0) {
            // 重复对比,小的放到数组前面
            if(left[0] < right[0]){
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        console.log('result ' + result);
        // 将结果合并返回
        return result.concat(left, right);
    }
    console.log(arr);
    // 重复一分为二
    return merge(mergeSort(left), mergeSort(right));
}

if(array[j] < array[j+1]) {

·第二遍外循环i=1时,j还是0,j<arr.length-i呢,内循环就不会遍历到数组的末尾了,就是最大的那个家伙呢不用参加这次遍历了,那么这次呢,又把数组里面第二大的家伙排到了倒数第二的位置了

冒泡

3、插入排序
插入排序是将前面的项看做数组,然后后面的项根据大小插入到对应的位置。比如第二项和第一项对比,他该插到第一项前面还是后面呢?第三项该插到一二项的哪个地方?
这个一般也需要插入n-1次。
澳门威斯尼人平台登录 3

快速排序(Quick Sort)

得到一个数组,获取中间位置的数字作为基准,比基准位置数字小的都到放到其前面,比基准数字大的都放到其后面,然后左右两边再分别找到基准位置,分别排序,直到完成。

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步骤如下:
第一次划分:[2, 1, 0]; [8, 5, 6, 9, 4, 7]
第二次划分:[0]; [2]; [5, 4]; [8, 9, 7]
第三次划分:[0]; [2]; [5, 4]; [8, 7]
第一次排序:[0, 1, 2]; [4, 5]; [7, 8, 9]
第二次排序:[0, 1, 2, 3]; [4, 5, 6, 7, 8, 9]
第三次排序:[0, 1, 2, 3,4, 5, 6, 7, 8, 9]
此处写的较为模糊,以下面代码为基准写的排序步骤,建议参考文章开头的可视化网站理解

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(quickSort(arr));

function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    var pivotInedx = Math.floor(arr.length / 2);  // 每次选择中间位置作为基准位置
    var pivot = arr.splice(pivotInedx, 1)[0];  // 选择基准位置上的数字
    console.log(pivot);
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        // 将数据一分为二,小于基准数字的数据放在左边数组中,大于或等于放在右边数组中
        if(arr[i] < pivot){
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
        console.log(arr)
    }
    // 重复调用,并将得到的数组拼接在一起,完成为止
    return quickSort(left).concat([pivot],quickSort(right));
}

vartemp = a[j];

·后面就是同上类推了,理解一下的话,就是冒泡一样,把最大的一遍一遍的冒泡到数组的末尾,退出整个函数的时候呢,整个数组就排好顺序了

冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标;
内层循环遍历游标及之后的元素, 通过两两交换的方式,
每次只确保该内循环结束位置排序正确, 然后内层循环周期结束,
交由外层循环往后移动游标, 随即开始下一轮内层循环, 以此类推,
直至循环结束.

插入排序最好情况下时间复杂度是O(n),其他情况下也都是O(n²)。

代码演示:

随机快速排序(Random Quick Sort)

原理同快速排序,只是基准位置为数组中随机数字,某些情况下排序的速度快于快速排序

var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(quickSort(arr));
function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    var pivotInedx = Math.floor(Math.random() * arr.length);  // 随机选择基准位置
    var pivot = arr.splice(pivotInedx, 1)[0];  // 选择基准位置上的数字
    console.log(pivot);
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        // 将数据一分为二,小于基准数字的数据放在左边数组中,大于或等于放在右边数组中
        if(arr[i] < pivot){
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
        console.log(arr)
    }
    // 重复调用,并将得到的数组拼接在一起,完成为止
    return quickSort(left).concat([pivot],quickSort(right));
}

a[j] = a[j+1];

 

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置,
它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

a[j+1] = temp;//交换位置

快速排序:

由于有两层循环, 因此可以有四种实现方式.

4、归并排序
原生js里面的sort方法,在firefox里面是用归并排序实现的,而在chrome里面是用快速排序的变体来实现的。
澳门威斯尼人平台登录 4

}

function quickSort(arr){
        if(arr.length <= 1){
            return arr;
        }
        var index = Math.floor(arr.length/2);
        var middle = arr.splice(index,1);
        var left = [];
        var right = [];
        for(var i=0;i<arr.length;i++) {
            if(arr[i] < middle){
                left.push(arr[i])
            }else{
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat(middle,quickSort(right));
    }

    var aaa = [1,3,2,7,1,5,9,2];
    alert(quickSort(aaa));

方案外层循环内层循环1正序正序2正序逆序3逆序正序4逆序逆序

归并排序是一种分治的算法,他是将一个大数组分成无数的小数组,如果小数组里面只有一项,那么直接返回,如果大于一项,就继续分,接着小数组合并成一个大数组,合并的时候左右会进行比较大小,然后排序

代码演示:

}

解析:

四种不同循环方向, 实现方式略有差异.

}

·首先判断数组长度是否小于等于1,是的话直接return回去

如下是动图效果(对应于方案1: 内/外层循环均是正序遍历.

5、快速排序
快速排序也使用了分治的算法,也是把大数组分成小数组.
它会选择一个中间元,创建两个左右指针,然后分别从左右开始出发,如果左指针遇到比中间元大的数,它会停下来,而右边的如果遇到比中间元小的数,它也会停下来,然后两者交换位置。
接着两个指针继续前进,直到左指针超过了右指针,这样左边的数就会小于中间元,右边的数都会大于中间元,接下来分成左右数组,然后再进行上面的操作,直到数组完全排序。

快速排序:

·splice取出数组的中位数middle,整个数组里面没有middle这个数了哦

冒泡排序

澳门威斯尼人平台登录 5

vararr =
[{“name”:”aa”,index:200},{“name”:”aa”,index:100},{“name”:”aa”,index:300}];

·新建两个left和right数组

如下是上图的算法实现(对应方案一: 内/外层循环均是正序遍历).

代码演示:

functionqSort(arr,i,j){

·遍历整个数组,判断arr[i]是小于还是大于中位数middle,小于的push到left这个数组,大于的push到right这个数组里

//先将交换元素部分抽象出来function swap(i,j,array){ var temp =
array[j]; array[j] = array[i]; array[i] = temp;}

if(i>=j)return;

·最后一句,将left和right两个数组当做参数递归调用quickSort函数。并且呢用concat连接起来,别忘了还有个中位数哦

function bubbleSort { 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 break; } return array;}

vartempi=i,tempj=j;

·之后的递归就是回到第一步重复调用了,当left或者right数组长度为1时,就是排好顺序啦

以上, 排序的特点就是: 靠后的元素位置先确定.

varkey=arr[i];

整个快速排序算法的逻辑就是把数组对半,小的放左边,大的放右边,然后再把左右两边继续对半分,小的放左边,大的放右边,不断如此··········

方案二: 外循环正序遍历, 内循环逆序遍历, 代码如下:

while(i<j){

拿写的aaa数组来说,中位数是7,那么left就是[1,3,2,1,5,2],right就是[9],然后递归left,还是很好理解的吧

function bubbleSort { 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 break; } return array;}

while(i<j&&arr[j].index>key.index)
j–;//从右向左找第1个小于key的数

 

以上, 靠前的元素位置先确定.

if(i<j) arr[i++]=arr[j];

 

方案三: 外循环逆序遍历, 内循环正序遍历, 代码如下:

while(i<j&&arr[i].index<key.index)
i++;//从左向右找第1个大于key的数

最后是JS的array对象的sort方法排序,我也不知叫什么名-。-

function bubbleSort { 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 break; } return array;}

if(i<j) arr[j–]=arr[i];

function ArraySort(){
        var tag = [];
        for(var i= 0;i<arguments.length;i++){
            tag.push(arguments[i]);
        }
        tag.sort(function(compare1,compare2){
            return compare1 - compare2
        })
        return tag
    }
    console.log(ArraySort(1,2,5,1,2,3,9,7,8));

以上, 由于内循环是正序遍历, 因此靠后的元素位置先确定.

}

解析:

方案四: 外循环逆序遍历, 内循环逆序遍历, 代码如下:

arr[i]=key;

·sort方法传入两个参数compare1,compare2,两两进行比较,如果compare1-compare2小于0呢,两两之间就不换位置,反之就调换位置

function bubbleSort { var length = array.length, isSwap; for (var i =
length – 1; i >= 0; i–) { //逆序 isSwap = false; for (var j = length

qSort(arr,tempi,i-1);

·当然可以这样写 return compare2 – compare1,这样呢就是倒序排列了

  • 1; j >= length – 1 – i; j–) { //逆序 array[j] < array[j-1]
    && (isSwap = true) && swap(j,j-1,array); } if break; } return array;}

qSort(arr,i+1,tempj);

 

以上, 由于内循环是逆序遍历, 因此靠前的元素位置先确定.

}

本人资历尚浅,如果表达或者理解有错,欢迎大家指正交流

以下是其算法复杂度:

qSort(arr,0,2)

平均时间复杂度最好情况最坏情况空间复杂度OO

澳门威斯尼人平台登录 ,选择排序:

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换,
共需遍历并交换将近n²/2次, 时间复杂度为O.
最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O.
平均来讲, 时间复杂度为O. 由于冒泡排序中只有缓存的temp变量需要内存空间,
因此空间复杂度为常量O.

varmin,len = arr.length;

双向冒泡排序

for(vari =0; i < len -1; i++) {

双向冒泡排序是冒泡排序的一个简易升级版, 又称鸡尾酒排序.
冒泡排序是从低到高单向排序,
双向冒泡排序顾名思义就是从两个方向分别排序(通常, 先从低到高,
然后从高到低). 因此它比冒泡排序性能稍好一些.

min = i;

如下是算法实现:

for(varj = i +1; j < len ; j++) {

function bothwayBubbleSort{ 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;}

if(arr[j].index < arr[min].index) {

选择排序

min = j;

从算法逻辑上看, 选择排序是一种简单且直观的排序算法. 它也是两层循环.
内层循环就像工人一样, 它是真正做事情的, 内层循环每执行一遍,
将选出本次待排序的元素中最小的一个, 存放在数组的起始位置. 而
外层循环则像老板一样, 它告诉内层循环你需要不停的工作,
直到工作完成(也就是全部的元素排序完成).

}

Tips: 选择排序每次交换的元素都有可能不是相邻的,
因此它有可能打破原来值为相同的元素之间的顺序. 比如数组[2,2,1,3],
正向排序时, 第一个数字2将与数字1交换,
那么两个数字2之间的顺序将和原来的顺序不一致, 虽然它们的值相同,
但它们相对的顺序却发生了变化. 我们将这种现象称作 不稳定性 .

}

如下是动图效果:

vartemp = arr[min];

选择排序

arr[min] = arr[i];

如下是上图的算法实现:

arr[i] = temp;

function selectSort { 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!=i &&
swap(i,min,array); } return array;}

}

以下是其算法复杂度:

平均时间复杂度最好情况最坏情况空间复杂度OO

选择排序的简单和直观名副其实, 这也造就了它”出了名的慢性子”,
无论是哪种情况, 哪怕原数组已排序完成,
它也将花费将近n²/2次遍历来确认一遍. 即便是这样,
它的排序结果也还是不稳定的. 唯一值得高兴的是, 它并不耗费额外的内存空间.

插入排序

插入排序的设计初衷是往有序的数组中快速插入一个新的元素. 它的算法思想是:
把要排序的数组分为了两个部分, 一部分是数组的全部元素,
另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素.
其中第一部分的排序也是通过再次拆分为两部分来进行的.

插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序,
链表插入排序, 希尔排序 .

直接插入排序

它的基本思想是: 将待排序的元素按照大小顺序,
依次插入到一个已经排好序的数组之中, 直到所有的元素都插入进去.

如下是动图效果:

直接插入排序

如下是上图的算法实现:

function directInsertionSort { 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; } if(index+1 != i){
//避免同一个元素赋值给自身 array[index+1] = current;
//将当前元素插入预留空位 //console.log; } } return array;}

为了更好的观察到直接插入排序的实现过程,
我们不妨将上述代码中的注释部分加入. 以数组 [5,4,3,2,1] 为例,
如下便是原数组的演化过程.

可见, 数组的各个元素, 从后往前, 只要比前面的元素小,
都依次插入到了合理的位置.

Tips: 由于直接插入排序每次只移动一个元素的位置,
并不会改变值相同的元素之间的排序, 因此它是一种稳定排序.

折半插入排序

折半插入排序是直接插入排序的升级版.
鉴于插入排序第一部分为已排好序的数组, 我们不必按顺序依次寻找插入点,
只需比较它们的中间值与待插入元素的大小即可.

Tips: 同直接插入排序类似,
折半插入排序每次交换的是相邻的且值为不同的元素,
它并不会改变值相同的元素之间的顺序. 因此它是稳定的.

算法基本思想是:

取0 ~ i-1的中间点( m = >>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 .

如下是算法实现:

function binaryInsertionSort{ 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] 举例🌰. 原数组的演化过程如下:

折半插入排序

虽然折半插入排序明显减少了查询的次数, 但是数组元素移动的次数却没有改变.
它们的时间复杂度都是O.

希尔排序

希尔排序也称缩小增量排序, 它是直接插入排序的另外一个升级版,
实质就是分组插入排序. 希尔排序以其设计者希尔(Donald Shell)的名字命名,
并于1959年公布.

算法的基本思想:

将数组拆分为若干个子分组, 每个分组由相距一定”增量”的元素组成.
比方说将[0,1,2,3,4,5,6,7,8,9,10]的数组拆分为”增量”为5的分组,
那么子分组分别为 [0,5], [1,6], [2,7], [3,8], [4,9] 和
[5,10].

然后对每个子分组应用直接插入排序.

逐步减小”增量”, 重复步骤1,2.

直至”增量”为1, 这是最后一个排序, 此时的排序,
也就是对全数组进行直接插入排序.

如下是排序的示意图:

希尔排序示意图

可见, 希尔排序实际上就是不断的进行直接插入排序,
分组是为了先将局部元素有序化. 因为直接插入排序在元素基本有序的状态下,
效率非常高. 而希尔排序呢, 通过先分组后排序的方式,
制造了直接插入排序高效运行的场景. 因此希尔排序效率更高.

我们试着抽象出共同点,
便不难发现上述希尔排序的第四步就是一次直接插入排序,
而希尔排序原本就是从”增量”为n开始, 直至”增量”为1,
循环应用直接插入排序的一种封装.
因此直接插入排序就可以看做是步长为1的希尔排序.
为此我们先来封装下直接插入排序.

//形参增加步数gap(实际上就相当于gap替换了原来的数字1)function
directInsertionSort(array, gap) { gap = (gap == undefined) ? 1 : gap;
//默认从下标为1的元素开始遍历 var length = array.length, index, current;
for (var i = gap; i < length; i++) { index = i – gap;
//待比较元素的下标 current = array[i]; //当前元素 while(index >= 0
&& array[index] > current) { //前置条件之一:待比较元素比当前元素大
array[index + gap] = array[index]; //将待比较元素后移gap位 index -=
gap; //游标前移gap位 } if(index + gap != i){ //避免同一个元素赋值给自身
array[index + gap] = current; //将当前元素插入预留空位 } } return
array;}

那么希尔排序的算法实现如下:

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

同样以数组[5,4,3,2,1] 举例🌰. 原数组的演化过程如下:

希尔排序

对比上述直接插入排序和折半插入排序, 数组元素的移动次数由14次减少为7次.
通过拆分原数组为粒度更小的子数组, 希尔排序进一步提高了排序的效率.

不仅如此, 以上步长设置为了 {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: 归并排序严格按照从左往右的顺序去合并子数组,
它并不会改变相同元素之间的相对顺序, 因此它也是一种稳定的排序算法.

如下是动图效果:

归并排序

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

自上而下的递归

自下而上的迭代

如下是算法实现:

function mergeSort { //采用自上而下的递归方法 var length = array.length;
if(length < 2) { return array; } var m = (length >> 1), left =
array.slice, right = array.slice; //拆分为两个子数组 return
merge(mergeSort, mergeSort;//子数组继续递归拆分,然后再合并}function
merge(left, right){ //合并两个子数组 var result = []; while
(left.length && right.length) { var item = left[0] <= right[0] ?
left.shift() :
right.shift();//注意:判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
result.push; } return result.concat(left.length ? left : right);}

由上, 长度为n的数组, 最终会调用mergeSort函数2n-1次.
通过自上而下的递归实现的归并排序, 将存在堆栈溢出的风险.
亲测各浏览器的堆栈溢出所需的递归调用次数大致为:

Chrome v55: 15670

Firefox v50: 44488

Safari v9.1.2: 50755

以下是测试代码:

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

为此, ES6规范中提出了尾调优化的思想:
如果一个函数的最后一步也是一个函数调用,
那么该函数所需要的栈空间将被释放, 它将直接进入到下次调用中,
最终调用栈里只保留最后一次的调用记录.

虽然ES6规范如此诱人, 然而目前并没有浏览器支持尾调优化, 相信在不久的将来,
尾调优化就会得到主流浏览器的支持.

以下是其算法复杂度:

平均时间复杂度最好情况最坏情况空间复杂度OOOO

从效率上看, 归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n,
那么拆分数组共需logn步, 又每步都是一个普通的合并子数组的过程,
时间复杂度为O, 故其综合时间复杂度为O. 另一方面,
归并排序多次递归过程中拆分的子数组需要保存在内存空间, 其空间复杂度为O.

快速排序

快速排序借用了分治的思想, 并且基于冒泡排序做了改进. 它由C. A. R.
Hoare在1962年提出. 它将数组拆分为两个子数组,
其中一个子数组的所有元素都比另一个子数组的元素小,
然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成.

如下是动图效果:

快速排序

如下是算法实现:

function quickSort(array, left, right) { var partitionIndex, left =
typeof left == ‘number’ ? left : 0, right = typeof right == ‘number’ ?
right : array.length-1; if (left < right) { partitionIndex =
partition(array, left, right);//切分的基准值 quickSort(array, left,
partitionIndex-1); quickSort(array, partitionIndex+1, right); } return
array;}function partition(array, left ,right) { //分区操作 for (var i =
left+1, j = left; i <= right; i++) {//j是较小值存储位置的游标
array[i] < array[left] && swap(i, ++j,
array);//以第一个元素为基准 } swap(left, j, array);
//将第一个元素移至中间 return j;}

以下是其算法复杂度:

平均时间复杂度最好情况最坏情况空间复杂度OOOO

快速排序排序效率非常高. 虽然它运行最糟糕时将达到O的时间复杂度, 但通常,
平均来看, 它的时间复杂为O, 比同样为O时间复杂度的归并排序还要快.
快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言,
相对效率更高. 之前在捋一捋JS的数组一文中就提到:
Chrome的v8引擎为了高效排序, 在排序数据超过了10条时, 便会采用快速排序.
对于10条及以下的数据采用的便是插入排序.

Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的,
因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.

堆排序

1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert
W.Floyd) 和威廉姆斯(J.Williams)
在1964年共同发明了著名的堆排序算法(Heap Sort).

堆排序是利用堆这种数据结构所设计的一种排序算法. 它是选择排序的一种.
堆分为大根堆和小根堆. 大根堆要求每个子节点的值都不大于其父节点的值,
即array[childIndex] <= array[parentIndex], 最大的值一定在堆顶.
小根堆与之相反, 即每个子节点的值都不小于其父节点的值,
最小的值一定在堆顶. 因此我们可使用大根堆进行升序排序,
使用小根堆进行降序排序.

并非所有的序列都是堆, 对于序列k1, k2,…kn, 需要满足如下条件才行:

ki <= k 且 ki<=k, 即为小根堆, 将<=换成>=, 那么则是大根堆.
我们可以将这里的堆看作完全二叉树, k 相当于是二叉树的非叶子节点, k
则是左子节点, k是右子节点.

算法的基本思想:

先将初始序列K[1..n]建成一个大根堆, 此堆为初始的无序区.

再将关键字最大的记录K1和无序区的最后一个记录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 { //建立大顶堆 length = array.length; for
(var i = length>>1; 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;

②调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度,
时间复杂度为O;

③堆排序的过程由n次第②步完成, 时间复杂度为O.

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

计数排序

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

使用计数排序需要满足如下条件:

待排序的序列全部为整数

排序需要额外的存储空间

算法的基本思想:

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

初始化游标i为0, 并准备一个缓存数组B, 长度为待排序数组A的最大值+1,
循环一遍待排序数组A, 在缓存数组B中存储A的各个元素出现的次数.

①将B中的当前元素item与0比较, 若大于0, 则往待排序数组A中写入一项A[i] =
item; 然后i++, item—; 然后重复步骤①, 直到item==0,
则进入到B的下一个元素中.

遍历缓存数组B, 即循环执行步骤2.
最终所有有效元素都将依次写回待排序数组A的第1,2,…n项.

如下是动图效果:

计数排序

如下是算法实现:

function countSort(array, max) { var tempLength = max + 1, temp = new
Array(tempLength), index = 0, length = array.length;
//初始化缓存数组各项的值 for (var i = 0; i < length; i++) { if
(!temp[array[i]]) { temp[array[i]] = 0; } temp[array[i]]++;
} //依次取出缓存数组的值,并写入原数组 for (var j = 0; j < tempLength;
j++) { while(temp[j] > 0) { array[index++] = j; temp[j]–; } }
return array;}

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

桶排序

桶排序即所谓的箱排序, 它是将数组分配到有限数量的桶子里.
每个桶里再各自排序(因此有可能使用别的排序算法或以递归方式继续桶排序).
当每个桶里的元素个数趋于一致时, 桶排序只需花费O的时间.
桶排序通过空间换时间的方式提高了效率, 因此它需要额外的存储空间.

算法的基本思想:

桶排序的核心就在于怎么把元素平均分配到每个桶里,
合理的分配将大大提高排序的效率.

如下是算法实现:

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.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;//往不同桶里添加数据 } 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: 基数排序不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

点击链接加入群【javascript学习交流群】:615496236

小结

各种排序性能对比如下:

排序类型平均情况最好情况最坏情况辅助空间稳定性冒泡排序OO稳定选择排序OO不稳定直接插入排序OO稳定折半插入排序OO稳定希尔排序OOO不稳定归并排序OOOO稳定快速排序OOOO不稳定堆排序OOOO不稳定计数排序OOO稳定桶排序OOO稳定基数排序OOOO稳定

注: 桶排序的稳定性取决于桶内排序的稳定性, 因此其稳定性不确定.
基数排序中, k代表关键字的基数, d代表长度, n代表关键字的个数.

愿以此文怀念下我那远去的算法课程.

未完待续…

感谢.
特别感谢不是小羊的肖恩在简书上发布的JS家的排序算法提供的讲解.***

本问就讨论这么多内容,大家有什么问题或好的想法欢迎在下方参与留言和评论.

本文作者:louis

本文链接:JS中可能用得到的全部的排序算法

参考文章

JS家的排序算法 – 简书

白话经典算法系列之三 希尔排序的实现 – MoreWindows Blog – 博客频道 –
CSDN.NET

算法与数据结构 冒泡排序、插入排序、希尔排序、选择排序(Swift3.0版) –
青玉伏案 – 博客园

想学习前端的加一下QQ群点击链接加入群【javascript学习交流群】615496236:

编辑

发表评论

电子邮件地址不会被公开。 必填项已用*标注