前言

本文整理了常用的十大经典排序算法，如果对答案有不一样见解的同学欢迎评论区补充讨论，当然有问题，也欢迎在评论区指出。

该篇文章基本引用于菜鸟教程，笔者只是做了一个简化版，以作记录

1.1 冒泡排序

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

2. 动图演示

3. JavaScript 代码实现

function bubbleSort(arr) {
    const len = arr.length;
    for(let i=0;i<len-1;i++){
        for(let j=0;j<len-i;j++){
            if(arr[j-1]>arr[j]){// 相邻元素两两对比
                [arr[j-1],arr[j]] = [arr[j],arr[j-1]];// 元素交换
            }
        }
    }
    return arr;
}
console.log(bubbleSort([4,2,5,6,7,2,3,41,3,2]))
复制代码

1.2 选择排序

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

2. 动图演示

3. JavaScript 代码实现

function selectionSort(arr) {
    const len = arr.length;
    for(let i=0;i<len;i++){
        let minIndex = i;
        for(let j=i+1;j<len;j++){
            if(arr[minIndex]>arr[j]){// 寻找最小的数
                minIndex = j;// 将最小数的索引保存
            }
        }
        [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]];//每轮只用交换一次
    }
    return arr;
}
console.log(selectionSort([23,4,1,2,5,2,5,6,7,4]))
复制代码

1.3 插入排序

1. 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2. 动图演示

3. JavaScript代码实现

function insertionSort(arr) {
    const len = arr.length;
    for(let i=1;i<len;i++){
        let index = i;
        const current = arr[i];
        while (current<arr[index-1]&&index>=0){
            arr[index]=arr[index-1];
            index--;
        }
        arr[index]=current;
    }
    return arr
}
console.log(insertionSort([23,4,1,2,5,2,5,6,7,4]))
复制代码

1.4 希尔排序

1. 算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2. JavaScript

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}
复制代码

1.5 归并排序

function mergeSort(arr) {  // 采用自上而下的递归方法
    const len = arr.length;
    if(len<2) return arr;
    const mid = Math.floor(len/2);
    const leftArr = arr.slice(0,mid);
    const rightArr = arr.slice(mid);
    return merge(mergeSort(leftArr),mergeSort(rightArr));
}

function merge(left, right) {
    const res = [];
    while (left.length&&right.length){
        if(left[0]<right[0]){
            res.push(left.shift());
        }else{
            res.push(right.shift());
        }
    }
    while (left.length){
        res.push(left.shift());
    }
    while (right.length){
        res.push(right.shift());
    }
    return res;
}
console.log(mergeSort([23,4,1,2,5,2,5,6,7,4]))
复制代码

1.6 快速排序

1. 算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

2. 动图演示

3. JavaScript

function quickSort(arr, left, right) {
    const len = arr.length;
    left = typeof left != 'number' ? 0 : left;
    right = typeof right != 'number' ? len - 1 : right;
    if(left<right){
        const partitionIndex = partition(arr,left,right);
        quickSort(arr,left,partitionIndex-1);
        quickSort(arr,partitionIndex+1,right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    const pivot = left;
    let index = left+1;
    for(let i=index;i<=right;i++){
        if(arr[pivot]>arr[i]){
            [arr[index],arr[i]]=[arr[i],arr[index]];
            index++;
        }
    }
    [arr[pivot],arr[index-1]] = [arr[index-1],arr[pivot]];
    return index-1
}
console.log(quickSort([23,4,1,2,5,2,5,6,7,4]))
复制代码

1.7 堆排序

1. 算法步骤

创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

2. 动图演示

3. JavaScript

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function heapSort(arr) {
    buildMaxHeap(arr);
    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}
复制代码

1.8 计数排序

1. 算法步骤

找出待排序的数组中最大和最小的元素 (0)
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

2. 动图演示

3. JavaScript

function countingSort(arr, maxValue) {
    const res = [];
    const container = new Array(maxValue+1).fill(0);
    //将所有数据存放在容器里
    for(let i=0;i<arr.length;i++){
        container[arr[i]]++;
    }
    for(let j=0;j<=maxValue;j++){
        while (container[j]>0){
            res.push(j);
            container[j]--;
        }
    }
    return res;
}
console.log(countingSort([23,4,1,2,5,2,5,6,7,4],23))
复制代码