[数据结构与算法]排序算法汇总(JavaScript版)

绝地灬酷狼 2022-12-06 12:39 194阅读 0赞

## JavaScript所有排序算法汇总 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center]

### 一、冒泡排序 ###

Array.prototype.bubbleSort = function () { 
                for (let i = 0; i < this.length - 1; i++) { 
                    let flag = 0 /* 用于记录一趟冒泡是否发生交换 */
                    for (let j = 0; j < this.length - 1 - i; j++) {  /* 一趟冒泡 */                     
                        if (this[j] > this[j + 1]) { 
                            const temp = this[j]
                            this[j] = this[j + 1]
                            this[j + 1] = temp
                            flag = 1 /* 发生了交换 */
                        }
                    }
                    if (flag === 0) break /* 如果一趟冒泡全程无交换，则说明排序已完成，break跳出循环 */
                }
                return this
            }
            const arr = [2, 1, 5, 3, 4]
            console.log(arr.bubbleSort()) // [1, 2, 3, 4, 5]

**稳定性：稳定**  
**时间复杂度：O(N^2)** 两层嵌套循环

最好情况：数组本来就有序，第一次冒泡就没有发生交换，flag===0，break，进行了一次循环O(n)  
最坏情况：数组完全逆序，O(N^2)

### 二、插入排序 ###

Array.prototype.insertionSort = function () { 
                for (let i = 1; i < this.length; i++) {  /* 从第二张开始 */
                    const temp = this[i] /* 抽出一张牌,此时产生了一个空位 */
                    let j = i
                    while (j > 0) {  /* 往前比较 */
                        if (this[j - 1] > temp) { 
                            /* 被比较的牌如果大于抽出的牌 */
                            this[j] = this[j - 1] /* 则被比较的牌往后放到一位到空位中,空位也就前移了 */
                        } else { 
                            break /* 否则 */
                        }
                        j--
                    }
                    this[j] = temp /* 将抽出的牌放到当前空出的位置 */
                }
                return this
            }
            arr = [2, 3, 1, 5, 4]
            console.log(arr.insertionSort())

**稳定性：稳定**  
**时间复杂度：O(N^2)** 两层嵌套循环  
最好情况：数组本来就有序，只需要一次循环将牌都抽一次O(N)  
最差情况：数组完全逆序，每次循环都要错位O(N^2)

### 冒泡排序和插入排序的比较： ###

插入排序相比冒泡排序而言，交换的操作要更加简单，冒泡排序是每一次都进行交换操作，而插入排序则是错开位置最后插入

**冒泡排序**、**插入排序**、**选择排序**合称为**简单排序**  
默认从小到大的排序顺序，如果对于下标`i<j`，而`arr[i]>arr[j]`，则称`(i,j)`是一对**逆序对**(inversion)  
对于序列`{34,8,64,51,32,21}`  
有`(34,8)(34,32)(32,21)(64,51)(64,32)(64,21)(51,32)(51,21)(32,21)`一共**9**个逆序对，  
**对于简单排序来说，每次交换的都是两个相邻的元素，所以交换一次就消除一个逆序对，做交换的次数也就正好等于逆序对的数量**

插入排序：`T(N,I)=O(N+I) /* I表示逆序对数量 */`  
如果序列中的逆序对比较少，换言之序列基本有序，则插入排序简单而高效

定理：任意N个不同元素组成的序列平均具有`N(N-1)/4`个逆序对  
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为`Ω(N^2)`（Ω为下界）  
这意味着：想要提高算法的效率，我们必须  
——>每次消去不止1个逆序对  
——>每次交换相隔比较远的2个元素，这样就可能在一次交换中消去几个逆序对

### 三、希尔排序（by Donald Shell） ###

利用了**插入排序**的简单，同时克服插入排序每次只交换**相邻**两个元素的缺点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 1]

#### 原始希尔排序： ####

Array.prototype.shellSort = function () { 
                for (let D = Math.floor(this.length / 2); D > 0; D = Math.floor(D / 2)) {  /* 选取增量序列 */
                    for (let i = D; i < this.length; i += D) {  /* 插入排序(将原来的1改为了D) */
                        let temp = this[i]
                        let j = i
                        while (j >= D) { 
                            if (this[j - D] > temp) { 
                                this[j] = this[j - D]
                            } else { 
                                break
                            }
                            j -= D
                        }
                        this[j] = temp
                    }
                }
                return this
            }
            console.log([2, 4, 5, 3, 1, 2, 5, 6, 7, 9, 1, 5, -1, 2, 6, 4, 72, 6, 8, 4].shellSort())

**最坏情况：T=Θ(N^2)**(Θ是上界也是下界)  
这种原始希尔排序有个缺点，因为他的增量序列是靠每次 `/2`来选取的，想下面这种情况则导致了一个问题：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 2]  
那么，就有一些学者提出了更多的增量序列：

1.Hibbard增量序列
      ·Dk=2^k - 1 保证了相邻元素互质
      ·最坏情况：T=Θ(N^(3/2)
      ·猜想：Tavg=O(N^(5/4))
    2.Sedgewick增量序列
      ·｛1，5，19，41，109，...｝
      计算方法：9*4^i - 9*2^i +1或4^i - 3*2^i + 1
      ·猜想：Tavg=O(N^(7/6)),Tworst=O(N^(4/3))
      ·当要排序的对象是几万数量级的，用希尔排序+Sedgewick增量序列效果是比较好的

### 四、选择排序 ###

Array.prototype.selectionSort = function () { 
                for (let i = 0; i < this.length; i++) { 
                    let minPosition = i
                    /* 从this[i]到this[length-1]中找最小元，并将其位置赋给minPosition */
                    for (let j = i + 1; j < this.length; j++) { 
                        if (this[j] < this[minPosition]) { 
                            minPosition = j
                        }
                    }
                    /* 将最小元和this[i]交换 */
                    let temp = this[i]
                    this[i] = this[minPosition]
                    this[minPosition] = temp
                }
                return this
            }
            console.log([5, 4, 1, 3, 2].selectionSort())

由于选择排序寻找最小元的操作每次都需要遍历完i到length-1的数组，所以他的**时间复杂度:** `T=Θ(N^2)`，对此寻找最小元操作的改进由此我们有了**堆排序**

### 五、堆排序 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 3]  
改进BuildHeap为大顶堆：

// 交换两个节点
            function swap(A, i, j) { 
                let temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
            // 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
            // 假设 结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的
            // 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
            // 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
            // 都执行 shiftDown操作，所以就满足了结点 i 以下的子堆已经是一大
            //顶堆
            function shiftDown(A, i, length) { 
                let temp = A[i]; // 当前父节点
                // j<length 的目的是对结点 i 以下的结点全部做顺序调整
                for (let j = 2 * i + 1; j < length; j = 2 * j + 1) { 
                    temp = A[i]; // 将 A[i] 取出，整个过程相当于找到 A[i] 应处于的位置
                    if (j + 1 < length && A[j] < A[j + 1]) { 
                        j++; // 找到两个孩子中较大的一个，再与父节点比较
                    }
                    if (temp < A[j]) { 
                        swap(A, i, j) // 如果父节点小于子节点:交换；否则跳出
                        i = j; // 交换后，temp 的下标变为 j
                    } else { 
                        break;
                    }
                }
            }
            // 堆排序
            Array.prototype.heapSort = function () { 
                // 初始化大顶堆，从第一个非叶子结点开始
                for (let i = Math.floor(this.length / 2 - 1); i >= 0; i--) { 
                    shiftDown(this, i, this.length);
                }
                // 排序，每一次for循环找出一个当前最大值，数组长度减一
                for (let i = Math.floor(this.length - 1); i > 0; i--) { 
                    swap(this, 0, i); // 根节点与最后一个节点交换
                    shiftDown(this, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                    // 前最大值，不需要再参与比较，所以第三个参数
                    // 为 i，即比较到最后一个结点前一个即可
                }
                return this
            }
            let arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
            console.log(arr.heapSort());

### 六、归并排序 ###

**稳定性：稳定**  
**时间复杂度：O(NlogN)**  
**空间复杂度: O(N)**

### 七、快速排序 ###

主元为头元素：

Array.prototype.quickSort = function () { 
                const rec = (arr) => { 
                    if (arr.length <= 1) { 
                        return arr
                    }
                    const left = []
                    const right = []
                    const mid = arr[0]
                    /* 这里基准主元我直接用了头部元素 */
                    for (let i = 1; i < arr.length; i++) { 
                        if (arr[i] < mid) { 
                            left.push(arr[i])
                        } else { 
                            right.push(arr[i])
                        }
                    }
                    return [...rec(left), mid, ...rec(right)]
                }
                const res = rec(this)
                res.forEach((n, i) => { 
                    this[i] = n
                });
                return this
            }
    
            const arr = [2, 4, 5, 3, 1]
            console.log(arr.quickSort())

**优化方案：**  
1.判断当前处理的数组大小，如果小于Cutoff（自己设定的一个值），则用插入排序处理  
2.主元的选取，上面这个算法主元选取的是头部元素，更好的方式是随机选取，但是Math.random()这个函数并不便宜，所以我们可以采用选取头中尾三个元素的中位数为主元

递归操作的时间复杂度是O(logN)  
分区操作的时间复杂度是O(N)  
所以快速排序的**时间复杂度是：O(NlogN)**

### 八、表排序 ###

表排序属于简介排序  
它针对排序对象的元素是一个很大的结构体的时候  
这种元素不适合进行直接移动  
所以我们用指针(元素的下标)代表元素进行排序  
比如我们要按照key的顺序输出书籍：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 4]

### 物理排序 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 5]

如上图，N个数字的排列由若干个独立的环组成。

即：

A\[0\]对应table\[3\]，A\[3\]对应table\[1\],A\[1\]对应table\[5\]，A\[5\]对应table\[0\]，这是一个环。  
有了独立的环，针对每个环进行移动操作则减少移动次数（避免无效的移动）。  
首先将A\[0\]存在Temp，之后将A\[3\]移至\[0\]，则此时\[3\]处空出，将A\[1\]移至\[3\]，以此类推。  
应该如何判断一个环结束呢？

if(table\[i\] == i) break;  
每当放好一本书时，就把其所放位置table\[i\]设为i。  
复杂度分析  
最好情况：初始即有序；  
最坏情况：

有⌊ N / 2 ⌋ \\lfloor N/2 \\rfloor⌊N/2⌋个环，每个环包含2个元素；  
需要⌊ 3 N / 2 ⌋ \\lfloor 3N / 2 \\rfloor⌊3N/2⌋此元素移动。  
则T = O ( m N ) T=O(mN)T=O(mN)，m是每个A元素的复制时间。

### 桶排序 ###

桶排序解释可参考：https://blog.csdn.net/an2766160/article/details/88532740

### 基数排序 ###

// Todo  
此文部分参考：浙江大学慕课 数据结构与算法 陈越  
向大家推荐浙江大学翁恺老师和陈越老师的慕课

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b28909472fb0462086162c446533f438.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d7b37b4d9b724017ad09b3a41c5ddce2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/d71be4b1f51d4e8aacbb40c103885d3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/3b532788ec664a64b251aabd86fbfa65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/6d83d4ce7dba414a9b7ade7d1c6bd930.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/34ec6012dd034f808f1f0a70f7174303.png