【排序算法】之堆排序

堆排序的基本思想是：

具体可看视频演示：堆排序

- 1、将带排序的序列构造成一个大（小）顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素； buildHeap(); - 2、将堆顶元素和最后一个元素交换交换一次，i--一次，然后将剩下的节点重新构造成一个大顶堆； swap() + buildHeap() - 3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。 heapSort(); 代码演示 /** * 堆排序 对简单选择排序的优化 */ public class HeapSort { //堆排序 public static void heapSort(int[] arr) { if (arr == null || arr.length == 0) { return; } int len = arr.length; //1.构件大顶堆,把数组变成一个大顶堆结构的数组； //要知道数组的长度 buildHeap(arr, len); //2.交换堆顶元素与末尾元素 剩下的元素重新构成一个大顶堆 for (int i = len - 1; i >= 0; i--) { //每交换一次末位位置要-1 //4. swap(arr, 0, i); len--; //每次调整的时候默认len-1；因为每次最后位置的数就是我们所求得最大的 heapify(arr, 0, len); } } //3.heapify真正用来调整大顶堆的方法 /** * @param arr 待整理的数组 * @param i 每次整理时候，当前非叶子节点的位置 * @param len 每次整理数组时，节点的个数 */ private static void heapify(int[] arr, int i, int len) { if (i>=len){ return; } //给了一个非叶子节点i的位置 我们首先找到它的两个孩子 int left = 2 * i + 1; int right = 2 * i + 2; int max = i;//假设父节点i是最大值的位置 //下面进行判断找到最大值所在的节点位置 同时要保证节点不会越界 if (left < len && arr[left] > arr[max]) { max = left; } if (right < len && arr[right] > arr[max]) { max = right; } //找出最大值后就进行交换 if (max!=i){ // 如果最大值位置不是当前非叶子节点的位置，那么就把当前节点和最大值的子节点值互换 swap(arr, i, max); // 因为互换之后，子节点的值变了，该子节点可能也有自己的子节点，仍需要再次调整。 heapify(arr, max,len); } } //1.构造大顶堆 private static void buildHeap(int[] arr) { // 从最后一个非叶节点开始向前遍历，调整节点，使整个数组成为大顶堆 //数组的长度/2 - 1 就是：第一个非零节点的位置 int n=arr.length; for (int i = n / 2 - 1; i >= 0; i--) { //3. heapify(arr, i, n); } } //4.交换元素 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr={23,45,1,5,67,88,99,9,2,3}; heapSort(arr); for (int res : arr) { System.out.print(res+" "); } } }