4. 希尔排序（Shell Sort）
思想
- 先将整个待排序的记录序列分割成为若干子序列。
- 分别进行直接插入排序。
- 待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。
过程
- 举个易于理解的例子：[35, 33, 42, 10, 14, 19, 27, 44]，我们采取间隔 4。创建一个位于 4 个位置间隔的所有值的虚拟子列表。下面这些值是 { 35, 14 }，{ 33, 19 }，{ 42, 27 } 和 { 10, 44 }。
- 我们比较每个子列表中的值，并在原始数组中交换它们（如果需要）。完成此步骤后，新数组应如下所示。
- 然后，我们采用 2 的间隔，这个间隙产生两个子列表：{ 14, 27, 35, 42 }， { 19, 10, 33, 44 }。
- 我们比较并交换原始数组中的值（如果需要）。完成此步骤后，数组变成：[14, 10, 27, 19, 35, 33, 42, 44]，图如下所示，10 与 19 的位置互换一下。
- 最后，我们使用值间隔 1 对数组的其余部分进行排序，Shell sort 使用插入排序对数组进行排序。
实现
const shellSort = arr => { let len = arr.length, temp, gap = 1; console.time('希尔排序耗时'); while (gap < len / 3) { //动态定义间隔序列 gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { for (let i = gap; i < len; i++) { temp = arr[i]; let j = i - gap; for (; j >= 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; console.log('arr :', arr); } } console.timeEnd('希尔排序耗时'); return arr; };
测试
// 测试 const array = [35, 33, 42, 10, 14, 19, 27, 44]; console.log('原始array:', array); const newArr = shellSort(array); console.log('newArr:', newArr); // 原始 array: [35, 33, 42, 10, 14, 19, 27, 44] // arr : [14, 33, 42, 10, 35, 19, 27, 44] // arr : [14, 19, 42, 10, 35, 33, 27, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [10, 14, 19, 27, 35, 33, 42, 44] // arr : [10, 14, 19, 27, 35, 33, 42, 44] // arr : [10, 14, 19, 27, 33, 35, 42, 44] // arr : [10, 14, 19, 27, 33, 35, 42, 44] // arr : [10, 14, 19, 27, 33, 35, 42, 44] // 希尔排序耗时: 3.592041015625ms // newArr: [10, 14, 19, 27, 33, 35, 42, 44]
分析
- 第一，希尔排序是原地排序算法吗 ？
希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1) 。所以，希尔排序是原地排序算法。
- 第二，希尔排序是稳定的排序算法吗 ？
我们知道，单次直接插入排序是稳定的，它不会改变相同元素之间的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，可能导致相同元素相对顺序发生变化。
因此，希尔排序不稳定。
- 第三，希尔排序的时间复杂度是多少 ？
最佳情况：T(n) = O(n logn)。
最差情况：T(n) = O(n (log(n))2)。
平均情况：T(n) = 取决于间隙序列。
动画
5. 堆排序（Heap Sort）
堆的定义
堆其实是一种特殊的树。只要满足这两点，它就是一个堆。
- 堆是一个完全二叉树。
完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。
对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。
其中图 1 和 图 2 是大顶堆，图 3 是小顶堆，图 4 不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。
思想
- 将初始待排序关键字序列 (R1, R2 .... Rn) 构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ..... Rn-1) 和新的有序区 (Rn) ，且满足 R[1, 2 ... n-1] <= R[n]。
- 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2 ...... Rn-1) 调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区 (R1, R2 .... Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程，直到有序区的元素个数为 n - 1，则整个排序过程完成。
实现
// 堆排序 const heapSort = array => { console.time('堆排序耗时'); // 初始化大顶堆，从第一个非叶子结点开始 for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) { heapify(array, i, array.length); } // 排序，每一次 for 循环找出一个当前最大值，数组长度减一 for (let i = Math.floor(array.length - 1); i > 0; i--) { // 根节点与最后一个节点交换 swap(array, 0, i); // 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可 heapify(array, 0, i); } console.timeEnd('堆排序耗时'); return array; }; // 交换两个节点 const swap = (array, i, j) => { let temp = array[i]; array[i] = array[j]; array[j] = temp; }; // 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是： // 假设结点 i 以下的子堆已经是一个大顶堆，heapify 函数实现的 // 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。 // 后面将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点 // 都执行 heapify 操作，所以就满足了结点 i 以下的子堆已经是一大顶堆 const heapify = (array, i, length) => { let temp = array[i]; // 当前父节点 // j < length 的目的是对结点 i 以下的结点全部做顺序调整 for (let j = 2 * i + 1; j < length; j = 2 * j + 1) { temp = array[i]; // 将 array[i] 取出，整个过程相当于找到 array[i] 应处于的位置 if (j + 1 < length && array[j] < array[j + 1]) { j++; // 找到两个孩子中较大的一个，再与父节点比较 } if (temp < array[j]) { swap(array, i, j); // 如果父节点小于子节点:交换；否则跳出 i = j; // 交换后，temp 的下标变为 j } else { break; } } };
测试
const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]; console.log('原始array:', array); const newArr = heapSort(array); console.log('newArr:', newArr); // 原始 array: [4, 6, 8, 5, 9, 1, 2, 5, 3, 2] // 堆排序耗时: 0.15087890625ms // newArr: [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
分析
- 第一，堆排序是原地排序算法吗 ？
整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。
- 第二，堆排序是稳定的排序算法吗 ？
因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
所以，堆排序是不稳定的排序算法。
- 第三，堆排序的时间复杂度是多少 ？
堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(nlogn)。
平均情况：T(n) = O(nlogn)。
动画
6. 排序算法的复杂性对比
复杂性对比
算法可视化工具
- 算法可视化工具 algorithm-visualizer
算法可视化工具 algorithm-visualizer 是一个交互式的在线平台，可以从代码中可视化算法，还可以看到代码执行的过程。
效果如下图。
旨在通过交互式可视化的执行来揭示算法背后的机制。
- 算法可视化来源 https://visualgo.net/en
效果如下图。
变量和操作的可视化表示增强了控制流和实际源代码。您可以快速前进和后退执行，以密切观察算法的工作方式。
