算法笔记（三）—— 桶排序及排序总结

堆

逻辑上是一棵完全二叉树（依次遍满或者全满）。

数组可以转为完全二叉树，完全二叉树某结点左孩子(2*i+1)，右孩子(i*2+2)，父结点((i-1/)2)，根节点的父还是自己。

如何将数组转化为堆（大根堆）：

1. 初始heapsize = 0，堆的尺寸

2. 给我一个5，我放在0位置，heapsize++

3. 再给我一个3，放在heapsize位置，heapsize++

4.给我一个6，同样，形成[5 3 6]，6需要跟其父结点比较，如果大于父则交换

5. 也就是说，当加入一个新数时，不断和自己的父结点比较，若大于父则交换，直到小于等于父

时间复杂度：O(logN)

如果拿掉了大根堆堆顶，怎么重新构造：

1. 先将数组最后一个数字放于0处，heapsize--

2. 从头结点开始，在左孩子和右孩子的最大值交换

3. 直到该结点成为叶子结点或者大于其左孩子和右孩子

时间复杂度：O(logN)

改变数组某位置的数据，怎么重新构造：

1. 判断变大了还是变小了

2. 若变小了，往下移

3. 若变大了，往上移

4. 不判断就两个全做即可

时间复杂度：O(logN)

堆排序

依次放入数组中的数，构造大根堆（小根堆），数组第一个元素与最后元素交换，heapsize--，重新构造，依次下次，直到堆的大小减为0，则实现排序。

时间复杂度：O(NlogN)

空间复杂度：O(1)

如何不通过添数的方式，依次heapify即可构造堆。时间复杂度O(N)

QUESTION

1. 准备一个小根堆，遍历数组，遍历前k+1个数构造

2. 小根堆的堆顶一定要在0位置，这时候弹出堆顶，加入下一个元素

3. 依次下去即可

桶排序（不基于比较的排序）

数据范围小的时候可以使用计数排序，一个数组统计数字频次，依次输出即可。

基数排序（可以通过词频统计完成入桶出桶操作）

1. 先看最大数字有几位，然后通过前补0，将所有数字变为该位

2. 准备10个（按进制来）的队列，根据数字最低位数放入对应队列

3. 从左到右取出队列数字

4. 按十位数放如对应序列，再从左到右取出

5. 下次下去，直到超过最大位数，排序完成