经典排序算法

名词解释

时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小
稳定：元素间相对位置固定，即：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
不稳定：元素间相对位置不固定，即：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行

排序方法归纳

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	In-place	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	In-place	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	In-place	稳定
希尔排序	O(n ㏒ n)	O(n ㏒² n)	O(n ㏒² n)	O(1)	In-place	不稳定
归并排序	O(n ㏒ n)	O(n ㏒ n)	O(n ㏒ n)	O(n)	Out-place	稳定
快速排序	O(n ㏒ n)	O(n ㏒ n)	O(n²)	O(㏒ n)	In-place	不稳定
堆排序	O(n ㏒ n)	O(n ㏒ n)	O(n ㏒ n)	O(1)	In-place	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-place	稳定
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	Out-place	稳定
基数排序	O(n*k)	O(n+k)	O(n*k)	O(n+k)	Out-place	稳定

排序方法介绍

1.冒泡排序√

从字面上能理解， “冒泡”即小值的浮上来，大值沉下去。

基本思路

第一步比较相邻的元素大小。如果第一个比第二个大，就交换两个元素位置
之后对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
针对除了最后一位的所有元素重复以上的步骤
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

代码

let bubbleSort = function (arr) {
    for (let i = 0; i < arr.length-1; i++) {
        for (let j = len; j > i; j--) {
            if (arr[j] < arr[i]) {
                let temp = arr[i];
                    arr[i] =  arr[j]
                    arr[j] =  temp
            }
        }
    }
    return arr
}

2.选择排序法√

选择排序是从冒泡排序演化而来，每一轮比较得出最小值，然后依次和每轮“无序区”中参与比较的第一个值进行交换。

基本思路

初始时在序列中找到最小元素
放到序列的起始位置作为已排序序列
然后再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾
以此类推，直到所有元素均排序完毕

代码

var selectSort = function(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var min = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    if (i != min) {
      swap(arr, i, min);
    }
    console.log(i + 1, ": " + arr);
  }
  return arr;
};

// 元素交换函数
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
};

3.插入排序√

插入排序是基于互相比较的排序。所谓的“比较”，就是通过比较数组中的元素，看谁大谁小，根据结果对应调整元素的位置。

基本思路

初始时先默认将第一个元素标记为已排序
然后提取第一个没有排序过的元素，找出插入提取元素的地方并和已经排序过的元素进行比较。
比较大小若条件成立，则将已排序过的元素往右移1个单位，如果条件不成立，则在现有位置直接插入。
以此类推，直到所有元素均排序完毕

代码

let arr = [4, 3, 1, 2, 6, 7, 8, 9, 5, 11, 21, 13]
var insertSort = function (arr) {
    var len = arr.length,
        key;
    for (var i = 1; i < len; i++) {
        var j = i;
        key = arr[j];  // 1:key = 3  2:key = 1
        while (--j > -1) {
            if (arr[j] > key) {
                arr[j + 1] = arr[j];	// arr[0] = 4 arr[1]=4 key =3
            } else {
                break;
            }
        }
        arr[j + 1] = key;	// arr[0] = 3  arr[1]=4   key=3
    }
    return arr;
};

4.快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

5.归并排序

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

6.希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

7.堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

8.计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

9.桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序

10.基数排序

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

引用参考：

十大经典排序算法最强总结