3，堆，桶排序，排序总结【p4-p5】

3.1堆

堆在逻辑概念上是完全二叉树结构，堆分为大根堆和小根堆

3.1.1堆结构

堆结构就是用数组实现的完全二叉树
完全二叉树中如果每颗子树的最大值都在顶部就是大根堆
完全二叉树中如果每颗子树的最小值都在顶部就是小根堆
堆结构的heapInsert与heapify操作
堆结构的增大和减小
优先级队列结构，就是堆结构

3.1.1.1完全二叉树

完全二叉树是满二叉树或者从左往右依次变来的树

完全二叉树有1个节点，高度为1
完全二叉树有2，3个节点，高度为2
完全二叉树有4，5，6，7个节点，高度为3
完全二叉树有n个节点，高度为logn,O(logN)

满二叉树：一个点是满二叉树，一个点下有两个点是满二叉树，一个点下两个点的下一个或各有两个点也叫满二叉树

左往右依次变来的树：


但是下图不是左往右依次变来的树

由值构成的完全二叉树

由下标构成
size=7

i位置的左孩子为2* i+1
i位置的右孩子为2* i+2
i位置的父为(i-1)/2

在知道size的情况下通过上方就可以找到了

3.1.1.2堆分为大根堆和小根堆

大根堆：每一个节点为头的子树，子树上最大值为头节点

以6为头的树最大值是6，以5为头的树最大值是5……这个二叉树为大根堆

小根堆，每一个节点为头的子树，子树上最小值为头节点

怎么把数组连续触发的一段搞成一个堆？
创建一个空的数组
heapsize=0代表数组中从0出发的连续的0个数是堆
导入5，放在0位置上，heapsize=1，现在是大根堆
导入3，放在heapsize=1位置上，heapsize=2，现在是大根堆
导入6，放在heapsize=2位置上，heapsize=3，不是大根堆，需要调整，用上述公式找到父，和父5比较，比父大则交换，现在是大根堆

导入7，放在heapsize=3位置上，heapsize=4，不是大根堆，需要调整，用上述公式找到父，和父3比较，比父大则交换，用上述公式找到父，和父6比较，比父大则交换

导入7，放在heapsize=4位置上，heapsize=5，不是大根堆，需要调整，用上述公式找到父，和父6比较，比父大则交换，用上述公式找到父，和父7比较，等于，是大根堆

如此可保证树必定是大根堆，叫heapinsert过程

找出刚才输入的最大数字，在0位置

3.1.1.2.1案例1-去掉最大数字，使剩下的数字依然是大根堆

去掉最大数字，使剩下的数字依然是大根堆怎么做？
把已经形成的堆结构的最后一个数字放在0位置上，把heapsize减小1
用头节点看两个孩子的最大值，选最大值替换，循环此操作，知道两孩子没有比父值大的或者没有孩子时停止

#include<iostream>
#include<algorithm>
void heapify(int arr[], int index, int heapSize)
{int left = index * 2 + 1;//左孩子的下标int largest;while (left < heapSize)//左孩子是否越界(左孩子下标比右孩子下标小，可以判断有没有孩子){int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;//两个孩子中，谁的值大，把下标给largest//如果有右孩子，同时右孩子值大于左孩子的值，largest就是右孩子下标//父和孩子之间，谁的值大，把下标给largestlargest = arr[largest] > arr[index] ? largest: index;if (largest == index)//父大则退出循环{break;}std::swap(arr[largest], arr[index]);index = largest;left = index * 2 + 1;}}int main()
{int arr[9] = { 5, 3, 6, 8, 2, 4, 7, 9, 1 };for (int i = 9 / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始向前构建大根堆heapify(arr, i, 9);}for (int i = 0; i < 9; i++) {std::cout << arr[i] << " ";}std::cout << std::endl;std::system("pause");return 0;
}

3.1.1.2.2案例2

创建一个堆，有效区域是0到heapsize-1，i位置数变为？，怎么在i改变为？后依然让这片有效区域为大根堆
分析：
i变大，往上调整
i变小，往下调整
时间复杂度：O(logN)

3.1.1.2.3案例3

删掉最大值，并让剩下的数重新调整成堆，时间复杂度是多少？

先让数组整体变为大根堆
heapsize=0
让0位置到0位置变为大根堆，heapsize=1
让0到1范围变为大根堆，5和3交换，heapsize=2
让0到2范围变为大根堆，9和5交换，heapsize=3
让0到3范围变为大根堆，不动，heapsize=4
让0到4范围变为大根堆，6和4交换，heapsize=5
让0到5范围变为大根堆，7和5交换，heapsize=6
让0到6范围变为大根堆，不动，heapsize=7
9673450

0位置和6位置交换变为0673459，heapsize=6（把最后的位置和堆断掉联系）怎么让其依旧为大根堆

0选一个较大的孩子，和7交换
7603459
0和5交换
7653409（为什么9没动，因为heapsize=6）

继续让0和7交换，heapsize=5（7被隐藏），怎么让其依旧为大根堆
0选一个较大的孩子，和6交换
6053479
0选一个较大的孩子，和4交换
6453079

继续让0和6交换，heapsize=4（6被隐藏），怎么让其依旧为大根堆
0选一个较大的孩子，和5交换
5403679

继续让0和5交换，heapsize=3（3被隐藏），怎么让其依旧为大根堆
0选一个较大的孩子，和5交换
5403679

让0和4交换，heapsize=2（5被隐藏），为大根堆
heapsize=1
0453679

这段代码，未完成

#include<iostream>
#include<algorithm>void heapInsert(int arr[], int index);
void heapify(int arr[], int index, int heapSize);void heapSort(int arr[], int size)
{if (arr == NULL || size < 2){return;}for (int i = 0; i < size; i++)//O(N){heapInsert(arr, i);//O(logN)}int heapSize = size;std::swap(arr[0], arr[--heapSize]);while (heapSize > 0)//O(N){heapify(arr, 0, heapSize);//O(logN)std::swap(arr[0], arr[--heapSize]);//O(1)}
}void heapInsert(int arr[], int index)
{while (arr[index] > arr[(index - 1) / 2]){std::swap(arr[index], arr[(index - 1) / 2]);index = (index - 1) / 2;}
}void heapify(int arr[], int index, int heapSize)
{int left = index * 2 + 1;//左孩子的下标int largest;while (left < heapSize)//左孩子是否越界(左孩子下标比右孩子下标小，可以判断有没有孩子){largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;//两个孩子中，谁的值大，把下标给largest//如果有右孩子，同时右孩子值大于左孩子的值，largest就是右孩子下标//父和孩子之间，谁的值大，把下标给largestlargest = arr[largest] < arr[index] ? largest : index;if (largest == index)//父大则退出循环{break;}std::swap(arr[largest], arr[index]);index = largest;left = index * 2 + 1;}}int main()
{int arr[] = { 5, 3, 6, 8, 2, 4, 7, 9, 1 };int size = sizeof(arr) / sizeof(arr[0]);heapSort(arr, size);for (int i = 0; i < size; i++){std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}

3.1.1.2.4案例4-方便制造大根堆方法

直接放入全部节点而不是一个一个插入时
可以从最后一个孩子的父出发，做大根堆

依次从最下端的父出发，做大根堆
最后一层树做完，从倒数第二层树的父出发，做大根堆
时间复杂度：
数组中有N个数，最底层节点（也叫叶节点）有多少个，N/2个
倒数第二层节点N/4个
倒数第三层节点N/8个
所以时间复杂度：
T(N)=N/2+2N/4+3N/8+4N/16+5N/32……
2T(N)=N/2+2N/2+3N/4+4N/8+5N/16……
T(N)=N/2+N/4+N/8+N/+5*N/32……

#include<iostream>
#include<algorithm>void heapInsert(int arr[], int index);
void heapify(int arr[], int index, int heapSize);void heapSort(int arr[], int size)
{if (arr == NULL || size < 2){return;}/* for (int i = 0; i < size; i++)//让整个数组变成大根堆的话用此方法{heapInsert(arr, i);}*/for (int i = size - 1; i >= 0; i--)//修改的代码，相比上述注释代码，快了一点{heapify(arr, i, size);}int heapSize = size;std::swap(arr[0], arr[--heapSize]);while (heapSize > 0)//O(N){heapify(arr, 0, heapSize);//O(logN)std::swap(arr[0], arr[--heapSize]);//O(1)}
}void heapInsert(int arr[], int index)
{while (arr[index] < arr[(index - 1) / 2]){std::swap(arr[index], arr[(index - 1) / 2]);index = (index - 1) / 2;}
}void heapify(int arr[], int index, int heapSize)
{int left = index * 2 + 1;//左孩子的下标int smallest;while (left < heapSize)//左孩子是否越界(左孩子下标比右孩子下标小，可以判断有没有孩子){smallest = left + 1 < heapSize && arr[left + 1] < arr[left] ? left + 1 : left;//两个孩子中，谁的值大，把下标给largest//如果有右孩子，同时右孩子值大于左孩子的值，largest就是右孩子下标//父和孩子之间，谁的值大，把下标给largestsmallest = arr[smallest] < arr[index] ? smallest : index;if (smallest == index)//父大则退出循环{break;}std::swap(arr[smallest], arr[index]);index = smallest;left = index * 2 + 1;}}int main()
{int arr[] = { 5, 3, 6, 8, 2, 4, 7, 9, 1 };int size = sizeof(arr) / sizeof(arr[0]);heapSort(arr, size);for (int i = 0; i < size; i++){std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}

3.1.2堆排序

3.1.2.1案例-堆排序的扩展

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对与数组来说比较小。
请选择一个合适的排序算法针对这个数据进行排序

设k=6，准备一个小根堆，
遍历前七个数
0123456，放到小根堆内，小根堆的最小值放在0位置，
7放到小根堆内，小根堆的最小值放在1位置
8放到小根堆内，小根堆的最小值放在2位置
…………
数组临近结束时，小根堆依次弹出最小值，放到数组
所以时间复杂度O(N*logk)

3.1.2.1.1扩容

一直添加变量的话需要 扩容，100变200，200变400，单词扩容的时间复杂度O(N)
假设加了N个数，扩容的次数为logN次，每一次扩容为O(N)水平，整体代价为O(NlogN)，单位平均扩容代价O(NlogN)/N=O(logN)

3.1.2.1.2※使用系统提供的堆结构

需注意：系统提供的堆结构类似于黑盒，只用程序员给它一个数add，黑盒传出一个数poll
不支持，更改一个堆结构内的数，使其重新用低代价再次变为堆结构，他会扫描所有才能操作，而手写的是支持的（※有需求时候用手写堆，没需求用自带堆更方便）

3.2比较器的使用

比较器的实质就是重载比较运算符
比较器可以很好的应用在特殊标准的排序上
比较器可以很好的应用在根据特殊标准的结构上

如果返回负数，认为第一个参数应该放在上面
如果返回正数，认为第二个参数应该放在前面
如果返回0，认为谁放前面都行

在类中三个元素，工号，姓名，年龄，排大小时，由大到小排序，需要自行设定用哪个元素排序，本质是c++中的重载比较运算符

怎么做出大根堆的比较器：第二个参数减第一个参数即可

3.3不基于比较的排序

例：一个数组内均为员工年龄，0~200
建立一个201的数组，0位置代表0岁的员工多少个
1位置代表1岁的员工多少个
2位置代表2岁的员工多少个
3位置代表3岁的员工多少个
…………
遍历老数组
发现0岁的时候新数组0位置++
发现1岁的时候新数组1位置++
…………

时间复杂度：O(N)

如果老数组位-2⁹⁹⁹~2⁹⁹⁹则需要创建的新数组太多了，太麻烦
所以不基于比较的排序 是根据数据状况做的排序，没有基于比较排序的应用范围广

3.3.1基数排序

3.3.1.1基数排序 例1：

本例目的：从小到大排序
[17，13，25，100，72]
先看最大数字几位：3位
所以都补成3位
[017，013，025，100，072]
准备是个容器（也可称为桶）
（桶的结构可以是数组、队列、栈、都可以）
本题中桶的结构是队列
准备0到9号桶
根据个位数放在对应桶中

把桶中的数字依次倒出来，先进先出

根据十位数放在对应桶中

把桶中的数字依次倒出来

根据百位数放在对应桶中

把桶中的数字依次倒出来

依然根数据状况有关，因为次排序和进制有关

3.3.1.2代码原理例2：

[013,021,011,052,062]

count代表个位比下标个数小与等于的个数，所以下标1有2个，下标2有2+2=4个，下标3有1+4=5个……
从右往左遍历数组（为什么从右往左遍历，因为这样等同于先出桶）
062，在下标2处，2对应的为4，所以写入新数组4-1=3位置，2位置count变为3
052，在下标2处，2对应的为3，所以写入新数组3-1=2位置，2位置count变为2
011，在下标1处，1对应的为2，所以写入新数组2-1=1位置，1位置count变为1
021，在下标1处，1对应的为1，所以写入新数组1-1=0位置，1位置count变为0
013，在下标3处，3对应的为5，所以写入新数组5-1=4位置，3位置count变为4

3.4排序总结

3.4.1排序算法的稳定性

同样的个体之间，如果不因为排序而改变相对次序，就是这个排序是具有稳定性的；否则就没有

不具备稳定性的排序：
选择排序、快速排序、堆排序

具备稳定性的排序：
冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度O(N*logN),额外空间复杂度O(1)，又稳定的排序

稳定性：值相同的元素排序之后能否保证原来的相对次序不变
[2,1,2,1,3,2,3,2]
[1,1,2,2,2,2,3,3]
原数组的第一个1和第二个1位置，在新数组中的顺序是不是还是同样的前后关系

稳定性的好处：
数个班级学生按年龄从小到大排序
再次按班级排序，如果是算法稳定的，则再每个班级的桶中，年龄依旧从小到大
在实际使用中有很多好处，比如商品先价钱排序，再好评率排序，即可得出物美价廉的商品

3.4.1.1选择排序的稳定性

不具备稳定性
[3,3,3,3,1,3,3,3,3,3,3,3]
1和第一个3做交换，所以第一个3和其他3的次序发生了改变

3.4.1.2冒泡排序的稳定性

具备稳定性
[6,5,4,5,3,4,6]
0,1,2,3,4,5,6
第一个6一直交换到下标为5处，同等大小时不交换，和同种元素第二个6位次不变，继续也是如此，所以稳定
因为同等大小时不交换所以具有稳定性，也可以同等大小时交换，这是就不具备稳定性了，所以说可以实现稳定性

3.4.1.3插入排序的稳定性

具备稳定性
[3,2,2-------]
0~0有序，3
0~1有序，第一个2和3排序，交换，第一个2和第二个2位次不变
0~2有序，第二个2和3排序，交换，第一个2和第二个2位次不变
因此具备稳定性

3.4.1.4快排的稳定性

不具备稳定性
1.0

不具备稳定性
[6,7,6,6,3]
以5作为划分值
6，7，6，6都大于5
5和3对比，5大，则3和0位置的6交换
第一个6和第二三个6的次序打乱
则不具备稳定性

2.0

不具备稳定性
[5,5,5,3,6,7]
以5作为划分值
0,1,2下标位置都为5相同，不动
5和3比较，3和0下标的数5交换，则第一个5和其他同样元素5次序打乱
则不具备稳定性

3.4.1.5堆排的稳定性

不具备稳定性
[5,4,4,6]
形成大根堆时6需要与第一个4交换，则第一个4和其他同样元素4次序打乱
则不具备稳定性

3.4.1.6计数排序与基数排序的稳定性

具备稳定性

3.4.2总结

一般用的都是快排，对空间复杂度有要求时使用堆排，需要稳定性时使用堆排

问题：
基于比较的排序时间复杂度能否做到O(NlogN)以下？
目前没有，不行
时间复杂度O(NlogN)时，空间复杂度做到O(N)以下，还能做到稳定性？
目前没有，不行

常见的坑：
1，归并排序的额外空间复杂度可以变成O(1)，可以，但是非常难，不需要掌握，有兴趣可以搜“归并排序内部缓存法”，变完O(1)会丧失稳定性
2，“原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成0(N²)
3，快速排序可以做到稳定性问题，但是非常难，不需要掌握， 可以搜“01stable sort”,达到时会使空间复杂度变为O(N)
4，所有的改进都不重要，因为目前没有找到时间复杂度0(N*logN)，额外空间复杂度0(1)，又稳定的排序。
5，有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官
经典快排的partion做不到稳定性，又是01标准
奇偶问题和快排01标准是一种策略，让面试官叫你这道论文级的题

3.4.3工程上对排序的改进

充分利用O(N*logN）和O(N²)排序各自的优势
稳定性的考虑