数据结构——排序算法(冒泡、快速、选择、插入)
文章目录
1. 概念
2. 十大排序算法
3. 冒泡排序
4. 冒泡代码实现
5. 快速排序
6. 快速代码实现
7. 选择排序
8. 选择代码实现
9. 插入排序
10. 插入代码实现
1. 概念
排序（Sort）是将无序的记录序列（或称文件）调整成有序的序列。排序算法在计算机科学中非常重要，因为它们可以提高数据检索效率、简化后续算法的复杂性和优化存储结构等。
稳定排序和非稳定排序
- 稳定排序：如果在排序前，两个相等的元素在原序列中的先后顺序在排序后依然保持不变，那么这种排序算法就是稳定的。插入排序，归并排序，冒泡排序。
- 非稳定排序：如果排序后，两个相等的元素的先后顺序可能改变，那么这种排序算法就是非稳定的。选择排序，快速排序，堆排序。
例如：
- 原序列：R1,R2,...,Ri,...,Rj,...,Rn
- 其中，Ki=Kj 且 i<j（即 Ri 在 Rj 之前）。
在稳定排序中，排序后 Ri 仍在 Rj 之前。而在非稳定排序中，Ri 和 Rj 的相对位置可能会改变。
内排序和外排序
- 内排序：如果待排序文件的所有记录都能放入内存中进行排序，那么这种排序称为内排序。内排序速度快，但受限于内存容量，适用于较小的数据集。插入排序、冒泡排序、选择排序、快速排序、归并排序等。
- 外排序：如果待排序文件的大小超过了内存容量，需要借助外存（如磁盘）进行排序，那么这种排序称为外排序。外排序速度较慢，但适用于大型数据集。通常通过将数据分块读取到内存中排序，然后再将排序后的块合并来实现。比如：归并排序。
排序算法是计算机科学中的基本算法，广泛应用于各种场景。稳定性和适用场景是选择排序算法时的重要考虑因素。内排序适用于小数据集，外排序则适用于大数据集。理解这些概念和性质有助于选择合适的排序算法，从而提高程序的效率和性能。
2. 十大排序算法
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n log² n) | O(n²) | O(n) | O(1) | 不稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n²) | O(n) | O(n) | 稳定 |
| 基数排序 | O(n * k) | O(n * k) | O(n * k) | O(n * k) | 稳定 |
3. 冒泡排序
冒泡排序是一种简单的排序算法，它通过多次遍历要排序的序列，依次比较相邻元素的大小，并根据需要交换它们的位置，以此将序列中的最大或最小元素逐步移动到序列的一端。其思路如下：
-
比较相邻元素：
- 从数组的第一个元素开始，依次比较相邻的两个元素。
-
交换位置：
- 如果当前面的元素比后面的元素大（或小，根据升序或降序排序的要求），则交换这两个元素的位置。
-
一趟遍历完成：
- 最大（或最小）元素已移至末尾：经过一趟遍历，最大（或最小）的元素会被交换到数组的最后一个位置。
-
重复进行遍历和交换：
- 除了最后一个元素，对数组中的所有元素重复执行上述两步。
每次遍历都会将当前未排序部分的最大（或最小）元素放置到合适的位置。
循环遍历：重复执行步骤3和步骤4，直到整个数组都被排序。
示例：
以序列 [3, 1, 5, 4, 2] 为例，进行冒泡排序的过程如下：
-
第一趟比较：
- 比较
3和1，3大于1，交换位置，序列变为[1, 3, 5, 4, 2]。 - 比较
3和5，3小于5，不交换位置，序列不变。 - 比较
5和4，5大于4，交换位置，序列变为[1, 3, 4, 5, 2]。 - 比较
5和2，5大于2，交换位置，序列变为[1, 3, 4, 2, 5]。 - 第一趟比较结束，最大元素
5已经移到序列末尾。
- 比较
-
第二趟比较：
- 比较
1和3，1小于3，不交换位置，序列不变。 - 比较
3和4，3小于4，不交换位置，序列不变。 - 比较
4和2，4大于2，交换位置，序列变为[1, 3, 2, 4, 5]。 - 第二趟比较结束，次大元素
4已经移到序列倒数第二位。
- 比较
-
第三趟比较：
- 比较
1和3，1小于3，不交换位置，序列不变。 - 比较
3和2，3大于2，交换位置，序列变为[1, 2, 3, 4, 5]。 - 第三趟比较结束，次小元素
3已经移到正确位置。
- 比较
-
第四趟比较：
- 比较
1和2，1小于2，不交换位置，序列不变。 - 第四趟比较结束，次次小元素
2已经移到正确位置。
- 比较
通过上述步骤，整个序列变为 [1, 2, 3, 4, 5]，排序完成。
优化：
在实际实现中，可以通过添加一个标志来检测在某一趟遍历中是否发生了交换。如果没有发生交换，则说明数组已经是有序的，可以提前终止排序过程，进一步提升算法效率。
这种算法适用于数据量较小的情况，虽然其时间复杂度为O(n²)，但其实现简单，且在某些情况下（如数据量较小或数据已基本有序）依然具有一定的实用性。
4. 冒泡代码实现
#include <stdio.h>// 冒泡排序函数定义
void bubbleSort(int arr[], int n) {int i, j;// 外层循环：控制比较轮数，每次减少一个元素的比较for (i = 0; i < n - 1; i++) {// 内层循环：进行元素比较和交换for (j = 0; j < n - i - 1; j++) {// 如果前一个元素大于后一个元素，则交换它们if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}// 打印数组的函数
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}// 主函数
int main() {// 定义一个数组int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组: \n");printArray(arr, n);// 调用冒泡排序函数bubbleSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}
5. 快速排序
快速排序（Quick Sort）是一种高效的排序算法，由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。其主要特点是通过分治法（Divide and Conquer）来实现对数据的快速排序。下面详细解释快速排序的算法原理和执行过程。
基本思想
快速排序通过以下步骤进行排序：
- 选择基准（pivot）：从数列中挑选一个元素，称为“基准”。
- 分区（partition）：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准后面。经过分区后，基准值的位置就是它在排序后数组中的最终位置。
- 递归排序：递归地对基准值左边的子数组和右边的子数组进行快速排序。
执行步骤
-
选择基准：
- 基准可以是数组中的任意一个元素，常见的选择方法有：选择第一个元素、最后一个元素、中间的元素，或者随机选择一个元素作为基准。
-
分区操作：
- 将数组中的元素重新排列，所有小于基准的元素放在基准的左边，所有大于基准的元素放在基准的右边。
- 分区过程中，基准值最终会被放到它的正确位置上，即使得基准左边的所有元素都小于基准，右边的所有元素都大于基准。
-
递归排序：
- 对基准左边和右边的子数组分别进行快速排序。
- 递归的基准情况是子数组的大小为零或一，此时数组已经被排序好了。
优点与缺点
-
优点：
- 平均时间复杂度为O(n log n)，在大多数情况下表现非常好。
- 空间复杂度为O(log n)，需要递归调用栈空间。
- 属于原地排序算法，空间利用率高。
- 排序速度非常快，尤其适用于大数据集。
-
缺点：
- 最坏情况下时间复杂度为O(n^2)，如数组已经有序或逆序时。
- 不稳定排序，可能打乱相同元素的相对顺序。
示例1：
个示例展示了如何使用快速排序算法对数组进行排序。假设有以下数组：
[49, 38, 65, 97, 76, 13, 27, 49]第一步：选择基准并进行第一次分区
- 选择基准
49。 - 进行分区，将数组分为三部分：小于
49、等于49和大于49的部分。
[27, 38, 13], 49, [76, 97, 65, 49]
第二步：递归排序
对每一部分继续递归地进行快速排序：
- 对左侧
[27, 38, 13]部分：- 选择
27作为基准。 - 分区为
[13] 27 [38]。
- 选择
[13] 27 [38]
对右侧 [76, 97, 65, 49] 部分：
- 选择
76作为基准。 - 分区为
[65] 76 [97]。
[65] 76 [97]组合结果
将所有部分组合起来，得到排序后的数组：
[13, 27, 38, 49, 49, 65, 76, 97]
示例2：
初始状态：
[9, -16, 30, 23, -30, -49, 25, 21, 30]
-
第一趟交换：
- 基准值：9
- 低位指针和高位指针开始交换：
- 第一次交换后： [-16, 9, 30, 23, -30, -49, 25, 21, 30]
- 第二次交换后： [-16, -49, 30, 23, -30, 9, 25, 21, 30]
- 第三次交换后： [-16, -49, -30, 23, 9, 30, 25, 21, 30]
-
第二趟交换：
- 基准值：-30
- 低位指针和高位指针开始交换：
- 第一次交换后： [-49, -30, -16, 23, 9, 30, 25, 21, 30]
- 第二次交换后： [-49, -30, -16, 23, 9, 30, 25, 21, 30]
-
分割完成：
- 将数组分为左侧和右侧分别继续递归排序，最终达到有序。
6. 快速代码实现
#include <stdio.h>// 快速排序入口函数
void quickSort(int arr[], int size) {subSort(arr, 0, size - 1);
}// 辅助排序函数，递归实现
void subSort(int arr[], int start, int end) {if (start < end) {int base = arr[start]; // 选择基准值为第一个元素int low = start; // 初始化低位索引int high = end + 1; // 初始化高位索引while (1) {while (low < end && arr[++low] <= base); // 从左向右扫描，找到第一个大于基准值的元素while (high > start && arr[--high] >= base); // 从右向左扫描，找到第一个小于基准值的元素if (low < high) {int temp = arr[low]; // 交换找到的两个元素arr[low] = arr[high];arr[high] = temp;} else {break; // 如果low和high相遇，则退出循环}}int temp1 = arr[start]; // 将基准值交换到正确的位置arr[start] = arr[high];arr[high] = temp1;subSort(arr, start, high - 1); // 递归排序基准值左边的子数组subSort(arr, high + 1, end); // 递归排序基准值右边的子数组}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {9, -16, 40, 23, -30, -49, 25, 21, 30};int length = sizeof(arr) / sizeof(int);// 排序前遍历数组printArray(arr, length);// 调用快速排序quickSort(arr, length);// 排序后遍历数组printArray(arr, length);return 0;
}
7. 选择排序
选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是不断地从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾，从而不断扩大已排序的部分，直到整个数组有序。选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)，是一种不稳定的排序算法。
算法原理
- 初始状态：整个数组为未排序部分。
- 找到最小值：从未排序部分中找到最小（或最大）的元素。
- 交换位置：将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
- 已排序部分增加：将已排序部分扩大一个元素，未排序部分减小一个元素。
- 重复步骤2-4：对未排序部分重复上述步骤，直到未排序部分为空，排序完成。
优点
-
简单易懂：选择排序的算法原理非常直观，容易理解和实现，特别适合教学和初学者学习。
-
不需要额外空间：选择排序是就地排序（in-place sorting）算法，只需要常数级别的额外空间，空间复杂度为O(1)。
-
适合小规模数据：对于小规模数据集，选择排序的实现简单且运行时间可以接受。
缺点
-
时间复杂度高：选择排序的时间复杂度为O(n^2)，不适合大规模数据集，随着数据量的增加，性能会显著下降。
-
不稳定：选择排序是不稳定的排序算法，即相同元素的相对顺序在排序过程中可能会被改变。
-
数据交换多：在选择排序过程中，每次找到最小值后都会进行数据交换，如果数组元素较多且数据量较大，频繁的数据交换会影响性能。
过程示例：
初始数组：
[29, 10, 14, 37, 14]
第一轮：找到最小值10，交换29和10。
[10, 29, 14, 37, 14]
第二轮：找到最小值14，交换29和14。
[10, 14, 29, 37, 14]
第三轮：找到最小值14，交换29和14。
[10, 14, 14, 37, 29]
第四轮(最终结果)：找到最小值29，交换37和29。
[10, 14, 14, 29, 37]
选择排序通过不断选择未排序部分的最小值，将其移动到已排序部分的末尾，逐步完成整个排序过程。虽然选择排序的时间复杂度较高，但其实现简单，适用于数据量较小或对稳定性要求不高的场景。
8. 选择代码实现
#include <stdio.h>// 选择排序函数
void selectionSort(int arr[], int size) {// 外层循环，逐步扩大已排序部分for (int i = 0; i < size - 1; i++) {// 假设当前位置i为最小值索引int minIndex = i;// 内层循环，从i+1位置开始寻找未排序部分的最小值for (int j = i + 1; j < size; j++) {if (arr[j] < arr[minIndex]) {// 更新最小值索引minIndex = j;}}// 交换当前位置i和找到的最小值位置minIndex的元素if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {// 定义并初始化一个待排序的数组int arr[] = {29, 10, 14, 37, 14};int length = sizeof(arr) / sizeof(arr[0]);// 排序前遍历数组并打印printf("排序前的数组: ");printArray(arr, length);// 调用选择排序函数对数组进行排序selectionSort(arr, length);// 排序后遍历数组并打印printf("排序后的数组: ");printArray(arr, length);return 0;
}
9. 插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理类似于我们整理扑克牌的过程，从左到右逐步扩大已排序的部分，将当前元素插入到已排序部分的适当位置，直到整个序列有序。
算法原理
- 初始状态：已排序部分只有第一个元素。
- 从第二个元素开始：逐一取出元素，将其插入到已排序部分的适当位置。
- 重复步骤2：直到所有元素均插入到已排序部分。
插入排序的优缺点
优点：
- 算法简单，易于理解和实现。
- 对于少量元素的数组或几乎已经排好序的数组，插入排序非常高效。
- 是稳定排序算法，保证相等元素的相对位置不变。
缺点：
- 对于大规模数组，插入排序的效率较低，时间复杂度为O(n^2)。
插入排序的步骤示例
初始状态：
[5, 2, 9, 1, 5, 6]
- 已排序部分：
[5] -
第二个元素2：
- 将2插入到已排序部分
[5]之前。
- 将2插入到已排序部分
[2, 5, 9, 1, 5, 6]
-
已排序部分：
[2, 5] -
第三个元素9：
- 将9插入到已排序部分
[2, 5]之后。
- 将9插入到已排序部分
[2, 5, 9, 1, 5, 6]
-
已排序部分：
[2, 5, 9] -
第四个元素1：
- 将1插入到已排序部分
[2, 5, 9]之前。
- 将1插入到已排序部分
[1, 2, 5, 9, 5, 6]
-
已排序部分：
[1, 2, 5, 9] -
第五个元素5：
- 将5插入到已排序部分
[1, 2, 5, 9]的适当位置。
- 将5插入到已排序部分
[1, 2, 5, 5, 9, 6]
-
已排序部分：
[1, 2, 5, 5, 9] -
第六个元素6：
- 将6插入到已排序部分
[1, 2, 5, 5, 9]的适当位置。
- 将6插入到已排序部分
[1, 2, 5, 5, 6, 9]
10. 插入代码实现
#include <stdio.h>// 插入排序函数
void insertionSort(int arr[], int size) {// 从数组的第二个元素开始，逐个插入到已排序部分for (int i = 1; i < size; i++) {int key = arr[i]; // 当前待插入的元素int j = i - 1;// 将已排序部分中大于key的元素向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key; // 将key插入到正确的位置}
}// 打印数组函数
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {// 定义并初始化一个待排序的数组int arr[] = {5, 2, 9, 1, 5, 6};int length = sizeof(arr) / sizeof(arr[0]);// 排序前遍历数组并打印printf("排序前的数组: ");printArray(arr, length);// 调用插入排序函数对数组进行排序insertionSort(arr, length);// 排序后遍历数组并打印printf("排序后的数组: ");printArray(arr, length);return 0;
}