C语言——排序（冒泡，选择，插入）

基本概念

        排序是对数据进行处理的常见操作，即将数据按某字段规律排列。字段是数据节点的一个属性，比如学生信息中的学号、分数等，可针对这些字段进行排序。同时，排序算法有稳定性之分，若两个待排序字段一致的数据在排序前后相对位置不变，则该排序算法是稳定的，否则不稳定。此外，根据数据量与内存的关系，还分为内排序（数据量小，可全部装入内存处理）和外排序（数据量大，需暂存外存，分批次读入内存处理）。

一、冒泡排序

（一）核心思想

        冒泡排序基于相邻元素比较的思路。从头到尾让每两个相邻元素进行比较，若顺序符合排序要求则保持位置不变，若为逆序则交换位置。经过一轮比较，序列中具有 “极值”（最大值或最小值，取决于排序顺序）的数据会被挪至序列末端。

        例如，对于数组[5, 3, 8, 6, 2]进行升序排序，从第一个元素开始，5 和 3 比较，因为 5 > 3，所以交换位置，数组变为[3, 5, 8, 6, 2]；接着 5 和 8 比较，顺序不变；8 和 6 比较，交换位置，数组变为[3, 5, 6, 8, 2]；8 和 2 比较，交换位置，第一轮比较结束后数组变为[3, 5, 6, 2, 8]。可以看到，最大的数 8 被移到了数组末尾。若序列中有n个数据，在最极端情况下，经过n - 1轮比较一定能将所有数据排序完毕。

（二）代码实现

​
// 冒泡排序，data为数组，len为数组长度
void bubbleSort(int* data, int len) {int i, j;for (i = 0; i < len - 1; i++) {int flag = 1;  // 用于标记某一趟是否有元素交换，若没有则说明已排序完成for (j = 0; j < len - 1 - i; j++) {if (data[j] > data[j + 1]) {  // 升序排序，若要降序改为data[j] < data[j + 1]int tmp;tmp = data[j];data[j] = data[j + 1];data[j + 1] = tmp;flag = 0;  // 有元素交换，标记为0}}if (flag) {  // 若某一趟没有元素交换，提前结束排序break;}}
}​

（三）性能分析

        冒泡排序的时间复杂度为 O(n^2)，其中n是待排序数据的数量。这是因为在最坏情况下，需要进行n - 1轮比较，每轮比较的次数从n - 1逐渐减少到 1。空间复杂度为 O(1)，因为它只需要几个临时变量来进行元素交换，不需要额外的大量空间。冒泡排序是一种稳定的排序算法，因为相同元素的相对顺序在排序过程中不会改变。

（四）示例图示

冒泡排序

以数组[5, 3, 8, 6, 2]的升序排序为例：

第一轮：

• 比较 5 和 3，交换，数组变为[3, 5, 8, 6, 2]
• 比较 5 和 8，顺序不变
• 比较 8 和 6，交换，数组变为[3, 5, 6, 8, 2]
• 比较 8 和 2，交换，数组变为[3, 5, 6, 2, 8]

第二轮：

• 比较 3 和 5，顺序不变
• 比较 5 和 6，顺序不变
• 比较 6 和 2，交换，数组变为[3, 5, 2, 6, 8]

第三轮：

• 比较 3 和 5，顺序不变
• 比较 5 和 2，交换，数组变为[3, 2, 5, 6, 8]

第四轮：

• 比较 3 和 2，交换，数组变为[2, 3, 5, 6, 8]，排序完成。

二、选择排序

（一）核心思想

        选择排序的思路是每一轮从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

        例如，对于数组[5, 3, 8, 6, 2]进行升序排序，第一轮从数组中找到最小的数 2，与第一个数 5 交换位置，数组变为[2, 3, 8, 6, 5]；第二轮从剩下的[3, 8, 6, 5]中找到最小的数 3，由于它已经在正确位置，无需交换；第三轮从[8, 6, 5]中找到最小的数 5，与 8 交换位置，数组变为[2, 3, 5, 6, 8]；第四轮从[6, 8]中找到最小的数 6，由于它已经在正确位置，无需交换，此时数组已排序完成。

（二）代码实现

​
// 选择排序，data为数组，len为数组长度
void selectionSort(int* data, int len) {int i, j, minIndex;for (i = 0; i < len - 1; i++) {minIndex = i;for (j = i + 1; j < len; j++) {if (data[j] < data[minIndex]) {  // 升序排序，若要降序改为data[j] > data[minIndex]minIndex = j;}}if (minIndex != i) {int tmp = data[i];data[i] = data[minIndex];data[minIndex] = tmp;}}
}​

（三）性能分析

        选择排序的时间复杂度同样为 O(n^2)，因为无论数据初始状态如何，都需要进行n - 1轮选择和交换操作。空间复杂度为 O(1)，只需要几个临时变量。选择排序是一种不稳定的排序算法，例如数组[5, 5, 3]进行升序排序时，两个 5 的相对顺序可能会改变。

（四）示例图示

选择排序

以数组[5, 3, 8, 6, 2]的升序排序为例：

第一轮：

找到最小的 2，与 5 交换，数组变为[2, 3, 8, 6, 5]

第二轮：

在剩下的[3, 8, 6, 5]中找到最小的 3，位置不变

第三轮：

在[8, 6, 5]中找到最小的 5，与 8 交换，数组变为[2, 3, 5, 6, 8]

第四轮：

在[6, 8]中找到最小的 6，位置不变，排序完成。

三、插入排序

（一）核心思想

        插入排序假设前面已经有i个节点是有序的，那么从第i + 1个节点开始，插入到前面i个节点的合适位置中。由于第一个元素自身总是有序的，因此从第 2 个元素开始，不断插入前面的有序序列，直到全部排列完毕。

        例如，对于数组[5, 3, 8, 6, 2]进行升序排序，初始时认为第一个元素 5 是有序的。然后取第二个元素 3，将其与 5 比较，因为 3 < 5，所以将 5 后移一位，把 3 插入到 5 原来的位置，数组变为[3, 5, 8, 6, 2]；接着取第三个元素 8，由于 8 > 5，所以 8 的位置不变，数组仍为[3, 5, 8, 6, 2]；再取第四个元素 6，将其依次与 8、5 比较，找到合适位置插入，数组变为[3, 5, 6, 8, 2]；最后取第五个元素 2，将其依次与 8、6、5、3 比较，找到合适位置插入，数组变为[2, 3, 5, 6, 8]。

（二）代码实现

​
// 插入排序，data为数组，len为数组长度
void insertionSort(int* data, int len) {int i, j, tmp;for (i = 1; i < len; i++) {tmp = data[i];j = i - 1;while (j >= 0 && data[j] > tmp) {  // 升序排序，若要降序改为data[j] < tmpdata[j + 1] = data[j];j--;}data[j + 1] = tmp;}
}​

（三）性能分析

        插入排序在最好情况下（数据已经有序）的时间复杂度为 O(n)，因为只需要进行n - 1次比较，无需移动元素。在最坏情况下（数据逆序）的时间复杂度为 O(n^2)，平均时间复杂度也为O(n^2)。空间复杂度为 O(1)，只需要几个临时变量。插入排序是一种稳定的排序算法，因为在插入过程中，相同元素的相对顺序不会改变。

（四）示例图示

插入排序

以数组[5, 3, 8, 6, 2]的升序排序为例：

第一轮：

3 插入到 5 前面，数组变为[3, 5, 8, 6, 2]

第二轮：

8 位置不变，数组仍为[3, 5, 8, 6, 2]

第三轮：

6 插入到 8 前面，数组变为[3, 5, 6, 8, 2]

第四轮：

2 插入到最前面，数组变为[2, 3, 5, 6, 8]，排序完成。

总结

冒泡排序、选择排序和插入排序都是简单的排序算法，它们的时间复杂度在最坏情况下都O(n^2)，空间复杂度为O(1)，适用于数据样本较小的场合。其中，冒泡排序和插入排序是稳定的排序算法，选择排序是不稳定的排序算法。在实际应用中，可根据数据特点和需求选择合适的排序算法。