}

}

树选择排序（Tree Selection Sort）

树选择排序算法相对于简单选择排序来说是典型的以空间换时间的算法。其思想是对待排序的 N 个元素 , 构造出相对较小的 （n+1）/2个数，然后再构造出相对较小的[n+1]/4个数，直到只有一个元素为止。构造成一个完全二叉树。 排序的时候，那个元素就是最小的，取出该最小元素，将该元素替换为"最大值",再调整完全二叉树。

下面是树形选择排序的一个Java实现版：

public static void treeSelectionSort（int[] data） {

if （data == null || data.length <= 1）

return;

int len = data.length , low = 0 , i , j;

// add Auxiliary Space

int[] tmp = new int[2*len -1];

int tSize = tmp.length;

//construct a tree

for（i =len-1 , j=tmp.length-1;i >=0 ;i--,j--）{

tmp[j]=data[i];

}

for（i = tSize -1 ; i > 0 ; i-=2）{

tmp[（i-1）/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];

}

//end