【Java -- 算法】十大排序算法之堆排序

简介

堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O(1)， 最坏时间复杂度为O(nlog2n) ，堆排序的堆序的平均性能较接近于最坏性能。

算法步骤

创建一个堆H[0…n-1]

把堆首（最大值）和堆尾互换

把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

重复步骤2，直到堆的尺寸为1

实例

1. Java 代码

public class Main {
public static void main(String[] args) {
int[] sort ={3,2,1,4,6,5,8,9,10,7} ;
System.out.println("排序前：");
printArray(sort);
heapSort(sort);
System.out.println("\n排序后：");
printArray(sort);
}

public static void printArray(int[] a) {
for (int i = 0;i < a.length;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}

public static void heapSort(int[] a){
int len = a.length;
for (int i = 0;i < len ;i++) {
sink(a,len-1-i);
exch(a,0,len-1-i);

}


}

/**
* 创建堆算法
*/
public static void sink(int[] a,int lastIndex) {
for(int i = (lastIndex-1)/2;i >= 0;i--) {
int k = i;
while(2 * k + 1 <= lastIndex) {
int bigIndex = 2*k+1;
if(bigIndex < lastIndex) {
if(a[bigIndex] < a[bigIndex + 1]) {
bigIndex++;
}
}

if(a[k] < a[bigIndex]) {
exch(a,k,bigIndex);
k = bigIndex;
}else {
break;
}
}
}
}

/**
* 交换两元素
*/
public static void exch(int[] a,int i,int j) {
if(i == j) {
return;
}
a[i] = a[i] + a[j];
a[j] = a[i] - a[j];
a[i] = a[i] - a[j];

}

}

2. 输出结果