树形选择排序的实现
/**第04讲-树形选择排序_写出树形选择排序的实现
*
一般而言，我们不会直接使用树形选择排序到实际工程中。因为这种方法需要额外的存储空间来建树。
但这种排序方法不失为练习逻辑能力的好机会；同时它也是堆排序思想的基础。
请写出树形选择排序的实现。
注意：
1. 树形的表达，未必使用真正的二叉树来表达，完全二叉树的父节点与孩子节点的序号有固定关系。用数组就可以了。
2. 根节点输出后，如何处理？寻找其值来源？很麻烦！可不可以在树的节点中不要存储值，只存待排序数组的元素序号？
*/
package cn.itcast.sort;
public class SelectSort {
/**
* 实现原理：
* 第一步，首先对n个记录进行两两比较，得到较小的n/2个数再依次比较，依次类推
* 直到得到一个最小值,这是一个构造完全二叉树的过程，根节点即为最小元素，叶子节点为列表元素。
* 构造的此树的存储结构可以用数组表示方法，数组长度为2n-1。填充此树，比如
* 列表元素为：49 38 65 97 76 13 27 49
* 构造的树为： 13
* 38 13
* 38 65 13 27
* 19 38 65 97 76 13 27 49
* 13为根结点位最小值，列表元素为叶子节点
*
* 第二步，移走最小元素，此时可重新为数组a的第一个位置赋值为此最小值，
* 之后如果找出次小值则可以为第二个位置赋值，......
*
* 第三步，找出次小值，找出最小值在叶子节点的位置，从该节点开始，和其兄弟节点
* 进行比较，修改从叶子节点到根节点的元素值，比较完毕后，根节点为次小值。
* 第三步比较是利用了第一次比较提供的信息，因为第一步已经得到了两两比较的
* 较小值，只要拿第一次与最小值比较的元素(即最小值的兄弟节点)与它们比较即可得最小值。
* 即拿上述例子的76与27比较，然后27与38比较得到次小值27。
* 重复第二和第三步，排序完成。
*
*/
//这里传递过来的是一个Integer类型的数组
public static void treeSelectSort(Object[] a){
int len = a.length;
int treeSize = 2 * len - 1; //完全二叉树的节点数
int low = 0;
//临时的树存储空间 ，所以我们不会直接使用树形选择排序到实际工程中
Object[] tree = new Object[treeSize];
//由后向前填充此树，索引从0开始
for(int i = len-1,j=0 ;i >= 0; --i,j++){
//填充叶子节点，treeSize-1是最后一个节点
tree[treeSize-1-j] = a[i];
}
//填充非终端节点
for(int i = treeSize-1;i>0;i-=2){
tree[(i-1)/2] = ((Comparable)tree[i-1]).compareTo(tree[i]) < 0 ? tree[i-1]:tree[i];
}
//不断移走最小节点
int minIndex;
while(low < len){
Object min = tree[0]; //最小值
a[low++] = min;
minIndex = treeSize-1;
//找到最小值的索引
while(((Comparable)tree[minIndex]).compareTo(min)!=0){
minIndex--;
}
tree[minIndex] = Integer.MAX_VALUE; //设置一个最大值标志
//找到其兄弟节点
while(minIndex > 0){
//如果其还有父节点
//如果是右节点 ,左节点minIndex-1与右节点minIndex比较
if(minIndex % 2 == 0){
tree[(minIndex-1)/2] = ((Comparable)tree[minIndex-1]).compareTo(tree[minIndex])
< 0 ? tree[minIndex-1]:tree[minIndex];
minIndex = (minIndex-1)/2;
}else{
//如果是左节点 ，左节点minIndex与右节点minIndex+1比较
tree[minIndex/2] = ((Comparable)tree[minIndex]).compareTo(tree[minIndex+1])
< 0 ? tree[minIndex]:tree[minIndex+1];
minIndex = minIndex/2;
}
}
}
}
public static void main(String[] args) {
Integer[] data = {49,38,65,97,76,13,27,49};
SelectSort.treeSelectSort(data);
for(Integer d:data){
System.out.println(d);
}
}
}
输出结果：
