一、排序算法对比表
| 特性 | 冒泡排序 | 插入排序 | 选择排序 |
|---|---|---|---|
| 时间复杂度 | O(n²) | O(n²)（最优O(n)） | O(n²) |
| 空间复杂度 | O(1) | ||
| 稳定性 | 稳定 | 不稳定 | |
| 最佳场景 | 基本有序的小数据集 | 部分有序的数组 | 数据量较小 |
| 交换次数 | 最多（每次逆序都交换） | 较少（仅移动元素） | 固定n-1次交换 |
二、修正后的标准实现
1. 冒泡排序（Bubble Sort）
void bubble_sort(int a[],int n){//稳定
for(int i=1;i<n;i++){
for(int j=1;j<=n-i;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
}
}
}
}
2. 插入排序（Insertion Sort）
void insert_sort(int a[],int n){//稳定
for(int i=2;i<=n;i++){
int key =a[i];
int j=i-1;
while(j>=1&&a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
3. 选择排序（Selection Sort）
void select_sort(int a[],int n){//不稳定
for(int i=1;i<=n;i++){
int k=i;
int j;
for(j=i+1;j<=n;j++){
if(a[k]>a[j]){
k=j;
}
}
swap(a[k],a[i]);
}
}
三、经典应用场景
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 数据基本有序 | 插入排序 | 接近O(n)时间复杂度 |
| 需要稳定排序 | 冒泡/插入排序 | 选择排序不稳定 |
| 内存严格受限 | 选择排序 | 交换次数最少（适合Flash存储设备） |
| 教学演示 | 冒泡排序 | 算法逻辑最简单直观 |
四、可视化过程对比
冒泡排序（相邻元素比较交换）：
初始：5 3 8 6 4
第1轮：3 5 6 4 [8]
第2轮：3 5 4 [6 8]
第3轮：3 4 [5 6 8]
第4轮：3 [4 5 6 8]
插入排序（逐步构建有序序列）：
初始：5 |3 8 6 4
步骤1：3 5 |8 6 4
步骤2：3 5 8 |6 4
步骤3：3 5 6 8 |4
结果：3 4 5 6 8
选择排序（选择最小元素前移）：
初始：5 3 8 6 4
第1轮：[3] 5 8 6 4
第2轮：[3 4] 8 6 5
第3轮：[3 4 5] 6 8
第4轮：[3 4 5 6] 8
0 条评论
目前还没有评论...