堆排序

图解堆排序

堆排序是什么

堆排序的步骤

  1. 将无序数组就地交换，堆化为最大堆
  2. 将堆顶元素与末尾元素交换，将最大元素沉到数组末端；
  3. 重复步骤 1 和 2，直到整个数组有序

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 构造小顶堆
void adjustHeap(int s[], int n, int cur)
{
    int tmp = s[cur];
    // 从 cur 的左子节点开始
    for (int i = 2 * cur + 1; i < n; i = i * 2 + 1)
    {
        // 如果存在右子节点且右子节点更小
        if (i + 1 < n && s[i + 1] < s[i])
        {
            i++;
        }

        // 找到左右节点中最小的元素与当前元素交换
        if (tmp > s[i])
        {
            s[cur] = s[i]; // 暂时不需要处理最初被交换的那个
            cur = i; // 以同样的方法处理子节点
        }
        else
        {
            // 如果当前元素比子节点都小，满足条件，退出
            break;
        }
    }

    s[cur] = tmp;
}

void heapSort(int s[], int n)
{
    // 步骤 1：建堆
    // 从第一个非叶子结点从下至上，从右至左调整结构
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        adjustHeap(s, n, i);
    }

    // 步骤 2：交换元素，重新调整堆
    for (int i = n - 1; i > 0; i--)
    {
        swap(s[0], s[i]);
        adjustHeap(s, i, 0);
    }
}

复杂度

  1. 建堆的复杂度是 O(N)
  2. 交换 N 次，调整的复杂度为 O(logN)

所以堆排序复杂度为：O(NlogN)

建堆时间复杂度为什么是 O(N)

应用

找出无序数组中位数，要求O(N)复杂度

找出无序数组中第 K 大元素

考虑 K = 1 的时候如何处理，K = 2、3 呢？最终会考虑到最大堆的建立

  1. 图解堆排序
  2. 堆排序的步骤
  3. 代码
  4. 复杂度
  5. 应用
    1. 找出无序数组中位数，要求O(N)复杂度
    2. 找出无序数组中第 K 大元素