06.选择类排序法（树形选择排序，堆排序）
参考网页：
选择类排序法
基本思想：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
1. 简单选择排序
基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行n-1趟比较，直到所有记录排序完成为止。
时间效率：O(n2)——虽移动次数较少，但比较次数仍多。
空间效率：O(1)——1个附加单元。
算法的稳定性：不稳定
void selectSort(Node[] nodes) {
Node temp;
int k = 0,i = 0,j =0;
for(i = 0;i<nodes.length;i++) {
k = i;
for(j = i +1;j<nodes.length;j++) {
if(nodes[j].key < nodes[k].key) {
k = j;
}
}
if(k != j ) {
temp = nodes[i];
nodes[i] = nodes[k];
nodes[k] = temp;
}
}
}
2. 树型选择排序
树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。
基本思想：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在n/2 个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。
public class TreeSelectSort {
public static int[] TreeSelectionSort(int[] mData) {
int TreeLong = mData.length * 4;
int MinValue = -10000;
int[] tree = new int[TreeLong]; // 树的大小
int baseSize;
int i;
int n = mData.length;
int max;
int maxIndex;
int treeSize;
baseSize = 1;
while (baseSize < n) {
baseSize *= 2;
}
treeSize = baseSize * 2 - 1;
for (i = 0; i < n; i++) {
tree[treeSize - i] = mData[i];
}
for (; i < baseSize; i++) {
tree[treeSize - i] = MinValue;
}
// 构造一棵树
for (i = treeSize; i > 1; i -= 2) {
tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
}
n -= 1;
while (n != -1) {
max = tree[1];
mData[n--] = max;
maxIndex = treeSize;
while (tree[maxIndex] != max) {
maxIndex--;
}
tree[maxIndex] = MinValue;
while (maxIndex > 1) {
if (maxIndex % 2 == 0) {
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
: tree[maxIndex + 1]);
} else {
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
: tree[maxIndex - 1]);
}
maxIndex /= 2;
}
}
return mData;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
TreeSelectionSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
}
算法分析：
被选中的关键字都是走了一条由叶子结点到根结点的比较的过程,由于含有n个叶子节点的完全二叉数的深度为log2n +1，则在树型选择排序中，每选择一个小关键字需要进行log2n次比较，因此其时间复杂度为O(nlog2n)。移动记录次数不超过比较次数，故总的算法时间复杂度为O(nlog2n)。
3. 堆排序
堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记录大小的辅助空间。堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析而已。
堆的含义：完全二叉树的所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。若系列是堆，则堆顶元素必定为序列中n个元素的最小值（或最大值）。
具体做法：
把待排序的记录的关键字存放在数组r[1..n]之中，将r看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r[1]作为二叉树的根，以下各记录r[2...n]依次逐层从左到右顺序排列，任意结点r[i]的左孩子是r[2i],右孩子是r[2i+1],双亲是r[i/2]。对这棵完全二叉树进行调整，使各结点的关键字值满足下列条件：
r[i].key≥r[2i].key并且r[i].key≥r[2i+1].key(i=1,2, ...n/2 )，
满足这个条件的完全二叉树为堆。
image.png
堆排序二叉树图
image.png
堆排序方块图
堆排序的过程主要需要解决两个问题：
(1) 按堆定义建初堆
一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆，因而可以反复利用“筛选”法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆。
（2）去掉最大元之后重建堆，得到次大元。
- 将堆顶元素和最后一个元素互换，此时根结点的左右子树均为大顶堆
- 若根结点存在左右子树，则比较根结点和左右子树根结点的值，否则调整结束，跳到步骤1
- 若根结点值依旧均大于左右子树的根结点的值，则跳转到第1步执行
- 否则将根结点和左右子树根结点较大值互换，跳转到第2步，以被交换的子树的根结点作为第2步根结点执行
public class HeapSort {
// 交换两个位置
void swap(Node[] nodes, int n, int m) {
Node temp;
temp = nodes[n];
nodes[n] = nodes[m];
nodes[m] = temp;
}
//堆排序的主函数
void heapSort(Node arr[], int count) {
//从下往上构建初始堆
//从根节点的上一层结点开始向上遍历
for (int i = count / 2 - 1; i >= 0; i--) {
shiftDown(arr, count, i);
}
//从上往下调整堆，构建大根堆（循环每进行一次，都会把最大元素交换到堆顶）
for (int j = count - 1; j > 0; j--) {
swap(arr, 0, j); //将堆顶元素与待排序的堆末元素交换
shiftDown(arr, j, 0); //抛去大根堆最后一个元素，对前面元素进行建堆
}
}
//arr是待排序数组，count是未排序的个数，在count下标往后的已经排好序，
//currentRoot当前的种子下标
//作用：构建大根堆
void shiftDown(Node[] arr, int count, int currentRoot) {
int max;
while (2 * currentRoot + 1 < count) { //该种子有左子树
max = 2 * currentRoot + 1; //默认他的左孩子为最大值
if (max + 1 < count && arr[max + 1].key > arr[max].key) {
//如果他的右孩子也在未排序序列，并且右孩子比左孩子大，让右孩子为最大值
max = max + 1;
}
if (arr[currentRoot].key >= arr[max].key) {
//如果种子结点的值大于或等于左右孩子最大值，就退出循环
break;
}
swap(arr, currentRoot, max); //否则，就让种子结点和他的左右孩子的最大结点交换
currentRoot = max; //并且将种子下标换成最大结点下标，进行下一轮循环
}
}
}
堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。
堆排序是一种不稳定的排序方法，
它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。
网友评论