堆排序算法-附Java示例

堆排序是基于比较排序的技术,类似于选择排序,先找到最大/小元素,将最大/小元素放在最后,重复这个过程直到全部有序。

堆数的功能有限,但被大量使用,常用于快速查找数组中,第k个最小或最大元素(统计),或按最大/最小优先级处理的场景(优先级队列)。

定义

"堆/heap"不是特指某个数据结构,而是泛指满足堆属性的任何数据结构。

堆中某个子节点的值总是不大于,或不小于其父节点的值。根节点存放最大值的堆叫最大堆/大根堆,存放最小值的堆叫最小堆/小根堆。

特点

堆排序的最坏、最好、平均时间复杂度均为O(nlogn),是不稳定排序算法。

注:稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面;不稳定指,如果a=b,a在b的前面,排序后可能会交换位置。

排序算法

利用数组快速定位的特点,通过指定索引元素,基于数组进行堆排序。

堆排序

找出数组中最大元素,根元素array[1]是数组中最大元素,先将该元素与数组中最后一个元素交换(最大堆),然后,将数组的长度减少1,以便将已处于正确位置的元素排除在堆外。重复这个过程,随着下标范围的收缩,可遍历的数组长度越来越短,直到完成排序。

排序过程

步骤1:用5替换8。

步骤2:8与堆断开连接,因为8现在已处于正确位置。

步骤3:构建大根堆,用3替换7。

步骤4:7与堆断开连接。

第5步:构建大根堆,用1替换5。

步骤6:5与堆断开连接。

步骤7:构建大根堆,用3替换4。

步骤8:4与堆断开连接。

步骤9:构建大根堆,用1替换3。

步骤10:3断开连接。

堆排序

堆排序

Java示例

package com.xieyonghui.art;

public class HeapSort {

  public static void main(String args[]) {
    int arr[] = {4, 3, 7, 1, 8, 5};
    int n = arr.length;
    // 初始化堆
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);

    //排序
    for (int i = n - 1; i >= 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      heapify(arr, i, 0);
    }
    // 打印结果
    printArray(arr);
  }

  static void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化根
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // left > root
    if (l < n && arr[l] > arr[largest])
      largest = l;

    // right > root
    if (r < n && arr[r] > arr[largest])
      largest = r;

    // 如果最大值不是根节点,调整
    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;

      // heapify
      heapify(arr, n, largest);
    }
  }
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
  }
}