堆排序

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]; //当k存在孩子节点的时候 进行操作 while(2*k+1<n){ int j=2*k+1; //如果当前节点的右孩子节点存在，并且大于左孩子节点 j++ //此举保证了j指向k子节点的最大节点 if(j+1<n &&arr[j+1]>arr[j]) j++; //如果e大于子节点 证明e找到了其适当的位置 结束循环 if(e>arr[j]) break; //将子节点上移 arr[k]=arr[j]; //将当前比较位置下移 k=j; } //将e赋值到其适当位置 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(); } }