基础排序算法详解：冒泡排序、选择排序与插入排序
引言
上一章，我们聊到了排序的基本概念和常见算法的分类。这一次，我们从基础开始，深入剖析三种常见的O(n²) 排序算法：冒泡排序、选择排序 和 插入排序。
它们是学习排序算法的入门神器，不仅实现简单，还能帮助你掌握排序的核心思想。虽然它们的效率较低，但在小规模数据场景中仍然非常实用。
准备好了吗？让我们一起“搞懂这三兄弟”！
一、冒泡排序（Bubble Sort）
算法思想
冒泡排序通过重复比较相邻元素，将较大的元素逐步向右“冒泡”。每一轮都把未排序部分的最大值放到最后。
算法过程
- 从第一个元素开始，依次比较相邻元素，如果左边的比右边大，就交换它们。
- 重复这一过程，直到所有元素有序。
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // 外层循环控制遍历轮数
int swapped = 0; // 标记是否发生交换
for (int j = 0; j < n - 1 - i; j++) { // 内层循环控制相邻比较
if (arr[j] > arr[j + 1]) { // 如果前面的比后面的大，交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break; // 如果没有发生交换，提前结束排序
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
优化版：提前结束判断
通过引入swapped变量，检测一轮比较后是否发生交换。如果没有交换，说明数组已经有序，可以提前结束循环，提升效率。
复杂度分析
- 时间复杂度：最优 O(n)（已排序），最差 O(n²)，平均 O(n²)
- 空间复杂度：O(1)
- 稳定性：稳定
二、选择排序（Selection Sort）
算法思想
选择排序的核心是“选择最小值”：每一轮从未排序部分找到最小值，将它与当前轮的起始位置交换。
算法过程
- 遍历未排序部分，找到最小元素。
- 将最小元素与当前轮的起始位置交换。
- 重复以上步骤，直到排序完成。
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 假设当前元素为最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { // 找到更小的值
minIndex = j;
}
}
// 交换最小值与当前轮的起始位置
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
复杂度分析
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定（因为交换可能改变相等元素的相对顺序）
优缺点
- 优点：实现简单，数据量小时可用。
- 缺点：不稳定，效率较低。
三、插入排序（Insertion Sort）
算法思想
插入排序通过逐步构建已排序部分，将未排序部分的元素插入到正确位置。它的核心思想类似于打牌时整理手牌。
算法过程
- 从第一个元素开始，它可以认为是有序的。
- 取下一个元素，与已排序部分从后往前比较，找到合适的位置插入。
- 重复，直到所有元素有序。
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前待插入的元素
int j = i - 1;
// 向右移动已排序部分，直到找到合适的位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入到正确位置
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
复杂度分析
- 时间复杂度：最优 O(n)（部分有序），最差 O(n²)，平均 O(n²)
- 空间复杂度：O(1)
- 稳定性：稳定
适用场景
插入排序在数据量小、数据部分有序时非常高效。
四、对比与总结
| 排序算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 特点 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 | 简单易懂，但效率较低 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 不适合对稳定性有要求的场景 |
| 插入排序 | O(n²) | O(1) | 稳定 | 数据量小或部分有序时性能较优 |
五、预告
通过这篇文章，我们详细学习了三种基础排序算法的原理与实现。它们是排序算法的基础，帮助我们理解排序的核心思想。在接下来的文章中，我们将进入高级排序算法的世界，从快速排序开始，感受分治法的强大威力，敬请期待！
结语
冒泡排序、选择排序、插入排序是排序算法的“入门三剑客”，它们简单易懂，却能揭示许多排序算法的本质。希望通过这篇文章，你能深入理解它们的逻辑与实现，并为接下来的高级排序算法打下坚实的基础。
有什么问题或建议，欢迎评论区讨论，我们一起进步！🎉
原文地址：https://blog.csdn.net/CHENWENFEIc/article/details/144327457
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！