堆排序?
public class HeapSort {
public static void heapSort(int[] a){
if(a == null){
throw new RuntimeException("输入数组");
}
int len = a.length;
for(int i = len/2-1;i>=0;i--){
createHeap(a,i,len);
}
for(int j = a.length-1;j>0;j--){
swap(a,0,j);
createHeap(a,0,j);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//构建大顶堆
private static void createHeap(int[] a,int i,int len) {
int father = a[i];
int j = 2i+1;//j代表子结点坐标 i代表父结点坐标
while(j < len){
if(j + 1 < len && a[j] < a[j+1] )
j++;
if(a[j] > father){
a[i] = a[j];
i = j;
}else {
break;
}
j = 2*i+1;
}
//找到最终位置
a[i] = father;
}
//构建小顶堆
public static void createMinHeap(int[] a,int i,int length){
int father = a[i];
int j = 2*i + 1;
while (j < length){
if(j+1 < length && a[j] > a[j+1]){
j++;
}
if(a[j] < father){
a[i] = a[j];
i = j;
}else {
break;
}
j = 2*i+1;
}
a[i] = father;
}
public static void main(String[] args){
int[] a = {1,1,1};
HeapSort.heapSort(a);
System.out.println(Arrays.toString(a));
}
}
近期评论