算法练习day6——190323（求中位数、堆排序、稳定性）
1.求中位数
有一个流，不断输出数，然后会不停地询问已输出的那些书的中位数。
解决方法：用一个大根堆，一个小根堆存那些已输出的数。
- 大根堆中存储较小的N/2个数；
- 小根堆中存储较大的N/2个数；
- 这样，中位数=（大根堆的根+小根堆的根）/2；
- 大根堆的根是较小的N/2中最大的；
- 小根堆的根是较大的N/2中最小的；
- 两者刚卡在数据的中间。
具体步骤：
- 输出的第一个数先放在大根堆；
- 后面输出的数小于等于大根堆的根，则如大根堆，然后调整堆；
- 若大于大根堆中的根，则入小根堆，调整堆；
- 若大根堆中的节点数比小根堆中的节点数多2个，则将大根堆的根取出，如小根堆；反之亦然。
- 用heapsize记录已形成的堆的大小;
- 取根的结果：
- 大根堆中最大的进入小根堆，满足小根堆中的数都大于大根堆中的数；
- 小根堆中最小的进入大根堆，满足小根堆中的数都大于大根堆中的数。
如何弹出大顶堆的根（小根堆类似）：
- 最后一个元素和堆顶元素交换；
- 堆范围-1；
- 再调整堆。
比如：
1、交换6和1：
2、堆范围-1（0~4变为0~3）：
3、调整堆：
调整之后：
2.堆的重要性
几乎一切的贪心结构都是用堆完成的。
优先级队列就是堆！
3.堆排序
步骤：
- 建立大根堆（并不是有序的）；
- 将堆顶位置的数和最后一个数交换位置；
- 堆范围-1；
- 调整堆；
- 重复2~4，直至堆大小减为0。
代码实现：
package Sort;public class HeapSort {public static void main(String[] args) {int[] array= {2,1,3,6,0,4};for(int i=0;i0) {heapify(arr,0,heapsize);swap(arr,0,--heapsize);}}public static void heapInsert(int[] arr,int i) {while(arr[i]>arr[(i-1)/2]) {swap(arr,i,(i-1)/2);i=(i-1)/2;//变为自己的父节点，继续向上比较}}public static void heapify(int[] arr,int i,int heapsize) {int left=i*2+1;while(leftarr[j]?arr[i]:arr[j];return num>arr[k]?num:arr[k];}
}
运行结果：
4.排序算法的稳定性
4.1 3个常规的
的排序
4.1.1 冒泡排序
可以做到稳定
相等时不交换，让后面的数继续往后比较即可。
第一次比较之后，交换：
第二次比较之后，交换：
第三次比较之后，相等，不交换：
让后面的7再和之后的数进行比较，则可保证这两个7的相对位置不变。
4.1.2 插入排序
可是实现为稳定的。
和前面数相等时，不交换。
第一次比较之后，交换：
第二次比较，相等，不交换，停止：
此时两个6的相对位置没变。
4.1.3 选择排序
无法做到稳定性。
第一次比较之后，0个第一个5进行交换：
现在第一个5和其他5的相对位置发生了变化，它从第一个变为了第四个。——不稳定。
4.2 
d的三个排序
4.2.1 归并排序
可以做到稳定。
merge时，若左=右，则先拷贝左，保证右和左相同的值不会跨到左的前面。
p1和p2指向的两个位置的值相等，都为3，先把p1指向的3拷贝到辅助数组；
p1右移；
此时p1指向的还为3，则继续将它拷贝到辅助数组；
p1右移；
p1的值4>3，将p2指向的3拷贝到辅助数组。
这种方式即可保证三个3的相对位置不变。
4.2.2 快速排序
不能保证稳定性。
因为partation过程无法实现稳定性。
荷兰国旗问题同理。
若目前情况如下所示：
此时，要处理的元素是3，它小于4，将它与最前面的4进行交换：
第一个4就变成了第三个4，不稳定。
题：奇数放在数组左边， 偶数放在数组右边， 还要求原始的相对次序不变。
此题类似于快排的Partation过程。
若要实现，<01 stable sort>有方法可解决，但特变难。
4.2.3 堆排序
无法实现稳定性。
因为交换过程中不关心相等值。
原始堆如下：
此时插入一个5：
需要对堆进行调整：
首先就是把5和它的父节点的4进行交换;
目前，4的相对位置已发生变化，所以堆排序不是稳定的。
4.3
| 排序算法 | 是否稳定 |
|---|---|
| 冒泡 | √ |
| 插入 | √ |
| 选择 | × |
| 归并 | √ |
| 快排 | × |
| 堆排 | × |
表格总结
4.4 稳定性的意义
可以利用前面比较的结果。
比如实际应用中，要对学生的一系列属性进行排序，具体信息如下：
首先按成绩从高到低进行排序：
再按班级进行排序：
则按班级排好之后，班级内的成绩也是按从高到低次序排列的，利用了前面按成绩排序的结果。
- 班级号相同的，按原始的相对位置（成绩从高到低的次序）调到了一块。
5. 工程中的综合排序算法
5.1 数组很大
先对数组内的元素类型进行判断：
5.1.1 元素类型为基本类型
则相同值之间无差异，不用氛原始顺序，所以可以采用不稳定的排序算法。
使用快速排序。
5.1.2 元素类型为自定义数据类型
例如：学生，需要先按成绩排序，再按班级号排序。即成绩相同的个体之间也是有差异的。
需要保证此次排序之前相等值的原始顺序。需要使用稳定的排序算法。
使用归并排序。
5.2 若数组比较短，<60
使用插入排序。
虽然它是，但是常数项极低，在元素个数小的情况下，非常有效。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！