
## 一、冒泡排序（Bubble Sort）

![冒泡排序_30秒循环.gif](https://developer.qcloudimg.com/http-save/yehe-2276240/4a3615ab1a3b3b96c6b44690e7fe5310.gif)

### 1. 核心思想
通过重复遍历待排序数组，比较相邻元素，若顺序错误就交换。每一轮将最大（或最小）元素“冒泡”到末尾。

### 2. 算法步骤
1. 从第一个元素开始，依次比较相邻两个元素；
2. 如果前一个大于后一个，则交换；
3. 每完成一次完整遍历，最大的元素就会“沉底”；
4. 重复上述过程，直到没有发生任何交换（说明已排好序）。

### 3. C 语言实现（带优化）
```c
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        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 = true;
            }
        }
        if (!swapped) break; // 优化：提前结束
    }
}
```

### 4. 复杂度分析
- **时间复杂度**：
  - 最坏/平均：O(n²)
  - 最好（已排序）：O(n)
- **空间复杂度**：O(1)
- **稳定性**：✅ 稳定

### 5. 适用场景
- 教学演示
- 小规模数据（n ≤ 100）
- 数据基本有序时效率较高（配合优化）

---

## 二、选择排序（Selection Sort）
![选择排序_30秒循环.gif](https://developer.qcloudimg.com/http-save/yehe-2276240/03e3c7fd49855739b6d04b9b89a08c1b.gif)
### 1. 核心思想
每次从未排序部分中选出最小（或最大）元素，放到已排序部分的末尾。

### 2. 算法步骤
1. 在未排序序列中找到最小元素；
2. 将其与未排序部分的第一个元素交换；
3. 重复此过程，直到所有元素排序完成。

### 3. C 语言实现
```c
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}
```

### 4. 复杂度分析
- **时间复杂度**：始终为 O(n²)
- **空间复杂度**：O(1)
- **稳定性**：❌ 不稳定（交换可能打乱相等元素顺序）

### 5. 优化方向
- **双向选择排序**：每轮同时找最小和最大，分别放到两端，减少一半轮数。

### 6. 适用场景
- 内存写入成本高时（交换次数少，最多 n-1 次）
- 小规模数据

---

## 三、插入排序（Insertion Sort）
![插入排序_30秒循环.gif](https://developer.qcloudimg.com/http-save/yehe-2276240/3a50c6e6827334f2d4abf0409675cca3.gif)
### 1. 核心思想
构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到合适位置插入。

### 2. 算法步骤
1. 从第二个元素开始，将其视为“待插入元素”；
2. 与前面已排序元素逐个比较，找到插入位置；
3. 将大于它的元素后移一位，腾出空位；
4. 插入该元素；
5. 重复直到处理完所有元素。

### 3. C 语言实现
```c
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;
    }
}
```

### 4. 复杂度分析
- **时间复杂度**：
  - 最坏/平均：O(n²)
  - 最好（已排序）：O(n)
- **空间复杂度**：O(1)
- **稳定性**：✅ 稳定

### 5. 优势
- 原地排序、稳定
- 对**小规模**或**近似有序**数据效率极高
- 是**希尔排序**和**快速排序（小数组优化）** 的基础

---

## 四、希尔排序（Shell Sort）
![希尔排序_30秒循环.gif](https://developer.qcloudimg.com/http-save/yehe-2276240/784bded8fddfc48f285683282c3a48e6.gif)
### 1. 核心思想
插入排序的改进版。通过引入“间隔（gap）”将数组分成多个子序列，先对子序列进行插入排序，逐步缩小 gap，最终对整体做一次插入排序。

> 也称为“缩小增量排序”。

### 2. 算法步骤
1. 选择一个 gap 序列（如：n/2, n/4, ..., 1）；
2. 对每个 gap，将数组划分为 gap 个子序列（下标相差 gap 的元素为一组）；
3. 对每个子序列执行插入排序；
4. 缩小 gap，重复步骤 2~3，直到 gap = 1。

### 3. C 语言实现（Knuth 序列：gap = gap * 3 + 1）
```c
void shellSort(int arr[], int n) {
    int gap = 1;
    while (gap < n / 3) {
        gap = gap * 3 + 1; // Knuth 序列: 1, 4, 13, 40, ...
    }
    while (gap >= 1) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
        gap /= 3;
    }
}
```

### 4. 复杂度分析
- **时间复杂度**：依赖 gap 序列
  - 最坏：O(n²)（如使用 n/2 序列）
  - 平均：O(n^1.3) ~ O(n^1.5)（Knuth 序列）
  - 最好：O(n log n)
- **空间复杂度**：O(1)
- **稳定性**：❌ 不稳定（跨组交换可能打乱顺序）

### 5. 优势
- 比 O(n²) 算法快很多
- 原地排序，代码简洁
- 适合中等规模数据（n < 10,000）

---

## 五、对比总结表

| 算法         | 最好时间     | 平均时间       | 最坏时间   | 稳定性 | 交换次数 | 适用场景                     |
|--------------|-------------|----------------|------------|--------|----------|------------------------------|
| 冒泡排序     | O(n)        | O(n²)          | O(n²)      | ✅     | 多       | 教学、极小数据               |
| 选择排序     | O(n²)       | O(n²)          | O(n²)      | ❌     | 少（≤n） | 写操作昂贵、小数据           |
| 插入排序     | O(n)        | O(n²)          | O(n²)      | ✅     | 中       | 小数据、近似有序             |
| 希尔排序     | O(n log n)  | O(n^1.3~1.5)   | O(n²)      | ❌     | 中       | 中等规模、快速实现、无递归   |

---

## 六、实际建议

- **不要在生产环境使用冒泡/选择排序**（效率太低）；
- **插入排序**常用于：
  - 快速排序的“小数组优化”（当子数组长度 < 10 时切换为插入排序）；
  - 在线算法（数据流式到达）；
- **希尔排序**是早期高效排序代表，虽被快排/归并取代，但在嵌入式或无递归环境中仍有价值。



通过重复遍历待排序数组，比较相邻元素，若顺序错误就交换。每一轮将最大（或最小）元素“冒泡”到末尾。

排序算法：冒泡排序(Bubble Sort)、选择排序(Selection Sort)、插入排序(Insertion Sort）、希尔排序(Shell Sort

本文从冒泡排序、选择排序、插入排序、希尔排序 四种经典排序算法的详细讲解，包括：核心思想、算法步骤、伪代码/示例代码（C 语言）、时间/空间复杂度分析、稳定性说明、优化方法及适用场景。

算法

编程语言

冒泡排序、选择排序、插入排序和希尔排序是基础排序算法。冒泡排序通过相邻元素交换实现排序，时间复杂度O(n²)；选择排序每次选择最小元素，交换次数少；插入排序适合小规模数据，时间复杂度O(n²)；希尔排序是插入排序改进版，时间复杂度O(n^1.3~1.5)。这些算法适用于教学和小规模数据处理场景。

数据流

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

排序算法：冒泡排序(Bubble Sort)、选择排序(Selection Sort)、插入排序(Insertion Sort）、希尔排序(Shell Sort-腾讯云开发者社区-腾讯云

排序算法：冒泡排序(Bubble Sort)、选择排序(Selection Sort)、插入排序(Insertion Sort）、希尔排序(Shell Sort

排序算法：冒泡排序(Bubble Sort)、选择排序(Selection Sort)、插入排序(Insertion Sort）、希尔排序(Shell Sort

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐