Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

算法

发布于：Sep 4, 2026

算法封面

简单选择排序

思路

  1. 把数组分成两部分：前面是已排序部分，后面是未排序部分。
  2. 一开始，已排序部分为空，未排序部分是整个数组。
  3. 每一轮，从未排序部分里找到最小的数，设中间量为k，记录最小值的下标。
  4. 根据下标把这个最小的数和未排序部分的第一个数交换。
  5. 重复上面的过程，直到未排序部分只剩一个元素为止。

代码实现

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
50
51
52
53
54
55
#include <stdio.h>

// 打印数组
void printArray(int *arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", *(arr + i));
    }
    printf("\n");
}

// 选择排序
void selectionSort(int *arr, int n)
{
    // i 表示未排序部分的第一个元素的下标
    for (int i = 0; i < n - 1; i++)
    {
        // 先假设未排序部分的第一个元素是最小的
        int minIndex = i;

        // 从 i + 1 开始，在未排序部分里找真正的最小值
        for (int j = i + 1; j < n; j++)
        {
            if (*(arr + j) < *(arr + minIndex))
            {
                minIndex = j;
            }
        }

        // 如果最小值不在 i 位置，就交换
        if (minIndex != i)
        {
            int temp = *(arr + i);
            *(arr + i) = *(arr + minIndex);
            *(arr + minIndex) = temp;
        }
    }
}

int main()
{
    int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前：");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("排序后：");
    printArray(arr, n);

    return 0;
}

运行结果

1
2
排序前：5 3 8 4 2 7 1 6
排序后：1 2 3 4 5 6 7 8

直接插入排序

思路

  1. 把数组分成两部分：前面是已排序部分，后面是未排序部分。
  2. 一开始，已排序部分只有第一个元素。
  3. 从第二个元素开始，依次取出当前元素，当作“待插入的值”，将待插入的值用中间量key保存。
  4. 在已排序部分里，从后往前找合适的位置。
  5. 如果已排序部分里的元素比待插入的值大，就把它往后挪一位。
  6. 找到合适位置后，把待插入的值放进去。
  7. 重复上面的过程，直到所有元素都插入完成。

代码实现

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
50
51
52
#include <stdio.h>

// 打印数组
void printArray(int *arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", *(arr + i));
    }
    printf("\n");
}

// 插入排序
void insertionSort(int *arr, int n)
{
    // i 表示当前要插入的元素的下标
    // 从第二个元素开始，因为第一个元素默认已经排好
    for (int i = 1; i < n; i++)
    {
        // 保存当前要插入的值
        int key = *(arr + i);

        // j 表示已排序部分的最后一个元素的下标
        int j = i - 1;

        // 从后往前找，如果已排序部分的元素比 key 大，就往后挪
        while (j >= 0 && *(arr + j) > key)
        {
            *(arr + j + 1) = *(arr + j);
            j--;
        }

        // 把 key 放到空出来的位置
        *(arr + j + 1) = key;
    }
}

int main()
{
    int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前：");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("排序后：");
    printArray(arr, n);

    return 0;
}

运行结果

1
2
排序前：5 3 8 4 2 7 1 6
排序后：1 2 3 4 5 6 7 8

冒泡排序

思路

  1. 从第一个元素开始，比较相邻的两个元素。
  2. 如果前一个比后一个大，就交换它们。
  3. 继续比较下一对，直到这一轮结束。这一轮结束后，最大的数会跑到最后。
  4. 重复上面的过程，每轮都会把当前未排序部分最大的数放到后面。
  5. 一共进行 n - 1 轮，数组就有序了。

代码实现

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
50
51
#include <stdio.h>

// 打印数组
void printArray(int *arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", *(arr + i));
    }
    printf("\n");
}

// 冒泡排序
void bubbleSort(int *arr, int n)
{
    int i, j;
    int temp;

    // 一共需要 n - 1 轮
    for (i = 0; i < n - 1; i++)
    {
        // 每一轮比较相邻两个元素
        // 后面 i 个元素已经排好了，不用再比较
        for (j = 0; j < n - 1 - i; j++)
        {
            // 如果前一个比后一个大，就交换
            if (*(arr + j) > *(arr + j + 1))
            {
                temp = *(arr + j);
                *(arr + j) = *(arr + j + 1);
                *(arr + j + 1) = temp;
            }
        }
    }
}

int main()
{
    int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前：");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("排序后：");
    printArray(arr, n);

    return 0;
}

运行结果

1
2
排序前：5 3 8 4 2 7 1 6
排序后：1 2 3 4 5 6 7 8

快速排序

思路

  1. 选枢轴
    在当前要排序的区间里，随便选一个数当枢轴。
    这里选最左边的数：pivot = *left;
    选完后，left 这个位置就相当于一个“坑”。
  2. 确定 left 和 right
    left 指向当前区间的第一个元素。
    right 指向当前区间的最后一个元素。
  3. 用两个指针从两边往中间走
    i 从左边开始往右走。
    j 从右边开始往左走。
  4. 循环填坑
    从右往左找，找到第一个小于枢轴的数，把它填到左边的坑里，然后 i 往右移。
    从左往右找，找到第一个大于枢轴的数，把它填到右边的坑里，然后 j 往左移。
  5. 枢轴归位
    把一开始保存的 pivot 填到 i 和 j 相遇的位置。
    此时，枢轴左边都比它小，右边都比它大。
  6. 递归左右两边
    对枢轴左边的区间再做一次快速排序。
    对枢轴右边的区间再做一次快速排序。

代码实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>

// 打印数组
void printArray(int *arr, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 快速排序
void quickSort(int *left, int *right)
{
    // 如果区间没有元素，或者只有一个元素，就不排序
    if (left >= right)
        return;

    // 1. 选枢轴，保存起来（选最左边的数保存起来）
    int pivot = *left;

    // 2. 确定两个指针
    int *i = left;  // i 从左往右走
    int *j = right; // j 从右往左走

    // 3. 开始填坑
    while (i < j)
    {
        // 从右往左找，找到第一个小于枢轴的数
        while (i < j && *j >= pivot)
            j--;

        // 找到后，把它填到左边的坑里
        if (i < j)
        {
            *i = *j;
            i++;
        }

        // 从左往右找，找到第一个大于枢轴的数
        while (i < j && *i <= pivot)
            i++;

        // 找到后，把它填到右边的坑里
        if (i < j)
        {
            *j = *i;
            j--;
        }
    }

    // 4. 枢轴归位，此时 i 和 j 相遇，把枢轴填到相遇位置
    *i = pivot;

    // 5. 递归排序左边和右边
    quickSort(left, i - 1);
    quickSort(i + 1, right);
}

int main()
{
    int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前：");
    printArray(arr, n);

    // arr 是第一个元素的地址，arr + n - 1 是最后一个元素的地址
    quickSort(arr, arr + n - 1);

    printf("排序后：");
    printArray(arr, n);

    return 0;
}

运行结果

1
2
排序前：5 3 8 4 2 7 1 6
排序后：1 2 3 4 5 6 7 8

堆排序

思路

堆（Heap）是满足以下两个条件的完全二叉树：

  1. 结构条件：是一棵完全二叉树；
  2. 堆序条件：
    • 大顶堆：父节点 ≥ 左右孩子（堆顶是最大值）
    • 小顶堆：父节点 ≤ 左右孩子（堆顶是最小值）
      升序排序用大顶堆，降序排序用小顶堆。
      堆是逻辑上的二叉树，物理上用数组存储，不需要指针建树。

从下标 1 开始：数组与树的关系

  • 数组开 n + 1 个；
  • arr[0] 不使用（空着或当哨兵）；
  • 有效元素为 arr[1] ~ arr[n]。
    设当前节点下标为 i：
    关系 公式
    父节点 i / 2（整数除法）
    左孩子 2 * i
    右孩子 2 * i + 1
    最后一个非叶子节点 n / 2
    第一个叶子节点 n / 2 + 1

堆排序整体思路

  1. 建大顶堆
    从最后一个非叶子节点 n / 2 开始，倒着到 1，依次对每个节点执行 heapify（向下调整）：

    1
    2
    for (int i = n / 2; i >= 1; i--)
        heapify(arr, n, i);

    为什么从 n / 2 开始？
    下标大于 n / 2 的节点全是叶子节点，叶子节点没有孩子，天然满足堆性质，无需调整。
    调整完后，整个数组满足大顶堆性质，arr[1] 就是全局最大值。

  2. 排序（反复取堆顶）
    循环 i 从 n 递减到 2：

    1. 交换 arr[1]（堆顶，当前最大值）与 arr[i]（堆的最后一个元素）；
    2. 交换后 arr[i] 已经是本轮的最终位置，堆的大小减为 i - 1；
    3. 对新的堆顶元素 arr[1] 执行 heapify(arr, i - 1, 1)，恢复大顶堆；
    4. 重复直到堆中只剩一个元素。
    1
    2
    3
    4
    5
    for (int i = n; i > 1; i--)
    {
        swap(&arr[1], &arr[i]);
        heapify(arr, i - 1, 1);
    }

    循环结束后，arr[1..n] 就是升序序列。

核心操作：heapify（向下调整）

含义：假设以 i 为根的左右子树已经是大顶堆，只调整以 i 为根的子树，使其重新成为大顶堆。
步骤：

  1. 令 largest = i；
  2. 若左孩子 2i <= n 且 arr[2i] > arr[largest]，则 largest = 2i；
  3. 若右孩子 2i + 1 <= n 且 arr[2i + 1] > arr[largest]，则 largest = 2i + 1；
  4. 若 largest != i，交换 arr[i] 与 arr[largest]，并递归/迭代对 largest 位置继续操作；
  5. 若 largest == i，说明 i 已经是三者最大，停止。
    递归版：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void heapify(int arr[], int n, int i)
{
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

    if (left <= n && arr[left] > arr[largest])
        largest = left;
    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

迭代版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void heapify(int arr[], int n, int i)
{
    while (1)
    {
        int largest = i;
        int left = 2 * i;
        int right = 2 * i + 1;

        if (left <= n && arr[left] > arr[largest])
            largest = left;
        if (right <= n && arr[right] > arr[largest])
            largest = right;

        if (largest == i)
            break;

        swap(&arr[i], &arr[largest]);
        i = largest;
    }
}

代码实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>

// 交换两个整数
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 打印 arr[1..n]
void printArray(int arr[], int n)
{
    for (int i = 1; i <= n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 向下调整：使以 i 为根的子树成为大顶堆
// 有效元素为 arr[1..n]，arr[0] 不使用
void heapify(int arr[], int n, int i)
{
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

    if (left <= n && arr[left] > arr[largest])
        largest = left;
    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序（升序）
// arr[1..n] 是有效元素，arr[0] 不用
void heapSort(int arr[], int n)
{
    // 1. 建大顶堆：从最后一个非叶子节点 n/2 到 1
    for (int i = n / 2; i >= 1; i--)
        heapify(arr, n, i);

    // 2. 依次把堆顶最大值放到末尾，再恢复堆
    for (int i = n; i > 1; i--)
    {
        swap(&arr[1], &arr[i]);
        heapify(arr, i - 1, 1);
    }
}

int main()
{
    int arr[] = {0, 12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]) - 1;   // 实际元素个数

    printf("排序前：");
    printArray(arr, n);

    heapSort(arr, n);

    printf("排序后：");
    printArray(arr, n);

    return 0;
}

运行结果

1
2
排序前：12 11 13 5 6 7
排序后：5 6 7 11 12 13

更新于：Sep 17, 2026

评论