1. 冒泡排序

冒泡排序是最简单的排序方法，原理就是从后往前遍历，在遍历一次的过程中，如果后面的数比前面的数小，就将小的数放到前面，因此遍历一次就能将当前最小的数冒泡到最前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bubbleSort (arr){
    let flag=false;
    for(let i=0;i<arr.length;i++){
        flag=false;
        for(let j=arr.length-1;j>i;j--){
            if(arr[j]<arr[j-1]){
                let tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
                flag=true;
            }
        }
        // 如果flag在某次循环中没有更改，则说明已经有序
        if(flag===false){
            break;
        }
    }
    console.log(arr);
}

冒泡排序的平均时间是O(n^2)，最坏情况是O(n^2)，即发生在要排序的数组是逆序情况下，最好情况是O(n)，即发生在元素本来有序的情况下。
冒泡排序的稳定性因为每次比较后如果两个相邻元素相等我们并不会将他们交换，所以冒泡不会改变相同元素的下标，所以冒泡排序是一个稳定的排序。
冒泡排序适用于数据量较小的场景下。

2. 插入排序

  1. 直接插入排序
    插入排序，对于一个数组，我们从第二个数字开始，将其认为是新增加的数字，这样第二个数字只需与其左边的第一个数字比较后排好序；在第三个数字，认为前两个已经排好序的数字为手里整理好的牌，那么只需将第三个数字与前两个数字比较即可；以此类推，直到最后一个数字与前面的所有数字比较结束，插入排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
function insertSort(arr){
    for(let j=1;j<arr.length;j++){
        let key=arr[j];
        let i=j-1
        while(i>=0 && key<arr[i]){
            arr[i+1]=arr[i]
            i--;
        }
        arr[i+1] = key;
    }
    console.log(arr);
}

插入排序的平均时间是O(n^2)，最坏情况是O(n^2)，即发生在要排序的数组是逆序情况下，最好情况是O(n)，即发生在元素本来有序的情况下。也是稳定排序。
适用场景是数据量小时使用。并且大部分已经被排序。

  1. 希尔排序
    https://www.cnblogs.com/chengxiao/p/6104371.html
    希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2)的第一批算法之一。
    希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
    我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。
    具体例子参见链接。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function shellSort(arr){
        for(let gap = Math.floor(arr.length/2); gap >=1; gap = Math.floor(gap/2)) {
            for(let i = gap; i < arr.length; i++) {
                let j=i-gap;
                let key = arr[i]; 
                while(j>=0&&key<arr[j]){
                    arr[j+gap] = arr[j];
                    j = j - gap;
                }
                arr[j+gap] = key;
            }
        }
        return arr;
    }

3. 选择排序

  1. 简单选择排序
    在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectSort(arr){
    for(let i=0;i<arr.length-1;i++){
        let min = i;
        for(let j=i+1;j<arr.length;j++){
            if(arr[j]<arr[min]){
                min = j;
            }
        }
        swap(arr,i,min);
    }
    return arr;
}
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
  1. 堆排序
    https://www.cnblogs.com/MOBIN/p/5374217.html
    堆排序是一种树形选择排序，在排序过程中可以把元素看成是一颗完全二叉树，每个节点都大（小）于它的两个子节点，当每个节点都大于等于它的两个子节点时，就称为大顶堆，也叫堆有序； 当每个节点都小于等于它的两个子节点时，就称为小顶堆。

算法思想(以大顶堆为例)：
1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
2.将根节点与尾节点交换并输出此时的尾节点
3.将剩余的n -1个节点重新进行堆有序化
4.重复步骤2，步骤3直至构造成一个有序序列
具体的步骤参见链接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function heapSort(arr){
    let result=[];
    let len = arr.length -1;
    //构造一个大顶堆，树的根节点是数组中的0~Math.floor(arr.length/2)-1位，所以从下到上对每一个根节点进行一个堆有序化的操作
    for(let i=Math.floor(arr.length/2)-1;i>=0;i--){
        adjustHeap(arr, i, len);
    }
    //将第一个节点与最后一个点交换，这样最大的节点就到了最后一位，然后前面的n-1个节点重新进行堆有序化，继续得到一个大顶堆，然后再重复操作。
    while(len>=0){
        swap(arr, 0, len--);
        adjustHeap(arr, 0, len);
    }
    return arr;
}

function adjustHeap(arr, i, length){
    let j;
    while(2*i+1 <= length){
        j = 2*i+1;
        if (arr[2*i+1] > arr[i]) {
            if(2*i+2 <= length && arr[2*i+1] < arr[2*i+2]) {
                j++;
                swap(arr, i, 2*i+2);
            }else{
                swap(arr, i, 2*i+1);
            }
        } else {
            if(2*i+2 <= length && arr[i] < arr[2*i+2]) {
                j++
                swap(arr, i, 2*i+2);
            }else{
                break;
            }
        }
        i = j;
    }
}
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

4. 归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之）。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
　　再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function main(arr){
    split(arr, 0, arr.length-1);
    console.log(arr);
}
function split(arr, start, end){
    if(start<end){
        let mid=Math.floor((start+end)/2);
        split(arr, start, mid);
        split(arr, mid+1, end);
        merge(arr, start, mid, end);
    }
}
function merge(arr, start, mid, end) {
    let i = start;
    let k = mid + 1;
    let t=0;
    let tmp = [];
    while(i<=mid && k<=end){
        if(arr[i]<=arr[k]){
            tmp.push(arr[i++]);
        }else{
            tmp.push(arr[k++]);
        }
    }
    tmp = (i<=mid) ? tmp.concat(arr.slice(i)) : tmp.concat(arr.slice(k));
    while(start<=end){
        arr[start++] = tmp[t++];
    }
}

归并排序的时间复杂度是O(N*logN)，是稳定排序，适用于需要稳定，空间不是很重要的情况下，并且n较大的情况