1 排序原理
具体什么是堆排序请自行查阅,不在此博客内容,本实例使用原地堆排序,先将数组建成一个最大堆,再将堆顶元素取出放在数组末尾。
2 实现
/**
* 对数组进行原地堆排序
* @author xld
*
*/
public class HeapSort {
/**
* 原地堆排序
* @param arr
*/
public static void sort(
int[] arr){
int n= arr.length;
/**
* 创建最大堆
* 注意:索引是从0开始的
* (最后一个元素索引-1)/2开始
* 最后一个元素索引=n-1
*
*/
for(
int i=(n-
1-
1)/
2;i>=
0;i--){
shiftDown(arr,n,i);
}
/**
* 将最大元素取出
* 存放在数组末尾
*/
for(
int i=n-
1;i>
0;i--){
swap(arr,
0,i);
shiftDown(arr,i,
0);
}
}
/**
* 交换元素
* @param arr
* @param i
* @param j
*/
private static void swap(
int[]arr,
int i,
int j){
int temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
/**
* 使用赋值的方式进行排序
* 用一次赋值代替了交换操作
* @param arr
* @param n
* @param k
*/
private static void shiftDown(
int[] arr,
int n,
int k){
int e = arr[k];
while(
2*k+
1<n){
int j=
2*k+
1;
if(j+
1<n &&arr[j+
1]>arr[j])
j++;
if(e>arr[j])
break;
arr[k]=arr[j];
k=j;
}
arr[k]=e;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
int[] arr = {
10,
9,
8,
7,
6,
5,
4,
3,
2,
1 ,
12};
HeapSort.sort(arr);
for (
int i =
0; i < arr.length; i++) {
System.out.print(arr[i]);
System.out.print(
' ');
}
System.out.println();
}
}