堆排序

本页面将简要介绍堆排序。

简介

堆排序（英语：Heapsort）是指利用 堆 这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。

工作原理

它的工作原理为对所有待排序元素建堆，然后依次取出堆顶元素，就可以得到排好序的序列。

当当前的结点下标为 i 时，父结点、左子结点和右子结点的选择方式如下：

1
2
3
4
//这里 floor 函数将实数映射到最小的前导整数。
iParent(i) = floor((i - 1) / 2);
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;

性质

稳定性

堆排序是一种不稳定的排序算法。

时间复杂度

堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 O(n\log n) 。

代码实现

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void max_heapify(int arr[], int start, int end) {
  // 建立父结点指标和子结点指标
  int dad = start;
  int son = dad * 2 + 1;
  while (son <= end) {  // 子结点指标在范围内才做比较
    if (son + 1 <= end &&
        arr[son] < arr[son + 1])  // 先比较两个子结点大小，选择最大的
      son++;
    if (arr[dad] >
        arr[son])  // 如果父结点比子结点大，代表调整完毕，直接跳出函数
      return;
    else {  // 否则交换父子内容，子结点再和孙结点比较
      swap(arr[dad], arr[son]);
      dad = son;
      son = dad * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // 初始化，i 从最后一个父结点开始调整
  for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1);
  // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    max_heapify(arr, 0, i - 1);
  }
}

外部链接

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论