堆排序

发表于 更新于 分类于 Waline： 阅读次数：

研究了一下堆排序，还挺有趣，记录一下。

原理：

  1. 首先把待排序的数组放入堆中，然后构建大顶堆。
  2. 讲堆顶元素（最大元素）和最后一个元素交换，把最后一个元素脱离堆结构。
  3. 重复步骤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
46
47
48
49
#include <stdio.h>

#define MAXITEM 100

// 构建大顶堆
void Heapify(int R[MAXITEM], int v, int n) {
    int i, j;
    i = v;
    j = 2 * i;

    R[0] = R[i];
    while (j <= n) {
        if (j < n && R[j] < R[j + 1]) {
            j++;
        }
        if (R[0] < R[j]) {
            R[i] = R[j];
            i = j;
            j = 2 * i;
        } else {
            j = n + 1;
        }
    }
    R[i] = R[0];
}

// 堆排序
void HeapSort(int R[MAXITEM], int n) {
    int i;
    for (i = n / 2; i >= 1; i--) {
        Heapify(R, i, n);
    }
    for (i = n; i >= 2; i--) {
        R[0] = R[i];
        R[i] = R[1];
        R[1] = R[0];
        Heapify(R, 1, i - 1);
    }
}

int main(void) {
    int R[] = {0, 12, 29, 8, 17, 1, 5, 24, 3, -2, 6};
    HeapSort(R, 10);

    for (int i = 1; i < 11; i++) {
        printf("%d ", R[i]);
    }
    return 0;
}