有且仅有的10个常见的排序算法，东西不多，怎么就背不下来呢

就这么跟你说吧，面试中肯定会出排序算法的算法题，你只需要背下来代码+背下来他们的时间复杂度和空间复杂度就能蒙混过关。

不管你是前端还是后端，关于排序的算法有且仅有这 10个，如果你用心了，怎么会记不住呢。看完这篇文章你还没记住，就说明你是笨蛋。

好吧，最最坏的情况下，也需要记住这个8【冒泡、选择、插入、希尔、归并、快速、桶、堆】

可以把所有排序分成三类

第一类【冒泡 + 选择 + 插入 + 希尔】重点是使用【循环+交换】【 O(n^2)】

第二类【归并 + 堆排序 】重点是【辅助函数 + 递归】【O(nlogn)】

第三类【快速排序】他自己一组，说明很重要，使用【递归思想】【O(nlogn)】

第三类【计数 + 桶 + 基数】重点是使用【额外空间桶】【O(n+k)】

一、循环+交换

1.1 冒泡排序

这个是你必须会的，我记得之前最先学的就是这个算法，因为他最简单，但是因为他的时间复杂度大，所以考的概率确实最小的，但是你怎么可以不会这么简单的排序呢？

冒泡排序分为三个，一个是基本的冒泡排序，二个改进的冒泡排序，我建议是至少记住一个基本的一个改进的。冒泡排序的时间复杂度都是 o（n^2）

改进的冒泡排序你一定要学会，因为如果你在面试中答了简单的冒泡排序，面试官一定会问你，有没有什么地方可以优化？如果你一步到位写出改进的冒泡排序说不定人家就放过你了。

1.1.1 基本的冒泡排序

记住一个关键字【双层 for 循环】

1. 外层 for 循环 i < len
2. 内层 for 循环 j 初始化为 0，j < len - i - 1
3. 使用内层 for 循环交换元素
4. 时间复杂度是 n^2， 因为有两层 for 循环
5. 注意是升序排序，还是降序排序

function bubbleSort(arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));

1.1.2 改进的冒泡排序

记住关键子【while 循环 + for 循环 + pos 位置信息】

1. 设置一个位置信息 pos 记录每趟排序中最后一次进行交换的位置
2. pos 初始化为0 ，在 while 循环内初始化，每次循环都重置
3. pos 位置之后的记录均已经交换到位
4. 在交换的时候 if 语句内更新 pos
5. 内层 for 循环 j < i 
6. 在下一趟排序时，只需要扫描到 pos 位置即可【说明 posm是用来改变循环终止位置的】
7. 注意 while 循环一定要有更改 while 循环条件的语句，这里就使用 pos
8.  时间复杂度还是为O(N^2)

function bubbleSort(arr) {
    let i = arr.length - 1
    while (i > 0) {
        let pos = 0
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 记录位置
                pos = j
                let temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            }
        }
        // 更改 while 循环条件
        i = pos
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));

1.1.3 终极版的冒泡排序

关键值【while 循环和2个for循环 +下标 最大值和最小值】

1. 这个是在 1.2 的基础上再进行优化的
2. 关键是使用最大值和最小值的概念【这里是指的下标的最大最小值】
3. 正向冒泡，找到最大值
4. 反向冒泡， 找到最小值
5. 2个 for 循环，不是双层 for 循环
6. while 循环条件是 low < high 所以内部有high-- low ++的语句
7. 要定义四个变量
8. 排序趟数几乎减少了一半

function bubbleSort(arr) {
    let low = 0;
    let high = arr.length - 1
    let temp, j
    while (low < high) {
        // 注意这个是 j + 1 和 j 的交换
        for (j = low; j < high; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            }
        }
        high--
        // 这个 for 循环是 j - 1 和 j的交换
        for (j = high; j > low; j--) {
            if (arr[j - 1] > arr[j]) {
                temp = arr[j - 1]
                arr[j - 1] = arr[j]
                arr[j] = temp
            }
        }
        low++
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(bubbleSort(arr));

1.2 选择排序

重点【双层 for 循环】

1. 找到数据结构中的最小值，并把放在第一位。
2. 选择排序的时间复杂度也是O(n^2)
3. 也是使用 双层的for循环
4. 外层 for 循环交换当前值和 最小值，外层循环小于 len - 1,因为内层循环初始化为i+1
5. 内层 for 循环用来寻找最小值【j = i + 1】
6. 使用 minIndex 存最小值的下标，初始化为 i

function selectSort(arr) {
    let len = arr.length
    let temp, minIndex
    for (let i = 0; i < len - 1; i++) {
        minIndex = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(selectSort(arr));

1.3 插入排序

这个插入排序也一定要会

重点【外层 for + 内层 while 】

1. 时间复杂度依旧为 O(n^2)
2. 外层使用 for 循环，初始化 i = 1【这就意味着使用j-1】
3. 内层使用 while 循环 j = i
4. 关键是 while 循环的条件
   1. 比较放在 while 循环的条件中 arr[j-1] > arr[i]
   2. 使用的是 j - 1, j--
5. 交换发生在 for 循环中
6. 适用于排小数组

function insertSort(arr) {
    let len = arr.length
    let temp
    for (let i = 1; i < len; i++) {
        temp = arr[i]
        let j = i
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1]
            j--
        }
        arr[j] = temp
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(insertSort(arr));

1.4 希尔排序

希尔排序可以说是特殊的插入排序

重点是有一个【间隔 + while 循环 + for 循环  + while 循环】

1. gap 初始化为 len /2，更新 gap = gap /2
2. while 循环条件是 gap > 0
3. 在插入排序的基础上外面加了一个 gap 的while循环
4. gap 是for 循环的初始值【普通插入排序是1】
5. 插入排序的 j-1 变成 j -gap
6. 大幅减少数据移动的次数

function shellSort(arr) {
    let len = arr.length
    let gap = Math.floor(len / 2)
    while (gap > 0) {
        for (let i = gap; i < len; i++) {
            const temp = arr[i]
            let j = i
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap = Math.floor(gap / 2)
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log('希尔排序', shellSort(arr));

二、辅助函数+递归

2.1 归并排序

重点【两个函数 + 递归】

1. 时间复杂度是O(nlogn)
2. 将整个数组分为两个数组
3. 对两个数组分别使用递归，调用两次
4. 写一个辅助函数
5. 第二个函数类似合并两个有序数组【使用双指针】
6. 最后调用辅助函数

function merge(left, right) {
    let res = []
    let i = 0, j = 0
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            res.push(left[i])
            i++
        }
        else {
            res.push(right[j])
            j++
        }
    }
    if (i < left.length) {
        res = res.concat(left.slice(i))
    }
    if (j < right.length) {
        res = res.concat(right.slice(j))
    }
    return res
}
function mergeSort(arr) {
    let len = arr.length
    if (len < 2) {
        return arr
    }
    let middle = Math.floor(len / 2)
    let left = arr.slice(0, middle)
    let right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right))
}
var arr = [1, 10, 8, 2, 30];
console.log(mergeSort(arr));

2.2 堆排序

重点是【3个函数+递归】

在堆排序算法中，最大堆是一种二叉堆，具有以下性质：

1. 堆序性质（Heap Property）：对于最大堆中的任意节点 i，其父节点 parent(i) 的键值要大于或等于节点 i 的键值。换句话说，最大堆中的每个节点都大于或等于其子节点。

2. 完全二叉树性质（Complete Binary Tree Property）：最大堆是一种完全二叉树，除了最底层之外，每一层都是满的，而且最底层的节点都尽可能地靠左排列。

这两个性质确保了最大堆的结构和顺序特性。在最大堆中，根节点存储着最大的元素，每个父节点的键值都大于或等于其子节点的键值。因此，堆排序算法可以利用最大堆的特性，实现对数组的原地排序。

1. 总共需要3个函数，其中两个辅助函数，一个构建最大堆，一个调整堆
2. 每个函数都需要调用调整堆的函数 heapify
3. heapify 递归调用自身
4. 两个 for 循环都是递减的
5. 堆的性质：在一个最大堆（或最小堆）中，堆顶元素总是数组中最大（或最小）的元素
6. 时间复杂度是O(n log n)

function heapSort(arr) {
    // 构建最大堆
    buildMaxHeap(arr);
    // 从最后一个非叶子节点开始向上调整堆
    for (let i = arr.length - 1; i > 0; i--) {
        // 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换
        [arr[0], arr[i]] = [arr[i], arr[0]];
        
        // 调整堆，使其满足最大堆性质
        heapify(arr, 0, i);
    }
    return arr;
}
// 构建最大堆
function buildMaxHeap(arr) {
    const len = arr.length;
    // 从最后一个非叶子节点开始向上调整堆
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(arr, i, len);
    }
}
// 调整堆
function heapify(arr, i, len) {
    let largest = i; // 当前节点
    const left = 2 * i + 1; // 左子节点
    const right = 2 * i + 2; // 右子节点
    // 如果左子节点比当前节点大，则更新最大值索引
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点比当前节点大，则更新最大值索引
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大值索引不是当前节点，则交换节点，并递归调整堆
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, largest, len);
    }
}
var arr = [1, 10, 8, 2, 30];
console.log('堆-排序', heapSort(arr));

三、快速排序

快速排序是一定一定会考的，频率最高的算法，就算被也要背下来，你看他的名字里面有快速两个字，就说明他的重要性。

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

关键字【分治法 + 递归】

1. 时间复杂度为 O(nlogn)
2. 有一个基准，每次递归只初始化一次基准，不会手动修改
3. 有一个小于基准的数组
4. 一个大于基准的数组
5. 有一个 for 循环，有一个 continue 语句
6. 在函数返回的地方，使用递归

function quickSort(arr) {
    if (arr.length <=1) {
        return arr
    }
    let baseIndex = Math.floor(arr.length / 2)
    let base = arr[baseIndex]
    let less = []
    let greater = []
    for(let i =0; i < arr.length; i ++) {
        if (i === baseIndex) {
            continue
        }
        if(arr[i] < base) {
            less.push(arr[i])
        } else {
            greater.push(arr[i])
        }
    }
    return [...quickSort(less), base, ...quickSort(greater)]
}
var arr = [1, 10, 8, 2, 30];
console.log(quickSort(arr));

四、额外桶空间

4.1 计数排序

分布式排序，使用一个用来存储每个元素在原始数组中出现次数的临时数组，在所有元素都计数完成后，临时数组已排好序,并可以带以构建排序后的结果数组

重点【找到最大值和最小值+一个计数数组】

1. 时间复杂度是O(o+k)，k是临时计数数组的大小
2. 找出数组中的最大值最小值
3. 计算每个元素的出现次数 arr[i] -min 
4. 计数数组，重建排序后的数组
5. 适用于整数数组的排序

function countSort(arr) {
    // 找出最大值和最小值
    let min = max = arr[0]
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i]
        }
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    // 由于是计数排序适用于整数数组，所以这样初始化数组
    const countArr = new Array(max - min + 1).fill(0)
    
    for (let i = 0; i < arr.length; i++) {
        countArr[arr[i] - min]++ // 用数组下标对应一个元素
    }
    // 结果数组的 index
    let sortedIndex = 0
    for (let i = 0; i < countArr.length; i++) {
        while (countArr[i] > 0) {
            // 因为计数数组中减去了 min
            // 所以这里面要使用循环的下标 i 加上 最小值 min
            arr[sortedIndex] = i + min
            sortedIndex++
            countArr[i]--
        }
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(countSort(arr));

4.2 桶排序

也是分布式排序，重点是【分桶+插入排序】

1. 和计数排序一样，先找到最大值和最小值
   1. 最大最小值，用于计算桶的个数
   2. 最小值，还用于把元素加入桶
2. 有两个函数
3. 第一个个函数将元素分成不同的桶
   1. 有两个参数，第二个参数是桶的大小
4. 将元素插入桶，重点是计算bucketIndex = (arr[i]-min )/ bucketSize
5. 第二个函数对桶进行排序，使用插入排序，因为插入排序用来排小数组不错
6. 时间复杂度 O(n+k)

function bucketSort(arr, bucketSize = 5) {
    if (arr.length ===0) {
        return arr
    }
    let min = arr[0]
    let max = arr[0]
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] < min) {
            min = arr[i]
        }
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    const bucketCount = Math.floor((max- min)/bucketSize ) + 1
    const bucketArr = Array.from({length: bucketCount}, () => [])
    for(let i =0; i < arr.length; i++) {
        let bucketIndex = Math.floor((arr[i] - min) / bucketSize)
        bucketArr[bucketIndex].push(arr[i])
    }
    
    let sortedArr = []
    for(let i = 0; i < bucketArr.length; i ++) {
        insertSort(bucketArr[i])
        sortedArr.push(...bucketArr[i])
    }
    return sortedArr
}
var arr = [1, 10, 8, 2, 30];
console.log(bucketSort(arr));

4.3 基数排序

重点是【获取最大数的位数+桶的个数时基数的大小】

1. 需要获取数组中的最大值
2. 桶的个数时基数的大小，通常是10进制就是10
3. 使用一个辅助函数获取指定位置上的数字
4. 时间复杂度是 O(n*k)

function radixSort(arr) {
    let maxNum = Math.max(...arr)
    let maxLen = `${maxNum}`.length
    // 通常创建桶的数量是基数的大小
    // Array.from 的第二个参数时map函数依次迭代
    let buckets = Array.from({ length: 10 }, () => [])
    // 获取数字num的指定位数上的数字
    const getDigit = (num, digit) => {
        // Math.pow返回基数得幂
        return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10
    }
    for (let i = 0; i < maxLen; i++) {
        for (let j = 0; j < arr.length; j++) {
            let digit = getDigit(arr[j], i)
            buckets[digit].push(arr[j])
        }
        arr = [].concat(...buckets)
        for (let j = 0; j < 10; j++) {
            buckets[j] = []
        }
    }
    return arr
}
var arr = [1, 10, 8, 2, 30];
console.log(radixSort(arr));