Java排序算法(三)
已经满足堆得条件了，于是需要调整根节点使得整个树满足堆得条件，于是从根节点开始，沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆沿着最小的儿子走）。主程序里面，首先从最后一个非终端节点开始调整到根也调整完，形成一个heap， 然后将heap的根放到后面去（即：每次的树大小会变化，但是 root都是在1的位置，以方便计算儿子们的index，所以如果需要升序排列，则要逐步大顶堆。因为根节点被一个个放在后面去了。降序排列则要建立小顶堆）
代码中的问题：有时候第2个和第3个顺序不对（原因还没搞明白到底代码哪里有错）
选择排序Java代码：
public class SelectionSort {
public void straitSelectionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=1;j
int jMin=getMinIndex(sorted,j);
exchange(sorted,j,jMin);
}
}
public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(i=0 &&j>=0){
doubletemp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}
public int getMinIndex(double [] sorted, int i){
int sortedLen= sorted.length;
int minJ=1;
doublemin= Double.MAX_VALUE;
for(int j=i;j
if(sorted[j]
min= sorted[j];
minJ= j;
}
}
returnminJ;
}
public void heapAdjust(double [] sorted,int start,int end){
if(start
doubletemp= sorted[start];
// 这个地方j
for(int j=2*start;j
if(j+110e-6){
++j;
}
if(temp<=sorted[j]){
break;
}
sorted[start]=sorted[j];
start=j;
}
sorted[start]=temp;
}
}
public void heapSelectionSort(double [] sorted){
int sortedLen = sorted.length;
for(int i=sortedLen/2;i>0;i--){
heapAdjust(sorted,i,sortedLen);
}
for(int i=sortedLen;i>1;--i){
exchange(sorted,1,i);
heapAdjust(sorted,1,i-1);
}
}
public static void main(String [] args){
Random random= new Random(6);
int arraysize=9;
double[] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;j
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
SelectionSort sorter=new SelectionSort();
// sorter.straitSelectionSort(sorted);
sorter.heapSelectionSort(sorted);
System.out.print("After Sort:");
for(int j=1;j
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
7）归并排序：
将两个或两个以上的有序表组合成一个新的有序表。归并排序要使用一个辅助数组，大小跟原数组相同，递归做法。每次将目标序列分解成两个序列，分别排序两个子序列之后，再将两个排序好的子序列merge到一起。
归并排序Java代码：
public class MergeSort {
private double[] bridge;//辅助数组
public void sort(double[] obj){
if (obj == null){
throw new NullPointerException("
The param can not be null!");
}
bridge = new double[obj.length];// 初始化中间数组
mergeSort(obj, 0, obj.length - 1); //归并排序
bridge = null;
}
private void mergeSort(double[] obj, int left, int right){
if (left < right){
int center = (left +right) / 2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(