锐客网

  1. 首页 > 生活百科 > it技术 > >

堆排序最优java代码 堆排序程序( 三 )

IT技术排序


sorted[k+1]=tempB;
}
}
}
}
public void QuickExchangeSortBackTrack(double [] sorted,
int low,int high){
if(lowhigh){
int pivot= findPivot(sorted,low,high);
QuickExchangeSortBackTrack(sorted,low,pivot-1);
QuickExchangeSortBackTrack(sorted,pivot+1,high);
}
}
public int findPivot(double [] sorted, int low, int high){
sorted[0]= sorted[low];
while(lowhigh){
while(lowhighsorted[high]= sorted[0])--high;
sorted[low]= sorted[high];
while(lowhighsorted[low]=sorted[0])++low;
sorted[high]= sorted[low];
}
sorted[low]=sorted[0];
return low;
}
public static void main(String[] args) {
Random random= new Random(6);
int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
ExchangeSort sorter=new ExchangeSort();
//sorter.BubbleExchangeSort(sorted);
sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize-1);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
6）选择排序：
分为直接选择排序，堆排序
直接选择排序：第i次选取 i到array.Length-1中间最小的值放在i位置 。
堆排序：首先，数组里面用层次遍历的顺序放一棵完全二叉树 。从最后一个非终端结点往前面调整，直到到达根结点，这个时候除根节点以外的所有非终端节点都已经满足堆得条件了 ， 于是需要调整根节点使得整个树满足堆得条件，于是从根节点开始 ， 沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆沿着最小的儿子走） 。主程序里面，首先从最后一个非终端节点开始调整到根也调整完 ， 形成一个heap ，  然后将heap的根放到后面去（即：每次的树大小会变化 ， 但是 root都是在1的位置，以方便计算儿子们的index ， 所以如果需要升序排列 ， 则要逐步大顶堆 。因为根节点被一个个放在后面去了 。降序排列则要建立小顶堆）
代码中的问题： 有时候第2个和第3个顺序不对（原因还没搞明白到底代码哪里有错）
选择排序Java代码：
public class SelectionSort {
public void straitSelectionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=1;jsortedLen;j++){
int jMin= getMinIndex(sorted,j);
exchange(sorted,j,jMin);
}
}
public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(isortedLenjsortedLeniji=0j=0){
double temp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}
public int getMinIndex(double [] sorted, int i){
int sortedLen= sorted.length;
int minJ=1;
double min= Double.MAX_VALUE;
for(int j=i;jsortedLen;j++){
if(sorted[j]min){
min= sorted[j];
minJ= j;
}
}
return minJ;
}
public void heapAdjust(double [] sorted,int start,int end){
if(startend){
double temp= sorted;
//这个地方jend与课本不同 ， j=end会报错：
for(int j=2*start;jend;j *=2){
if(j+1endsorted[j]-sorted[j+1]10e-6){
++j;
}
if(temp=sorted[j]){
break;
}
sorted=sorted[j];
start=j;
}
sorted=temp;
}
}
public void heapSelectionSort(double [] sorted){
int sortedLen = sorted.length;
for(int i=sortedLen/2;i0;i--){
heapAdjust(sorted,i,sortedLen);
}
for(int i=sortedLen;i1;--i){

推荐阅读


上一篇：怎么用绳索连接队友手机，怎么用绳索连接队友手机游戏

下一篇：消防现在直播素材下载，消防直播视频