admin 管理员组

文章数量: 1086019

java堆排序算法

java堆排序算法

排序思想
1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

  • 注意:
    • 升序用大根堆，降序就用小根堆(默认为升序)
    • 堆排序是不稳定的排序，空间复杂度为O(1),平均的时间复杂度为O(nlogn),最坏情况下也稳定在O(nlogn)

代码示例:

public class HeapSort {public static void main(String[] args) {int arr[] = { 555, -3, 7, 62, 54, 10, 86, 2, 5, -6, 9, 24 };System.out.println("排序前" + Arrays.toString(arr));heapSort(arr);System.out.println("排序后" + Arrays.toString(arr));}public static void heapSort(int array[]) {// 构建一个大顶堆，从array.length/2 - 1 最后一个非叶子结点开始for (int i = array.length / 2 - 1; i >= 0; i--) {adjustHeap(array, i, array.length);}for (int len = array.length - 1; len > 0; len--) {// 大顶堆的根元素与数组末尾元素交换int temp = array[0];array[0] = array[len];array[len] = temp;// 交换后的末尾元素忽略(len--) 不再参与堆结构的调整// 重新调整堆结构adjustHeap(array, 0, len);}}/*** 完成将以i对应的非叶子结点的树调整成大顶堆*/public static void adjustHeap(int[] array, int i, int length) {// 先把当前元素取出来，因为当前元素可能要一直移动int temp = array[i];// 2*i+1表示结点i的左子树for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {if (k + 1 < length && array[k] < array[k + 1]) {k++;// 让k先指向子节点中最大的节点}if (array[k] > temp) {// 如果发现结点(左右子结点)大于根结点，则进行值的交换array[i] = array[k];// 把较大的值赋值给父节点// array[k] = temp; // 这里没必要换i = k;// 子结点更换了，以子结点为根的子树会受到影响，指针移向子节点，循环对子结点所在的树继续进行判断} else {break;// 不用交换，直接终止循环}}array[i] = temp;// 将temp值放到最终的位置}}

参考：

  • 堆排序（超详细图解 java版）
  • 堆排序_百度百科
    /%E5%A0%86%E6%8E%92%E5%BA%8F/2840151
  • java实现10种排序算法
  • 十大经典排序算法总结
  • 堆排序及复杂度分析

本文标签： java堆排序算法

版权声明：本文标题：java堆排序算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686561757a10546.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。