一、什么是选择排序？
1. 选择排序的主要思想是每一趟从待排序列中选取一个关键字值最小的记录，也即第1趟从n个记录中选取关键字最小的记录，在第2趟中，从剩下的n-1个记录中选取关键字值最小的记录，直到整个序列中的记录都选完位置，这样，由选取记录的顺序便可得到按关键字有序的排序。
2. 常见的三种选择排序方式：
直接选择排序
树形选择排序
堆排序
二、堆排序
堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
1）概述
堆排序是一种重要的选择排序方法，它只需要一个记录大小的辅助存储空间，每个待排序的记录仅占用一个记录大小的存储空间，因此弥补了树形选择排序的弱点。
大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
一般升序采用大顶堆，降序采用小顶堆
2）示意图
大顶堆：
小顶堆：
3）算法分析
基本思想：
1. 首先将这n条记录按关键字值的大小建立堆（称为初始堆），将堆顶元素r[0]与r[n-1]交换
2. 然后，将剩下的{r[0]..r[n-2]}序列调整成堆
3. 再将 r[0]与r[n-2]交换，再将剩下的{r[0]..r[n-3]}序列调整成堆
4. 如此反复，直到整个序列有序。
5. 这个过程称为堆排序
要实现堆排序需解决以下两个主要问题：
1. 将n条记录的序列按关键字值的大小建成初始堆。
2. 将堆顶记录r[0]与r[i]交换后，如何将序列{r[0]..r[i-1]}按其关键字值的大小调整成一个新堆。
4）筛选法调整堆：分析
将给定无序序列构造成一个小顶堆，调整过程如下：
1. 假设给定无序序列结构如下，且该序列已经是小顶堆：
2. 然后交换堆顶元素和最后一个元素，从而筛选出整个序列中的最小值（13）
3. 然后将剩余的无序序列调整成小堆顶，先从根的左右孩子[25,18]中选择最小值18，然后根与最小孩子比较，并保证根为最小值[18]
4. 然后继续调整下一层，选择出[63,95,46]中的最小值46
5. 此时，我们就将一个无需序列构造成了一个小顶堆。
6）筛选法调整堆：算法
代码
//【算法】将以筛选法调整堆算法 //将以low为根的子树调整成小顶堆，low、high是序列下界和上界 public void sift(int low, int high) { int i = low; //子树的根 int j = 2 * i + 1; //j为i结点的左孩子 RecordNode temp = r[i]; while (j < high) { //沿较小值孩子结点向下筛选 if (j < high - 1 && r[j].key.compareTo(r[j + 1].key) > 0) { j++; //数组元素比较,j为左右孩子的较小者 } if (temp.key.compareTo(r[j].key) > 0) { //若父母结点值较大 r[i] = r[j]; //孩子结点中的较小值上移 i = j; j = 2 * i + 1; } else { j = high + 1; //退出循环 } } r[i] = temp; //当前子树的原根值调整后的位置 // System.out.print("sift " + low + ".." + high + " "); // display(); }
测试
public class TestSeqList11_sift { public static void main(String[] args) throws Exception { int[] arr = {13,25,18,33,58,95,46,63}; SeqList seqList = new SeqList(arr.length); System.out.print("序列号:"); for (int i = 0; i < arr.length; i++) { System.out.print(" " + i); seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); System.out.print("原数据："); seqList.display(); // 树形选择排序(锦标赛排序) RecordNode temp = seqList.r[0]; seqList.r[0] = seqList.r[arr.length - 1]; seqList.r[arr.length-1] = temp; System.out.print("交换值："); seqList.display(); seqList.sift(0, arr.length-1); System.out.print("调整后："); seqList.display(); } } //树形选择排序(锦标赛排序) //序列号: 0 1 2 3 4 5 6 7 //原数据： 13 25 18 33 58 95 46 63 //交换值： 63 25 18 33 58 95 46 13 //调整后： 18 25 46 33 58 95 63 13
7）建初始堆：分析
为一个无序序列构建堆的过程，就是对完全二叉树从下往上反复筛选的过程。也就是说每一个结点与自己的孩子结点进行比较，从而选择出最小元素。
有孩子的结点，称为非叶子结点，在完全二叉树中，最后一个非叶子结点的编号为 ⌊n/2⌋ -1
因此我们从最后一个非叶子结点开始调整，最后调整到根节点
//序列号: 0 1 2 3 4 5 6 7
//sift 3..8 33 25 46 13 58 95 18 63
//sift 2..8 33 25 18 13 58 95 46 63
//sift 1..8 33 13 18 25 58 95 46 63
//sift 0..8 13 25 18 33 58 95 46 63
8）堆排序：分析
步骤：
首先通过对 ⌊n/2⌋ -1记录进行调整，构建堆。
然后将堆顶的元素，与最后一个元素交换，获得最小元素。
接着将剩余无序序列，调整成小顶堆，重复步骤2，获得每一次调整后的最小值
直到调整到根，从而获得排序序列
9）堆排序：算法
代码
//【算法】 堆排序算法 public void heapSort() { // System.out.println("堆排序"); int n = this.curlen; RecordNode temp; // 从最后一个非叶子节点开始调整堆，直到根结点 for (int i = n / 2 - 1; i >= 0; i--) {//创建堆 sift(i, n); } System.out.println("堆构建完成"); for (int i = n - 1; i > 0; i--) {//每趟将最小值交换到后面，再调整成堆 // 第一个元素和无序中的最后一个交换 temp = r[0]; r[0] = r[i]; r[i] = temp; sift(0, i); } }
测试
public class TestSeqList12_heap { public static void main(String[] args) throws Exception { int[] arr = {33,25,46,13,58,95,18,63}; SeqList seqList = new SeqList(arr.length); System.out.print("序列号:\t\t"); for (int i = 0; i < arr.length; i++) { System.out.print(" " + i); seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); // 树形选择排序(锦标赛排序) seqList.heapSort(); } } //树形选择排序(锦标赛排序) //序列号: 0 1 2 3 4 5 6 7 //sift 3..8 33 25 46 13 58 95 18 63 //sift 2..8 33 25 18 13 58 95 46 63 //sift 1..8 33 13 18 25 58 95 46 63 //sift 0..8 13 25 18 33 58 95 46 63 //堆构建完成 //sift 0..7 18 25 46 33 58 95 63 13 //sift 0..6 25 33 46 63 58 95 18 13 //sift 0..5 33 58 46 63 95 25 18 13 //sift 0..4 46 58 95 63 33 25 18 13 //sift 0..3 58 63 95 46 33 25 18 13 //sift 0..2 63 95 58 46 33 25 18 13 //sift 0..1 95 63 58 46 33 25 18 13
10）性能分析
- 空间复杂度：需要一个记录辅助存储空间，O(1)
- 最坏时间复杂度：O(nlog2n)
- 堆排序是==不稳定==的排序算法。
11）练习
使用堆排序，写出每一趟的排序结果
序列：16, 15, 50, 53, 64, 7
