堆排序的基本思想:将待排序的序列构造成一个大顶堆.此时,真个序列的最大值就是堆顶的根节点.将它移走(其实就是将其与堆数组的末尾元素进行交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会跟到n个元素中的次小值.如此反复执行,便能得到一个有序序列了.
下面分别用递归与非递归的方式实现之.
核心代码:
非递归:
// 堆化, 即建堆 public static void heapify(int[] data, int start, int end){ // 跟节点为i, 则i节点的左子节点的下标为2*i+1, 右子节点的下标为2*i+2 int temp = data[start]; for(int i=2*start+1; i<=end; i=2*i+1){ if(i<end && data[i]<data[i+1]){ // 比较左右节点值的大小 i++; } if(temp > data[i]){ break; // 说明当前当前节点的值比左右子节点的值都要大,循环结束 } // 走到这一步,说明跟节点的值不为最大值,要进行调整, 将最大值赋值给根节点 data[start] = data[i]; start = i; // 交换之后破坏了堆的特性, 应该继续调整 } data[start] = temp; }递归:
// 堆化, 建堆 public static void heapify(int[] data, int start, int end){ int left = 2 * start + 1; // 根节点的左节点 int right = 2 * start + 2; // 根节点的右节点 int maxIndex = start; // 假设当前根节点即为最大值 if(left<=end && data[left]>data[maxIndex]){ //左子节点与最大值的比较 maxIndex = left; } if(right<=end && data[right] > data[maxIndex]){ // 右与大的比较 maxIndex = right; } if(maxIndex != start){ // 如果根节点不为最大值 swap(data, start, maxIndex); heapify(data, maxIndex, end); } }
完整代码:
非递归:
package cn.ccnu.sort; public class Heap { // 堆化, 即建堆 public static void heapify(int[] data, int start, int end){ // 跟节点为i, 则i节点的左子节点的下标为2*i+1, 右子节点的下标为2*i+2 int temp = data[start]; for(int i=2*start+1; i<=end; i=2*i+1){ if(i<end && data[i]<data[i+1]){ // 比较左右节点值的大小 i++; } if(temp > data[i]){ break; // 说明当前当前节点的值比左右子节点的值都要大,循环结束 } // 走到这一步,说明跟节点的值不为最大值,要进行调整, 将最大值赋值给根节点 data[start] = data[i]; start = i; // 交换之后破坏了堆的特性, 应该继续调整 } data[start] = temp; } public static void heapSort(int[] data){ // 将现在的待排序列构建成一个大顶堆 for(int i=data.length/2; i>=0; i--){ heapify(data, i, data.length-1); } // 逐步将大顶堆的堆顶元素与末尾元素进行交换, 并再次将其调整为大顶堆 for(int j=data.length-1; j>=0; j--){ swap(data, 0, j); heapify(data, 0, j-1); } } private static void swap(int[] data, int i, int j) { int temp = data[i]; data[i] = data[j]; data[j] = temp; } public static void main(String[] args) { int[] data = {10, 3, 12, 5, 4, 9, 4, 7, 6, 2, 11, 8, 15}; heapSort(data); for (int i : data) { System.out.print(i + " "); } } } 递归:
package cn.ccnu.sort; public class HeapTwo { // 堆化, 建堆 public static void heapify(int[] data, int start, int end){ int left = 2 * start + 1; // 根节点的左节点 int right = 2 * start + 2; // 根节点的右节点 int maxIndex = start; // 假设当前根节点即为最大值 if(left<=end && data[left]>data[maxIndex]){ //左子节点与最大值的比较 maxIndex = left; } if(right<=end && data[right] > data[maxIndex]){ // 右与大的比较 maxIndex = right; } if(maxIndex != start){ // 如果根节点不为最大值 swap(data, start, maxIndex); heapify(data, maxIndex, end); } } public static void heapSort(int[] data){ for(int i=data.length/2; i>=0; i--){ heapify(data, i, data.length-1); } for(int i=data.length-1; i>=0; i--){ swap(data, 0, i); heapify(data, 0, i-1); } } private static void swap(int[] data, int a, int b) { int temp = data[a]; data[a] = data[b]; data[b] = temp; } public static void main(String[] args) { int[] data = {10, 3, 12, 5, 4, 9, 4, 7, 6, 2, 11, 8, 15}; heapSort(data); for (int i : data) { System.out.print(i + " "); } } }
