几种常见的排序算法总结（JavaScript 描述）

港控/mmm° 2022-05-25 01:54 244阅读 0赞

本文讨论：冒泡排序、插入排序、希尔排序、简单搜索排序、快速排序、归并排序、堆排序。

# 冒泡排序 #

## 介绍 ##

冒泡排序比较任何两个相邻的项。如果前一个比后一个大，就交换它们。元素向上移动至正确的位置，看上去就像水中上升的气泡一样。

## 代码 ##

### 注意点 ###

*  设定无序序列在左边，有序序列在右边。
 *  最开始，全是无序序列（0 到 length-1）。冒泡排序过程，就是右边的有序序列从无到有一路左扩的过程。
 *  外层循环的`i` 标识**有序序列**的长度变化，即从最右 `arr[arr.length - 1]` 到最左`arr[1]` 的过程。
 *  内层循环的`j`是每次遍历**无序序列**的指针，比较`arr[j-1]`是否比 `arr[j]`大。是则把更大的右移。
 *  引入变量 `flag` 减少无用的循环。然并卵，和其他比依然慢。

### 时间复杂度 ###

*  **O(n²)** 
 *  最好情况： 本身正序 O(n)
 *  最差情况： 本身反序 O(n²)

### 空间复杂度 ###

冒泡排序算法的额外空间只有一个 `t` ,故而

*  O(1)

### 示意图 ###

![冒泡排序][28749710-5213c280-7503-11e7-977e-7c0616e3b582.gif]

--------------------

# 简单选择排序 #

### 介绍 ###

简单选择排序是一种原址比较排序算法。  
其思路是：找到数据结构中的最小值，并把它放到第一位。接着找到第二小的值，并放到第二位 … … 以此类推。

即，从无序序列中找出**最小的**，把它与当前无序序列中**最左端**的交换

### 代码 ###

### 注意点 ###

*  刚开始认为全是无序，有序序列从左向右扩张。
 *  外层循环：遍历无序序列中每一个，每次都假设当前第 1 个（即 `i`）就是 `minIndex`。
 *  内层循环：从无序序列中找出最小的。**第一个**先是和第二个比，再是和第三个第四个…，故 `j=i+1`
 *  当发现 `j` 指向的比 `minIndex` 更小，`minIndex` 保存 这个 `j` 。目的是：用 `minIndex` 保存无序序列中最小值的下标。
 *  无序序列中找出最小的之后，就**它与当前无序序列中最左端的交换**。由此，无序序列长度减一，有序序列长度加一。

### 时间复杂度 ###

*  **O(n²)** 
 *  最好情况： **O(n²)** 
 *  最差情况： **O(n²)** 
 *  嗯 … 慢得很稳定

### 空间复杂度 ###

简单选择排序算法的额外空间只有一个 `t` ,故而

*  O(1)

### 示意图 ###

![简单选择排序][28749720-90304278-7503-11e7-9bc8-e3b56539d8bf.gif]

--------------------

# 直接插入排序 #

### 介绍 ###

假设第一项已经排序，从第二项开始，一一与有序序列进行比对，确定其插入位置。

### 代码 ###

### 注意点 ###

*  最开始，默认第一个为红色有序，其余为蓝色无序。插入排序的过程，就是右侧蓝色无序序列渐渐减减少，元素一个个插入左侧红色有序序列中的过程。
 *  外层 `for` 循环：遍历无序序列，故从 `arr[1]` 至 `arr[len-1]`;每次先把该值保存到 t
 *  内层 `while` ：把 `arr[i]` 与 左边红色有序序列 中的每一项进行对比，从右到左。 故 `j = i-1`  
    \*`j` 指针不断前移，寻找更比 `t` 小的值。
 *  当未找到时，即前值 `arr[j]` 覆盖后值 `arr[j+1]`，使得空位前移  
    
    
     *  空位是指该值已经赋给别的变量，此处可以被覆盖的位置
 *  当找到，用 `t` 填 `arr[j+1]` 且不再移动指针 `j`

### 时间复杂度 ###

*  **O(n²)** 
 *  最好情况： 初始序列有序 O(n)
 *  最差情况： 初始序列逆序 O(n²)

### 空间复杂度 ###

直接插入排序算法的额外空间只有一个 `t` ,故而

*  O(1)

### 示意图 ###

![插入排序][28749729-ca072084-7503-11e7-881c-92aa915ce369.gif]

--------------------

# 希尔排序 #

### 介绍 ###

希尔排序又叫**缩小增量排序**，是优化后的插入排序。  
插入排序最耗时的部分就是元素的移动。初始序列越有序，元素移动越少，耗时也就越少。  
希尔排序引入了**增量**的规则，将待排序列分为若干子序列，再分别对子序列进行直接插入排序。通过这种方法，显著减少了元素移动，将算法的时间复杂度优化到 O(nlog2 n)。

### 代码 ###

### 注意点 ###

*  和直接插入排序相比，多加的一层循环用来设置 `gap` 。  
    
    
     *  初始值一般数组长度/2 向下（上）取整；每次减半；直到为 1.
     *  这就是它叫“缩小增量排序”的原因。
 *  中层（原插排第一层循环）：`i = gap`。从本轮的增量值开始，一一进行比对。  
    
    
     *  直接插入排序相当于 `gap = 1`
 *  内层：作用同直接插入排序

### 时间复杂度 ###

*  **O(nlog2 n)**

### 空间复杂度 ###

同直接插入排序算法

*  O(1)

--------------------

# 二路归并排序 #

### 介绍 ###

归并排序是一种分治算法。  
其思想：

*  将 原始数组 **切分**成较小的数组，直到每个小数组只有 一个位置 ；
 *  接着将 小数组 **归并** 成较大的数组，直到最后只有一个排序完毕的大数组。

### 代码 ###

// 归并排序： 先切分 再合并
    function mergeSort(arr) {  
        let len = arr.length;
        let mid = Math.floor(len / 2); // 找中间位置
    
        if (len < 2) { // 终止递归的条件
            return arr;
        }
        let left = arr.slice(0, mid); // 切分数组为左右两段
        let right = arr.slice(mid);
    
        left = mergeSort(left); // 对左右两段分别递归执行归并排序
        right = mergeSort(right);
    
        return merge(left, right); // 最后 合并小数组直到成为一个大数组
    }
    
    // merge 函数作用：对小数组进行 合并 与 排序，来产生大数组，直到回到原始数组并已排序完成
    function merge(left, right) { 
        let result = [];
    
        while (left.length > 0 && right.length > 0) {
            // 当 左右数组 都还有，就比较二者，将较小的推入结果数组
            // 如果推入较大的，就是从大到小的排序
            result.push(left[0] < right[0] ? left.shift() : right.shift()); // 之所以比较各自第 0 项，是因为 shift ; shift 等方法的参数与返回值
        }
        // 二者比较完，把剩下的数组推入结果数组
        while (left.length) result.push(left.shift());
        while (right.length) result.push(right.shift());
    
        return result;
    }

### 时间复杂度 ###

*  **O(nlog2 n)**
 *  最快 **O(nlog2 n)**
 *  最慢 **O(nlog2 n)**

### 空间复杂度 ###

归并排序需要转存整个待排序列，故而

*  O(n)

### 示意图 ###

![归并排序][28749732-1793eecc-7504-11e7-9b59-cfd1e9812aa0.gif]

--------------------

# 快速排序 #

### 介绍 ###

快速排序可能是最常用的排序算法。  
同归并排序一样，快速排序也使用了分治的方法，将原始数组分为较小的数组。  
就平均时间而言，快速排序是所有排序算法中性能最好的。

### 代码 ###

### 注意点 ###

*  参数 low high
 *  `[if]` 只有当 low < high 才执行，否则返回。算是结束递归执行的条件  
    
    
     *  当执行，先选定一个基准值 保存到 t
     *  `[while]` 仅在 i < j 时进行**指针相向运动**操作  
        
        
         *  `[while]` 右指针 j 左移，直到找到比基准值 t 更小的 `[if]` 就把它赋值给左指针 i 指向的值，并右移左指针
         *  `[while]` 左指针 i 右移，直到找到比基准值 t 更大的 `[if]` 就把它赋值给右指针 j 指向的值，并左移右指针
     *  当 i, j **指针相遇**，即找到了基准位置，用 t 赋值；并对左右两端进行递归操作

### 时间复杂度 ###

待排序列越接近无序，快排算法效率越高；  
待排序列越接近有序，快排算法效率越低。

*  **O(nlog2 n)**
 *  最好情况 **O(nlog2 n)**
 *  最坏情况 **O(n²)**

### 空间复杂度 ###

快速排序是递归进行的，递归需要栈的辅助，因此它需要的辅助空间较多。

*  O(log2 n)

### 示意图 ###

![快速排序][28749748-817fea84-7504-11e7-802f-841e7689e7bf.gif]

--------------------

# 堆排序 #

### 介绍 ###

堆是一种数据结构，可以把堆看成一颗完全二叉树。  
这颗完全二叉树满足：任何一个 非叶节点 的值都不小于（大于）其左右孩子节点的值。  
若父亲大孩子小，称为**大顶堆**；反之则称为**小顶堆**。

**堆排序的思想：**  
根据堆的定义，代表这颗完全二叉树的根节点的值是最大（小）的，因此将一个无序序列调整为一个堆，就可以找出这个序列的最大（小）值，然后将找出的这个值交换到序列的最后（前）。  
这样，有序序列元素增加一个，无序序列元素减少一个。对新的无序序列重复操作，就实现了排序。

堆排序中最关键的操作是将序列调整为堆。整个排序过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树的过程。

先建堆，再排序。

这是可以使用的规律：  
![堆][70]

### 代码 ###

let len;    // 全局变量
    
    function buildMaxHeap(arr) {    // 建立大顶堆
        len = arr.length;
        for (let i = Math.floor(len/2); i >= 0; i--) {
            heapify(arr, i);
        }
    }
    
    function heapify(arr, i) {      // 堆调整
        let 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) { 
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function heapSort(arr) { 
        buildMaxHeap(arr);
    
        for (let i = arr.length-1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

### 时间复杂度 ###

*  O(nlog2 n)

--------------------

注：  
部分图片引用自 github.com/Wscats/CV/issues/14

[28749710-5213c280-7503-11e7-977e-7c0616e3b582.gif]: /images/20220525/7c04c931ebb54202aa6b936b611677f4.png
[28749720-90304278-7503-11e7-9bc8-e3b56539d8bf.gif]: /images/20220525/0300c33ba34b40a489b179fb6e5d14ee.png
[28749729-ca072084-7503-11e7-881c-92aa915ce369.gif]: /images/20220525/8e38513002774b78a56b8339ad2a5c51.png
[28749732-1793eecc-7504-11e7-9b59-cfd1e9812aa0.gif]: /images/20220525/a0dde149b9524b6d81d77b5e67a4ade0.png
[28749748-817fea84-7504-11e7-802f-841e7689e7bf.gif]: /images/20220525/edc1df89449e427c9eb073886626282c.png
[70]: /images/20220525/1c4bf0c8bf9c46ccade4dea17af45fa0.png