堆排序算法-Java示例代码图解

堆排序是基于比较排序的技术,堆排序类似于选择排序,首先,找到最大元素并将最大元素放在最后,然后,对剩余元素重复这个过程。

堆排序的最坏、最好、平均时间复杂度均为O(nlogn),所以它是不稳定排序。堆分为大顶堆和小顶堆,是完全二叉树。每个结点的值都大于或等于,其左右孩子结点的值,则为大顶堆。每个结点的值都小于或等于,其左右孩子结点的值,为小顶堆。

可以利用数组快速定位的特点,通过指定索引的元素,基于数组进行堆排序。在大顶堆中,最大元素总是在根节点,利用堆的这个特性,对数组进行排序。例如:有一个数组,我们用堆排序的概念对它进行排序。

堆排序

首先,在数组中构建一个大顶堆(概念),如下图所示:

堆排序

根元素array[1](图1),它是array中最大的元素。然后,将该元素与array的最后一个元素交换。将已处于正确位置的元素(最后一个),排除到堆外,然后将堆的长度减少1,再组织最大堆。重复步骤2,直到所有元素都处于正确的位置。

构建大顶堆,数组中元素位置变换过程:

步骤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] + " ");
  }
}