排序算法之堆排序及Java实现 傷城~ 2022-05-26 04:47 178阅读 0赞 ## 一、排序算法的分类 ## 1. 选择排序([直接选择排序][Link 1],[堆排序][Link 2]) 2. 交换排序([冒泡排序][Link 3],[快速排序][Link 4]) 3. 插入排序([直接插入排序][Link 5],[希尔排序][Link 6]) 4. [归并排序][Link 7] 5. 桶式排序 6. 基数排序 ## 二、堆排序的原理 ## 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序。堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。 它的基本思想是将待排序的序列构造成一个大顶堆(或小顶堆)。此时,整个序列的最大值就是堆顶的根节点,将其与堆数组的末尾元素交换,此时末尾元素就是最大值,然后将剩余的 n-1 个序列重新构造成一个最大堆,再将新的最大堆的顶与末尾元素交换,如此反复执行,便能得到一个有序序列了。 ![这里写图片描述][70] ## 三、堆排序的实现 ## 堆排序中重要的一个部分是不断调整堆使其满足最大堆的性质,即父节点都比子节点的值大。调整最大堆的算法如下所示,输入为一个数组A和一个下标i,它用来维护以下标i为根结点的子树最大堆的性质,通过让A\[i\]的值在最大堆中“逐级下降”,从而使得以下标i为结点的子树重新遵循最大堆的性质。 ![这里写图片描述][70 1] 之后用置底向上的方法利用MAX-HEAPIFY把一个大小为n=A.length的数组A\[1~n\]转化为最大堆。算法如下所示,原理很简单,就是从倒数第2层开始,调用MAX-HEAPFY方法,直至到根结点。 ![这里写图片描述][70 2] 最后是取出最大值的算法,也就说将最大堆的顶值与最后一个节点值交换,这样最后一个节点就变成了最大值,再将前n-1个值重新进行最大堆排序。算法如下所示,首先将待排序的数组构建为最大堆数组,之后遍历整棵树,每次遍历“取出”根结点,再调用MAX-HEAPIFY维护子树的最大堆性质。这样就能保证遍历时每次“取出”的元素是当前剩余元素中最大的。 ![这里写图片描述][70 3] 实现代码如下所示: public class HeapSort { public static void heapSort(int[] arr){ buildMaxHeap(arr); int heapSize = arr.length; //最大值的节点与最后一个节点交换位置 for (int i = arr.length - 1; i > 0; i--) { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //最后一个节点为最大值后,再对前边节点进行堆排序,每交换出一个最大值,最大堆的大小减1 heapSize--; maxHeapify(arr, 0, heapSize); } } /** * 4 3 9 5 10 2 6 * 0 1 2 3 4 5 6 * * 4 * 3 9 * 5 10 2 6 * * @param arr 待排序的数组 * @param index 要进行调整的节点位置 * @param heapSize 最大堆的大小 */ public static void maxHeapify(int[] arr, int index, int heapSize) { int leftIndex = 2 * index + 1;//左节点 int rightIndex = 2 * index + 2; int largeIndex;//临时存储三个节点中最大的节点 if (leftIndex < heapSize && arr[leftIndex] > arr[index]) { largeIndex = leftIndex; } else { largeIndex = index; } if (rightIndex < heapSize && arr[rightIndex] > arr[largeIndex]) { largeIndex = rightIndex; } if (largeIndex != index) { //与最大值的节点交换位置 int temp = arr[largeIndex]; arr[largeIndex] = arr[index]; arr[index] = temp; //递归的方式对新的节点进行最大堆调整 maxHeapify(arr, largeIndex, heapSize); } } //建立最大堆,遍历其中的非叶子节点,调整位置,达到最大堆的特点,即父节点的值大于子节点的值 public static void buildMaxHeap(int[] arr) { int heapSize = arr.length; for (int i = (arr.length - 2) / 2; i > -1; i--) { maxHeapify(arr, i, heapSize); } } public static void main(String args[]){ int[] test = { 4,3,9,5,10,2,6}; heapSort(test); for(int i=0; i<test.length; i++){ System.out.print(test[i] + " "); } } } 测试结果: 2 3 4 5 6 9 10 [Link 1]: https://blog.csdn.net/xdzhouxin/article/details/80017538 [Link 2]: https://blog.csdn.net/xdzhouxin/article/details/80079195 [Link 3]: https://blog.csdn.net/xdzhouxin/article/details/80017719 [Link 4]: https://blog.csdn.net/xdzhouxin/article/details/80031668 [Link 5]: https://blog.csdn.net/xdzhouxin/article/details/80024190 [Link 6]: https://blog.csdn.net/xdzhouxin/article/details/80070031 [Link 7]: https://blog.csdn.net/xdzhouxin/article/details/80070839 [70]: /images/20220526/3bdc1cd7d6b44257b3839af04dd72153.png [70 1]: /images/20220526/fcaf6b50b61e4a018440f197bdb74366.png [70 2]: /images/20220526/eddae993bf3641e0ad9a05ddd9485840.png [70 3]: /images/20220526/eafd7407ecb94edb9a1c37c24ed09ad6.png
还没有评论,来说两句吧...