中值排序的java实现

public class MidSort {
public static void main(String[] args){
int[] arr={,,,,,,,,};
midSort(arr,,);
for(int i:arr){
System.out.print(i + " ");
}
System.out.println();
} //返回数组被中值分成两堆后中值所在位置
public static int partition(int[] goal,int left,int right,int midPos){//left和right是为位置指示，表明你要排序的是
// 数组的那部分,否则要把待排序的数组切割出来
int mid=goal[midPos];
int tmp,idx;
//把中值移到数组末尾
tmp=goal[right];
goal[right]=goal[midPos];
goal[midPos]=tmp; int smallPos=left;//指向比中值小的，每当有比中值小的数把它放入smallPos所指地方，然后smallPos+1，这样保证
//smallPos指过的位置都放着比中值小的（也就是在最前面的那些）
for(idx=left;idx<right;idx++){
if(goal[idx]<mid){//每当有比中值小的数把它放入smallPos所指地方,从而把小于中值的移到前面去
tmp=goal[idx];
goal[idx]=goal[smallPos];
goal[smallPos]=tmp;
smallPos++;
}
}
//把中值放回它应该在的位置
tmp=goal[right];
goal[right]=goal[smallPos];
goal[smallPos]=tmp;
return smallPos;//返回中值所在位置
} //因为选值来作为中值是随机的（有时是以第一个来作为），所以被分成两堆的数组可能不均衡，所有找出第k（此时k=（length+1）/2）
// 便使分堆后的数组平衡了）大的元素的位置
public static int selectKth(int[] goal,int left,int right, int k){//返回第K大元素
int midPos=selectMidPos(goal,left,right);//返回作为中值的为元素的位置，若是选数组第一个作为中值时有时会让性能
//退化成O(n的平方)（如它是最大、小值时，分堆后会有一堆为空），要避免
//会在数组中随机选一个作为中值
int pos=partition(goal,left,right,midPos);//数组被中值分成两堆后中值所在位置
if(pos==k+left-){//说明真正想要作为分堆的中值恰好就是之前选定分堆的中值
return pos;
}else if(k+left-<pos){//小于，如k是第4大，之前是第3大，所以小于,继续分堆直到返回k为止因为此时数组才按k作为中值来分堆
//所以第K大元素在在之前分好堆中的左边那堆,它在这堆是第k-pos大
return selectKth(goal,left,pos-,k);
}else{//大于，所以第K大元素在在之前分好堆中的右边那堆,它在这堆是第k大
return selectKth(goal,pos+,right,k-(pos-left+));
}
} public static void midSort(int[] goal,int left,int right){
if (left>=right)return;//如果只有一个元素或更少
int mid=(right-left+)/;
int midPos=selectKth(goal,left,right,mid+);//得到能把数组分为平均两堆的中值的位置且此时已分好堆
midSort(goal,left,left+mid-); //对左边这堆继续分堆
midSort(goal,left+mid+,right); //对右边这堆继续分堆
} public static int selectMidPos(int[] goal,int left,int right){
//随机选定中值
int distant =right-left+;
int random=(int)Math.round(Math.random()*distant);
int pos=random+left<=right?random+left:random+left-;
return pos; }}