排序算法补充

堆排序

堆排序介绍

堆排序(Heap Sort)是一种基于比较的排序算法，它的核心思想是使用二叉堆来维护一个有序序列

• 二叉堆是一种完全二叉树，其中每个节点都满足父节点比子节点大(或小)的条件
• 在堆排序中，我们使用最大堆来进行排序，也就是保证每个节点都比它的子节点大

在堆排序中，我们首先构建一个最大堆

• 然后，我们将堆的根节点(也就是最大值)与堆的最后一个元素交换，这样最大值就被放在了正确的位置上
• 接着，我们将堆的大小减小一，并将剩余的元素重新构建成一个最大堆
• 我们不断重复这个过程，直到堆的大小为 1
• 这样，我们就得到了一个有序的序列

堆排序和选择排序有一定的关系，因为它们都利用了"选择"这个基本操作

• 选择排序的基本思想是在待排序的序列中选出最小(或最大)的元素，然后将其放置到序列的起始位置
• 堆排序也是一种选择排序算法，它使用最大堆来维护一个有序序列，然后不断选择出最大的值

堆排序时间复杂度为 O(nlogN)

手写堆排序

堆排序可以分为两大步骤：构建最大堆和排序

构建最大堆:

1. 遍历待排序序列，从最后一个非叶子节点开始，依次对每个节点进行调整
2. 假设当前节点的下标为 i，左子节点的下标为 2i+1，右子节点的下标为 2i+2，父节点的下标为 (i-1)/2
3. 对于每个节点 i，比较它和左右子节点的值，找出其中最大的值，并将其与节点 i 进行交换
4. 重复进行这个过程，直到节点 i 满足最大堆的性质
5. 依次对每个非叶子节点进行上述操作，直到根节点，这样我们就得到了一个最大堆

排序:

1. 将堆的根节点(也就是最大值)与堆的最后一个元素交换，这样最大值就被放在了正确的位置上
2. 将堆的大小减小一，并将剩余的元素重新构建成一个最大堆
3. 重复进行步骤 1 和步骤 2，直到堆的大小为 1，这样我们就得到了一个有序的序列

二叉堆索引

function heapSort(arr: number[]): number[] {
  // 1.获取数组的长度
  const n = arr.length
  // 2.对arr进行原地建堆
  // 2.1.从第一个非叶子节点开始进行下滤操作
  const start = Math.floor((n - 1) / 2)
  for (let i = start; i >= 0; i--) {
    // 2.2.进行下滤操作
    heapDown(arr, n, i)
  }
  // 3.对最大堆进行排序操作
  for (let i = n - 1; i > 0; i--) {
    swap(arr, 0, i)
    heapDown(arr, i, 0)
  }
  return arr
}
/**
 * 下滤操作函数
 * @param arr 在数组中进行下滤操作
 * @param n 下滤操作的范围
 * @param index 哪一个位置需要进行下滤操作
 */
function heapDown(arr: number[], n: number, index: number) {
  while (2 * index + 1 < n) {
    // 1.获取左右子节点的索引
    const leftChildIndex = 2 * index + 1
    const rightChildIndex = 2 * index + 2
    // 2.找出左右子节点较大的值
    let largeIndex = leftChildIndex
    if (rightChildIndex < n && arr[rightChildIndex] > arr[leftChildIndex]) {
      largeIndex = rightChildIndex
    }
    // 3.判断index位置的值比更大的子节点，直接break
    if (arr[index] >= arr[largeIndex]) {
      break
    }
    // 4.和更大位置的进行交换操作
    swap(arr, index, largeIndex)
    index = largeIndex
  }
}

堆排序复杂度

堆排序的时间复杂度分析较为复杂，因为它既涉及到堆的建立过程，也涉及到排序过程

1. 堆的建立过程
   • 堆的建立过程包括 n/2 次堆的向下调整操作，因此它的时间复杂度为 O(n)
2. 排序过程步骤
   • 排序过程需要执行 n 次堆的删除最大值操作，每次操作都需要将堆的最后一个元素与堆顶元素交换，然后向下调整堆
   • 每次向下调整操作的时间复杂度为 O(logN)，因此整个排序过程的时间复杂度为 O(nlogN)

综合起来，堆排序的时间复杂度为 O(nlogN)

需要注意的是，堆排序的空间复杂度为 O(1)，因为它只使用了常数个辅助变量来存储堆的信息

总结：

堆排序是一种高效的排序算法，它利用堆这种数据结构来实现排序

• 堆排序具有时间复杂度为 O(nlogN) 的优秀性能，并且由于它只使用了常数个辅助变量来存储堆的信息，因此空间复杂度为 O(1)
• 但是，由于堆排序的过程是不稳定的，即相同元素的相对位置可能会发生变化，因此在某些情况下可能会导致排序结果不符合要求

总的来说，堆排序是一种高效的、通用的排序算法，它适用于各种类型的数据，并且可以应用于大规模数据的排序

希尔排序

希尔排序介绍

希尔排序(Shell Sort)是一种创新的排序算法，它的名字来源于它的发明者 Donald shell(唐纳德·希尔)，1959年，希尔排序算法诞生了

在简单排序算法诞生后的很长一段时间内，人们不断尝试发明各种各样的排序算法，但是当时的排序算法的时间复杂度都是 O(N^2^)，看起来很难超越

• 当时计算机学术界充满了"排序算法不可能突破 O(N^2^)" 的声音，这与人类100米短跑不可能突破10秒大关的想法一样
• 这是因为很多著名的排序算法，如冒泡排序、选择排序、插入排序等，它们的时间复杂度都是 O(N^2^) 级别的
• 因此，人们普遍认为，除非发生突破性的创新，否则排序算法的时间复杂度是不可能达到 O(nlogN) 级别的

在这种情况下，希尔排序的提出成为了一种重要的突破

• 希尔排序利用了分组和插入排序的思想，通过不断缩小间隔的方式，让数据不断地接近有序状态，从而达到了较高的排序效率
• 希尔排序的时间复杂度不仅低于 O(N^2^)，而且可以通过调整步长序列来进一步优化。这一突破性的创新引起了广泛的关注和研究，也为后来的排序算法研究提供了重要的借鉴

回顾插入排序的过程:

• 由于希尔排序基于插入排序，所以有必要回顾一下前面的插入排序
• 我们设想一下，在插入排序执行到一半的时候，标记符左边这部分数据项都是排好序的，而标识符右边的数据项是没有排序的
• 这个时候，取出指向的那个数据项，把它存储在一个临时变量中，接着，从刚刚移除的位置左边第一个单元开始，每次把有序的数据项向右移动一个单元，直到存储在临时变量中的数据项可以成功插入

插入排序的问题:

• 假设一个很小的数据项在很靠近右端的位置上，这里本来应该是较大的数据项的位置
• 把这个小数据项移动到左边的正确位置，所有的中间数据项都必须向右移动一位
• 如果每个步骤对数据项都进行N次移动，平均下来是移动N/2，N个元素就是N*N/2=N^2^/2
• 所以我们通常认为插入排序的效率是O(N^2^)
• 如果有某种方式，不需要一个个移动所有中间的数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率就会有很大的改进

希尔排序的做法:

• 比如下面的数字：81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15
• 我们先让间隔为5，进行排序。(35，81)，(94，17)，(11，95)，(96，28)，(12，58)，(35，41)，(17，75)，(95，15)
  • 排序后的新序列，一定可以让数字离自己的正确位置更近一步
• 我们再让间隔为3，进行排序。(35，28，75，58，95)，(17，12，15，81)，(11，41，96，94)
  • 排序后的新序列，一定可以让数字离自己的正确位置又近了一步
• 最后，我们让间隔为1，也就是正确的插入排序。这个时候数字都离自己的位置更近，那么需要复制的次数一定会减少很多

手写希尔排序

希尔排序的基本思想是利用分组插入排序的思想，通过不断缩小间隔来让数据逐步趋于有序。它的步骤思路如下:

1. 定义一个增量序列 d1, d2,… dk，一般选择增量序列最后一个元素为1，即 dk=1
2. 以 dk 为间隔将待排序的序列分成 dk个子序列，对每个子序列进行插入排序
3. 缩小增量，对缩小后的每个子序列进行插入排序，直到增量为1

其中，第一步的增量序列的选择比较重要，增量序列的不同选择会影响到排序效率的好坏。目前比较常用的增量序列有希尔增量、Hibbard增量、Knuth增量等

以希尔增量为例，希尔增量的计算方法为：dk=floor(n/2^K)，其中，k为增量序列的元素下标，n为待排序序列的长度。当 k=0 时，dk=1

function shellSort(arr: number[]): number[] {
  const n = arr.length
  // 选择不同的增量(步长/间隔)
  let gap = Math.floor(n / 2)
  // 1.不断改变步长的过程
  while (gap > 0) {
    // 获取到不同的gap，使用gap进行插入排序
    // 2.找到不同的数列集合进行插入排序操作
    for (let i = gap; i < n; i++) {
      let j = i
      const num = arr[i]
      // 使用num向前去找一个比num小的值
      // 3.while循环，对数列进行插入排序的过程
      while (j > gap - 1 && num < arr[j - gap]) {
        arr[j] = arr[j - gap]
        j = j - gap
      }
      arr[j] = num
    }
    gap = Math.floor(gap / 2)
  }
  return arr
}

希尔排序复杂度

希尔排序的效率

• 希尔排序的效率和增量是有关系的
• 但是，它的效率证明非常困难，甚至某些增量的效率到目前依然没有被证明出来
• 但是经过统计，希尔排序使用原始增量，最坏的情况下时间复杂度为 O(N^2^)，通常情况下都要好于 O(N^2^)

Hibbard 增量序列

• 增量的算法为2^k-1^。也就是为1 3 5 7...等等
• 这种增量的最坏复杂度为 O(N^3/2^)，猜想的平均复杂度为 O(N^5/4^)，目前尚未被证明

Sedgewick 增量序列

• { 1，5，19，41，109，…)，该序列中的项或者是9×4^i^-9×2^i^+ 1或者是4^i^-32^i^+1
• 这种增量的最坏复杂度为 O(N^4/3^)，平均复杂度为 O(N^7/6^)，但是均未被证明。

总之，我们使用希尔排序大多数情况下效率都高于简单排序

总结：

• 希尔排序是一种改进版的插入排序，从历史的角度来看，它是一种非常非常重要的排序算法，因为它解除了人们对原有排序的固有认知
• 希尔排序的时间复杂度取决于步长序列的选择，目前最优的步长序列还没有被证明，因此希尔排序的时间复杂度依然是一个开放的问题
• 但是现在已经有很多更加优秀的排序算法：归并排序、快速排序等，所以从实际的应用角度来说，希尔排序已经使用的非常非常少了
• 因为，我们只需要了解其核心思想即可