选择排序原理及Java实现

欢迎进入Java社区论坛，与200万技术人员互动交流 >>进入

　　下面是树形选择排序的一个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

　　//remove the minimum node.

　　while（low < len）{

　　data[low++] = tmp[0];

　　for（j=tSize-1;tmp[j]!=tmp[0];j–）；

　　tmp[j] = Integer.MAX_VALUE;

　　while（j > 0）{

　　if（j%2 == 0）{ //如果是右节点

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

　　j = （j-1）/2;

　　}else{ //如果是左节点

　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];

　　j = j/2;

　　}

　　在构造完全二叉树的时候对 N 个元素的集合，需要 2*N -1 个辅助空间。

　　代码：