要求：

给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。

代码实现：

看老师演示:

说明：

  • 堆排序不是很好理解，老师通过Debug 帮助大家理解堆排序
  • 堆排序的速度非常快，在我的机器上 8百万数据 3 秒左右。O(nlogn)

    代码

    核心方法

    ```

/**

  • 将一个数组(二叉树) 调整成一个大顶堆 *
  • 方法的功能: 完成,当我们传递了,
  • “ 将以i对应的非叶子节点的树调整成大顶堆
  • 举例: int arr[] = {4,6,8,5,9} => i =1 ==>
  • adjustHeap => 得到 {4,9,8,5,6}
  • 如果我们再次调用 adjustHeap 传入的是i =0 ==>
  • adjustHeap 得到{4,9,8,5,6}=> {9,6,8,5,4}
  • @param arr
  • @param i 表示非叶子节点在 数组中的索引
  • @param lenght 表示对多少个元素进行调整, length 是在逐渐减少 / public static void adjustHeap(int arr[], int i,int lenght) { int temp = arr[i]; // 先取出当前元素的值,保存在临时变量 // 开始调整 // /*
    • 说明:
    • 1.k代表的是以i为非叶子节点的左子节点
    • k = i 2 + 1 中k是i节点的左子节点 / for (int k = i 2 + 1; k < lenght; k=k2+1) { // 找i的柚子节点大还是左子节点大 if (arr[k] < arr[k + 1] && k+1 < lenght) {
      1.  // 说明左子节点的值 小于 右子节点的值
      2.  k++;    //让k指向右子节点
      3.  // k 指向i这个下面的 较大的 子节点
      } // 现在这个k已经指向了,右子节点后者左子节点最大的值 if (arr[k] > temp) {
      1.  // 如果子节点大于父节点temp
      2.  arr[i] = arr[k];    // 把较大的值赋给当前的节点
      3.  i = k;      // 让i指向k,继续循环比较
      } else {
      1.  // 这里!!!!
      2.  // 因为这个地方我是 从左至右 从上至下 调整的
      3.  break;
      } } // 当for循环结束后,我们己经将以i为父节点的树的最大值,放在了最顶上的位置 // 局部(以i为父节点的)吧这个树调整成了大顶堆 // 调整完后i不是原来的i了,i是调整中的当前的i arr[i] = temp; // 将temp值放到调整后的位置 // 这里因为前面 是将子节点中大数字和父节点的数字换了顺序,现在 // 父节点原来的数字他不能丢了,所以用temp又给到arr[i]

}

  1. ## 堆排序的方法

/**

  • 编写一个堆排序的方法
  • @param arr */ public static void heapSort(int arr[]) { System.out.println(“堆排序!”); // 分步完成 adjustHeap(arr, 1, arr.length); System.out.println(“第一次”+ Arrays.toString(arr)); // {4,9,8,5,6} }
  1. ## 主方法

public static void main(String[] args) { /**

  1.  * 要求,吧一个
  2.  *
  3.  * ??? 如何将一个给定的数组,
  4.  * 以一个大顶堆的方式来搞出来
  5.  */
  6. int arr[] = {4, 6, 8, 5, 9};
  7. heapSort(arr);
  8. /*
  9. * 堆排序!
  10. 第一次[4, 9, 8, 5, 6]
  12. Process finished with exit code 0
  13. * */

}

  1. ## 运行

堆排序! 第一次[4, 9, 8, 5, 6]

Process finished with exit code 0

  1. # 调整第二次
  2. ## 这次全了就

/**

  • 编写一个堆排序的方法
  • @param arr */ public static void heapSort(int arr[]) { System.out.println(“堆排序!”); // 分步完成 adjustHeap(arr, 1, arr.length); System.out.println(“第一次”+ Arrays.toString(arr)); // {4,9,8,5,6} adjustHeap(arr, 0, arr.length); System.out.println(“第二次”+ Arrays.toString(arr)); }
  1. ## 运行

堆排序! 第一次[4, 9, 8, 5, 6] 第二次[9, 6, 8, 5, 4]

Process finished with exit code 0

  1. ![哔哩哔哩动画](https://cdn.nlark.com/yuque/0/2021/png/2460262/1635357300795-f7479ad6-d07f-451e-890c-d57f2c5d62ad.png)
  3. > 然后,我不可能每次都写一遍一遍的
  5. > 所以,
  8. ## 循环

/**

  • 编写一个堆排序的方法 *

  • @param arr */ public static void heapSort(int arr[]) { System.out.println(“堆排序!”);

    // 4, 6, 8, 5, 9 for (int i = arr.length / 2-1; i >= 0; i—) {

    1.  adjustHeap(arr, i, arr.length);
    2.  System.out.println("第"+(arr.length / 2-1-i)+"次" + Arrays.toString(arr));

    } }

  1. # 完整代码

``` img