排序算法入门

概念说明

排序算法的目标是把一组无序数据按升序或降序重新排列。
它是学习 C 语言时非常典型的综合练习，因为会把数组、循环、条件判断、函数、指针和临时空间管理串到一起。

C语言中文网的排序教程不只讲冒泡排序。
它还继续介绍了选择排序、插入排序、希尔排序、归并排序和快速排序，并且归并排序、快速排序都给出了迭代版与递归版思路。

学习这些排序的重点，不只是“把代码背下来”。
更重要的是理解每种排序靠什么维持局部有序、什么时候需要交换、什么时候需要移动元素，以及它们在时间复杂度、额外空间和稳定性上的差异。

语法/规则

排序函数通常接收两个参数：数组首元素地址和数组长度，因为函数内部无法直接知道传入数组原本有多长。
冒泡排序、选择排序、插入排序都属于基础的 O(n^2) 排序，适合教学和小规模数据处理。
希尔排序是插入排序的改进版，它通过“分组 + 缩小增量”减少元素移动次数。
归并排序使用分治思想，先拆分，再合并，时间复杂度通常是 O(n log n)，但需要额外辅助数组。
快速排序通常也能达到 O(n log n) 的平均性能，但如果基准选择不合适，最坏情况会退化到 O(n^2)。
归并排序和快速排序都可以写成递归版，也可以改写成显式栈或分段循环驱动的迭代版。
稳定排序会尽量保持“相等元素的原始先后顺序”；冒泡、插入、归并通常是稳定的，选择、希尔、快速通常不是。
写排序时最容易出错的地方是循环边界、分区边界、辅助数组长度和递归终止条件。

常见排序可以先按下面这张表建立整体印象：

算法	核心思路	平均时间复杂度	额外空间	稳定性
冒泡排序	相邻比较，较大元素逐步冒到后面	`O(n^2)`	`O(1)`	稳定
选择排序	每轮选最小值，再放到当前起始位置	`O(n^2)`	`O(1)`	不稳定
插入排序	维护前缀有序区，把新元素插进去	`O(n^2)`	`O(1)`	稳定
希尔排序	按增量分组做插入排序	依赖增量序列	`O(1)`	不稳定
归并排序	先分解再合并	`O(n log n)`	`O(n)`	稳定
快速排序	分区后分别处理左右两侧	`O(n log n)`	递归栈或显式栈	不稳定

示例

下面各个示例都使用同一组数据：

1
7 12 17 29 41 45 53 65 71 84 88 96

为了便于和原网站内容对照，下面分别补全每一种排序的最小可运行示例。

冒泡排序

冒泡排序会反复比较相邻元素。
如果前一个比后一个大，就交换它们。每完成一轮，当前未排序区间里最大的元素就会被“冒”到末尾。

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

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void bubble_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    bubble_sort(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

选择排序

选择排序每一轮都会在未排序区间里找一个最小值。
找到后，把这个最小值交换到当前轮的起始位置。

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

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void selection_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            int temp = arr[min_index];
            arr[min_index] = arr[i];
            arr[i] = temp;
        }
    }
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    selection_sort(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

插入排序

插入排序会维护一个“前面已经有序”的区间。
每次取出一个新元素，把它插入到前面合适的位置，同时把较大的元素整体后移。

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

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void insertion_sort(int arr[], int len) {
    for (int i = 1; i < len; i++) {
        int current = arr[i];
        int j = i;

        while (j > 0 && arr[j - 1] > current) {
            arr[j] = arr[j - 1];
            j--;
        }

        arr[j] = current;
    }
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    insertion_sort(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

希尔排序

希尔排序可以看作“带增量的插入排序”。
它先按较大的间隔把元素分组排序，再逐步缩小间隔，直到间隔为 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
#include <stdio.h>

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void shell_sort(int arr[], int len) {
    for (int gap = len / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < len; i++) {
            int temp = arr[i];
            int j = i;

            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }
    }
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    shell_sort(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

归并排序（迭代法）

归并排序的迭代版不会递归拆分数组。
它会从长度为 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

void merge_sort_iterative(int arr[], int len) {
    int *temp = malloc((size_t)len * sizeof(int));
    if (temp == NULL) {
        return;
    }

    for (int size = 1; size < len; size *= 2) {
        for (int left = 0; left < len - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = left + 2 * size - 1;

            if (right >= len) {
                right = len - 1;
            }

            merge(arr, left, mid, right, temp);
        }
    }

    free(temp);
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    merge_sort_iterative(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

归并排序（递归法）

归并排序的递归版更符合“分治”本来的表达方式。
它会先递归处理左半部分和右半部分，再把两段有序数组合并起来。

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

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void merge(int arr[], int left, int mid, int right, int temp[]) {
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

void merge_sort_recursive_impl(int arr[], int left, int right, int temp[]) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;
    merge_sort_recursive_impl(arr, left, mid, temp);
    merge_sort_recursive_impl(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

void merge_sort_recursive(int arr[], int len) {
    int *temp = malloc((size_t)len * sizeof(int));
    if (temp == NULL) {
        return;
    }

    merge_sort_recursive_impl(arr, 0, len - 1, temp);
    free(temp);
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    merge_sort_recursive(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

快速排序（迭代法）

快速排序的关键是“分区”。
它会选一个基准值，把小于基准的元素放左边，大于基准的元素放右边。迭代版不会递归调用，而是用显式栈记录后续还要处理的区间。

 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
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Range;

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int partition(int arr[], int start, int end) {
    int pivot = arr[end];
    int i = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[end];
    arr[end] = temp;
    return i + 1;
}

void quick_sort_iterative(int arr[], int len) {
    Range *stack;
    int top = -1;

    if (len <= 1) {
        return;
    }

    stack = malloc((size_t)len * sizeof(Range));
    if (stack == NULL) {
        return;
    }

    stack[++top] = (Range){0, len - 1};

    while (top >= 0) {
        Range current = stack[top--];
        int start = current.start;
        int end = current.end;

        if (start >= end) {
            continue;
        }

        int pivot_index = partition(arr, start, end);

        if (pivot_index - 1 > start) {
            stack[++top] = (Range){start, pivot_index - 1};
        }
        if (pivot_index + 1 < end) {
            stack[++top] = (Range){pivot_index + 1, end};
        }
    }

    free(stack);
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    quick_sort_iterative(arr, len);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

快速排序（递归法）

快速排序的递归版是最常见的写法。
每次分区后，递归处理基准值左边和右边两个子区间。

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

void print_array(const int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quick_sort_recursive(int arr[], int low, int high) {
    if (low < high) {
        int pivot_index = partition(arr, low, high);
        quick_sort_recursive(arr, low, pivot_index - 1);
        quick_sort_recursive(arr, pivot_index + 1, high);
    }
}

int main(void) {
    int arr[] = {29, 17, 45, 12, 53, 7, 84, 65, 96, 41, 71, 88};
    int len = (int)(sizeof(arr) / sizeof(arr[0]));

    quick_sort_recursive(arr, 0, len - 1);
    print_array(arr, len);
    return 0;
}

输出结果：

1
7 12 17 29 41 45 53 65 71 84 88 96

看完整篇后，可以把这几种排序分成两类来记：

基础交换/插入类：冒泡、选择、插入、希尔
分治类：归并、快速

这样复习时会更容易抓住主线，而不是把每一段代码都当成独立模板死记。

如何选择排序算法

数据量很小、主要为了练基本功时，可以先从冒泡、选择、插入开始。
数据接近有序时，插入排序往往比你想象中更好用。
需要稳定性并且能接受额外空间时，归并排序是更稳妥的选择。
追求平均性能、接受最坏情况退化风险时，快速排序通常是默认候选。
真实项目里如果标准库已经提供了成熟排序接口，优先用库，再回头理解这些算法思想。

常见错误

冒泡排序和选择排序把内层循环边界写错，导致比较次数不足，或者访问 arr[j + 1] 越界。
插入排序忘了把较大的元素向后移动，只保留了“插入”动作，结果会覆盖原数据。
希尔排序把 gap 缩小逻辑写错，或者没有最终缩到 1，导致数组并没有真正排完。
归并排序没有正确分配辅助数组，或者合并后没有把临时结果拷回原数组。
归并排序的递归终止条件写错，导致递归不收敛或重复处理同一区间。
快速排序分区时把基准值交换顺序写乱，最终会出现重复元素丢失或分区不正确。
快速排序在最坏情况下递归层数很深，如果输入接近有序又总是选边界元素做基准，性能会明显下降。
把函数参数里的数组再次用 sizeof(arr) / sizeof(arr[0]) 求长度，结果得到的是指针大小，不是真实元素个数。

章节

7.1 排序算法入门

排序算法入门

概念说明

语法/规则

示例

冒泡排序

选择排序

插入排序

希尔排序

归并排序（迭代法）

归并排序（递归法）

快速排序（迭代法）

快速排序（递归法）

如何选择排序算法

常见错误