Java实现堆排序经典代码和算法思路

本文重点讲解Java实现堆排序经典代码和算法思路。

简介

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序是一种基于比较的排序算法，它的基本思想是将待排序的元素构建成一个堆，然后依次将堆顶元素取出，放到已排序的序列中，直到堆中所有元素都被取出，最终得到一个有序的序列。

什么是堆

堆排序算法思路

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

堆排序的基本步骤

构建堆：将待排序的元素构建成一个堆，可以使用数组来表示堆，数组中下标为 i 的元素的左子节点下标为 2i+1，右子节点下标为 2i+2。

取出堆顶元素：将堆顶元素取出，放到已排序的序列中。

调整堆：将剩余的元素重新构建成一个堆，然后重复步骤 2 和步骤 3，直到堆中所有元素都被取出。Java代码实现堆排序

构建大顶堆实现堆排序：

public class HeapSort { //声明全局变量，用于记录数组array的长度； static int len; public static void main(String[] args) { int[] arr={3,7,2,9,1,4,6,8,10,5}; HeapSort(arr); System.out.println("交换后："+ Arrays.toString(arr)); } /** * 堆排序算法 * * @param array * @return */ public static int[] HeapSort(int[] array) { len = array.length; if (len < 1) return array; //1.构建一个最大堆 buildMaxHeap(array); //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆 while (len > 0) { swap(array, 0, len - 1); len--; adjustHeap(array, 0); } return array; } /** * 建立最大堆 * * @param array */ public static void buildMaxHeap(int[] array) { //从最后一个非叶子节点开始向上构造最大堆 for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1) adjustHeap(array, i); } } /** * 调整使之成为最大堆 * * @param array * @param i */ public static void adjustHeap(int[] array, int i) { int maxIndex = i; //如果有左子树，且左子树大于父节点，则将最大指针指向左子树 if (i * 2 < len && array[i * 2] > array[maxIndex]) maxIndex = i * 2; //如果有右子树，且右子树大于父节点，则将最大指针指向右子树 if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) maxIndex = i * 2 + 1; //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。 if (maxIndex != i) { swap(array, maxIndex, i); adjustHeap(array, maxIndex); } } /** * 交换数组内两个元素 * @param array * @param i * @param j */ public static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } }

小顶堆实现堆排序：

public class SmailHeap { public static void main(String[] args) { int[] array = new int[]{1,3,2,7,4,0,5,10}; heapSort(array); System.out.println(Arrays.toString(array)); } private static void heapSort(int[] array) { for (int i = array.length / 2 - 1; i >= 0; i--) { adjustHeap(array,i,array.length); } for (int j = array.length - 1; j >= 0; j--) { int temp = array[0]; array[0] = array[j]; array[j] = temp; adjustHeap(array,0,j); } } private static void adjustHeap(int[] array, int i, int len) { int temp = array[i]; for (int k = i * 2 + 1; i < len; k = 2 * k + 1) { if (k + 1 < len && array[k] > array[k + 1]) { k++; } if (k<len && array[k] < temp) { array[i] = array[k]; i = k; } else { break; } } array[i] = temp; } }