3. 详解桶排序以及排序内容大总结

Tags: 堆

堆结构(Heap)

• 本质上是一棵完全二叉树
  • N个结果点的完全二叉树，高度为$O(logN)$
• 优先级队列结构底层就是堆结构
• 可以把数组从0位置(index)开始的连续一段想象成完全二叉树，这也是在构建所谓堆的时候的实际做法，以数组来间接构建堆。
  • 
  • 其对应的Index在完全二叉树的位置如图
    • 
  • 对于第i个index，其左孩子的index为$2i+1$，右孩子为$2i+2$，父节点index为$\frac{i-1}{2}$

• 堆可以分为大根堆和小根堆
  • 大根堆：一个完全二叉树中，每一个子树内的值都比头节点的值小。
  • 小根堆：一个完全二叉树中，每一个子树都比头节点的值大
    • 构建小根堆的方法同上
• 堆操作HeapInsert：向大根堆中插入一个元素。（以大根堆为例）新进来的子节点都需要和父节点比较，大于父节点值就交换（可能需要比到头，该过程称为HeapInsert）。 - 时间复杂度$O(logN)$，只走一个父节点的路，最差一路向上（即走完了二叉树的高度） - HeapInsert实际代码 -
• 堆操作Heapify：找到大根堆中最大值，移除并保证后续的堆结构仍为大根堆
  • 具体方法：大根堆就是index=0的位置，将堆最后一个位置的数字移到首位（ind=0）,同时heapsize-1。后从ind=0开始，比较该位置的数字与其两个子孩子的最大值的关系，若该位置小于最大值，两者交换，重复停止条件为：1.比两个子孩子都大，2.堆越界。
  • 时间复杂度$O(logN)$，只走一个子节点的路，最差一路向下（即走完了二叉树的高度）
  • 实际代码
    • 

• 堆操作：用户给定一个ind（ind在有效区域内），要求把这个ind上的值替换成target。
  • 具体方法：根据当前位置值和target比较大小，决定使用Heapify操作还是Heapinsert操作

对于系统给的`Class Heap`细粒度比较高，无法（高效）完成上述第三个堆操作，而自己实现的堆操作是可以实现更加细粒度的操作。所以有的时候在做算法题的时候需要自己手写堆的数据结构类。简言之，系统的堆类只能实现你给我一个数后者

堆排序

• 步骤：
  1. 给定数组arr，逐步将数据变成大根堆（先00位置，再01位置，在0~2位置…逐渐扩到数组的整体，即不断增加heapSize，并执行heapInsert操作，将数组逐一Insert到当前的大根堆中）
  2. 将大根堆最大的值（ind=0）和数组最后一个数交换（也就是大根堆最后一个数），然后heapSize--（即相当于把换到最后一个位置的最大的数和堆断开）
  3. 利用heapify重新构建当前的大根堆
  4. 重复2~3步骤直到heapSize=1完成排序。
• 实际代码：
• 时间复杂度：$O(NlogN)$
• 额外空间复杂度：$O(1)$ → 只有堆排能做到，其他排序都不能做到
• 如果一股脑给你一整个数组让你构成大根堆而不是一个一个给你的，更好的方法是从右下的最小子树开始一点一点做heapify，这样做比逐个做heapInsert更快一点，但不会影响整体复杂度。

比较器

• 比较器的实质就是重载比较运算符
  • 在C++里就是重载运算符的意思，在Java里就是告诉他两个东西比较大小的规则（说明跟普通的比较大小的规则不一样）
• 比较器可以很好的应用在特殊标准的排序上
• 比较器可以很好的应用在根据特殊标准排序的结构上

有人说这是Python的魔法方法

桶排序

• 桶排序不是基于比较的排序，而别的排序：只和”比较”这个事情有关，即都是基于比较的排序
• 不是基于比较的排序，需要结合数据状况来定制，是一种小众的排序

计数排序

• 定义：计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
• 分析：当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

基数排序

• 需要设置多个桶，同时需要对空位补0，比如(1,2,5,78,134) → (001,002,005,078,134)
• 需要要求排序的东西是有进制的东西

桶：我们不关心其数据结构，按需而定，然后把东西扔进去就行

相关题目

• 题目：已知一个几乎有序的数组, 几乎有序是指, 如果把数组排好顺序的话, 每个元素移动的距离可以不超过k, 并且 k 相对于数组来说比较小。请选择一个合适的 排序算法针对这个数据进行排序。 堆 排序算法
  • 思路：比如K=6，准备一个小根堆，对给定的数组遍历前7个数，扔到小根堆里。然后把小根堆的最小值放到ind=0（根据题意，可以肯定的是0位置此时一定是最小值），之后把ind=0的最小值弹出（注意这里是弹出，弹出后数组该位置之后的元素前移），然后再重复上述步骤。【当然，这样处理也可以是其他的排序算法，就是相当于有一个长度为K的窗，在窗内排序。】
  • 时间复杂度为$O(NlogK)$，若K很小，则可以认为是$O(N)$
  • 题解：
    • 
    • PS: 上图java代码中有小根堆的数据结构，就是优先级队列。Python中使用小根堆结构如下

      import heapq
       
      heap = []
      heapq.heappush(heap, val) #入堆
      heapq.heappop(heap) #弹出，每次都是最小值，因为这是小根堆
      heapq.heapify(List) #把一个列表list变成小根堆