数据结构-八大选择排序（冒泡排序、简单选择排序、插入排序、希尔排序）
数据结构：八大排序算法原理与实现（Java）-冒泡排序、简单选择排序、插入排序、希尔排序
引入：
在数据结构与算法的学习中，排序算法是基础且核心的内容。八大排序算法（冒泡、选择、插入、希尔、归并、快速、堆、基数）各自有其适用场景，本文将聚焦其中冒泡排序、简单选择排序、插入排序和希尔排序四种，从核心思想、时间复杂度、Java代码实现及优化思路展开讲解，帮助初学者快速理解并掌握。
一、冒泡排序（Bubble Sort）
冒泡排序是最易理解的排序算法之一，核心思路是通过“前后两两对比交换”，将较大的元素逐步“冒泡”到数组末尾。
1.1 核心思想
冒泡排序的本质是通过相邻元素的两两对比与交换，将无序区间内的最大元素 “筛选” 到有序区间的起始位置（即数组末尾）。具体步骤可拆解为：
- 初始化区间：将数组分为 “无序区间”（初始为整个数组
[0, n-1]）和 “有序区间”（初始为空[]）。 - 一轮冒泡：遍历无序区间，依次对比相邻元素
arr[i]和arr[i+1]：- 若
arr[i] > arr[i+1]，交换两者位置，确保大元素向后移动； - 若
arr[i] <= arr[i+1]，不交换，继续对比下一对。
- 若
- 缩小区间：每完成一轮冒泡，无序区间的最大元素会 “浮” 到有序区间的开头，因此无序区间范围缩小为
[0, n-2]、[0, n-3]... - 终止条件：当某一轮冒泡中没有发生任何交换，说明无序区间已完全有序，可提前终止算法（关键优化点）。
为了更直观理解，我们以数组 [5,4,8,3,0,1] 为例，看第一轮冒泡的过程：
- 初始：
[5,4,8,3,0,1]（无序区间[0,5]） - 对比 5 和 4：交换 →
[4,5,8,3,0,1] - 对比 5 和 8：不交换 →
[4,5,8,3,0,1] - 对比 8 和 3：交换 →
[4,5,3,8,0,1] - 对比 8 和 0：交换 →
[4,5,3,0,8,1] - 对比 8 和 1：交换 →
[4,5,3,0,1,8]（有序区间新增元素 8，无序区间变为[0,4]）
1.2 时间复杂度
- **最坏情况/平均情况**：`O(n²)`（数组完全逆序时，需执行 `n-1` 轮循环，每轮对比 `n-i` 次）。
- **最好情况**：`O(n)`（数组已有序，加入“无交换则终止”的优化后，仅需遍历一次数组）。
注：关于时间复杂度的计算将在后续文章中体现。
1.3 Java实现（基础版与简化优化版）
基础版（无优化）
```java
public class BubbleSortBasic {
public static void main(String[] args) {
int arr[] = {1, 8, 4, 5, 6, 7, 5, 4};
bubbleSort(arr);
// 打印排序结果
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); // 输出：1 4 4 5 5 6 7 8
}
}
// 基础冒泡排序
public static void bubbleSort(int[] arr) {
// 外层循环：控制排序轮次（最多 n-1 轮）
for (int j = 0; j < arr.length - 1; j++) {
// 内层循环：每轮对比相邻元素（未排序部分）
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
// 交换元素
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
}
```
简化优化版1减少无效对比（缩小内层循环范围）
基础版中，每轮循环会重复对比“已排序完成”的末尾元素，优化版通过 `arr.length - 1 - i` 减少内层循环次数：
```java
public class BubbleSortOptimized {
public static void main(String[] args) {
int arr[] = {5, 4, 8, 3, 0, 1};
sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); // 输出：0 1 3 4 5 8
}
}
public static void sort(int array[]) {
// 外层循环：控制轮次
for (int i = 0; i < array.length - 1; i++) {
// 内层循环：仅对比未排序部分（末尾 i 个元素已有序）
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// 交换
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
}
简化优化版1提前终止（无交换则有序）
若某一轮冒泡中没有发生任何交换，说明无序区间已完全有序，可直接跳出外层循环，避免后续无效轮次：
```java
public class BubbleSortOptimized2 {
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,6}; // 已排序数组，测试提前终止
optimizedBubbleSort(arr);
}
public static void optimizedBubbleSort(int[] arr) {
boolean hasSwap; // 标记本轮是否发生交换
for (int i = 0; i < arr.length - 1; i++) {
hasSwap = false; // 初始化为“无交换”
System.out.printf("第%d轮：", i+1);
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
hasSwap = true; // 发生交换，标记为true
}
}
for (int num : arr) System.out.print(num + " ");
if (!hasSwap) {
System.out.println("\n本轮无交换，数组已有序，提前终止！");
break; // 无交换，直接终止循环
}
System.out.println();
}
}
}
// 运行结果：
// 第1轮：1 2 3 4 5 6
// 本轮无交换，数组已有序，提前终止！
二、简单选择排序（Simple Selection Sort）
简单选择排序的核心是“找最小值并交换”，通过减少交换次数优化性能（相比冒泡排序，交换次数从 `O(n²)` 降至 `O(n)`）。
2.1 核心思想
简单选择排序将数组分为 “已排序区间”（初始为空 []）和 “未排序区间”（初始为 [0, n-1]），每轮仅进行一次交换，具体步骤：
- 定位最小值：遍历未排序区间，找到其中的最小值，记录其索引
minIndex（初始假设未排序区间的第一个元素为最小值）； - 交换元素：将最小值（
arr[minIndex]）与未排序区间的第一个元素（arr[j]，j为未排序区间起始索引）交换，此时最小值加入已排序区间； - 缩小区间：未排序区间起始索引
j向后移动 1 位，重复步骤 1-2，直到未排序区间为空。
以数组 [5,7,4,2,0,3,1,6] 为例，第一轮选择过程：
- 未排序区间
[0,7]，初始minIndex=0（值为 5）； - 遍历
i=1到7：i=1（值 7）：7>5，minIndex不变；i=2（值 4）：4<5，minIndex=2；i=3（值 2）：2<4，minIndex=3；i=4（值 0）：0<2，minIndex=4；- 后续元素均大于 0，
minIndex保持为 4；
- 交换
arr[0]（5）和arr[4]（0），数组变为[0,7,4,2,5,3,1,6]，已排序区间变为[0]。
2.2 时间复杂度
- **最坏情况/平均情况/最好情况**：均为 `O(n²)`（无论数组是否有序，每轮都需遍历“未排序部分”找最小值，对比次数固定）。
2.3 Java实现
```java
public class SimpleSelectionSort {
public static void main(String[] args) {
int arr[] = {5, 7, 4, 2, 0, 3, 1, 6};
sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); // 输出：0 1 2 3 4 5 6 7
}
}
public static void sort(int[] arr) {
// 外层循环：控制“已排序部分”的边界（j 是未排序部分的第一个元素索引）
for (int j = 0; j < arr.length; j++) {
int minIndex = j; // 初始假设未排序部分的第一个元素是最小值
// 内层循环：遍历未排序部分，找真正的最小值索引
for (int i = j + 1; i < arr.length; i++) {
if (arr[minIndex] > arr[i]) {
minIndex = i; // 更新最小值索引
}
}
// 将最小值与未排序部分的第一个元素交换
int temp = arr[j];
arr[j] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
```
三、插入排序（Insertion Sort）
插入排序类似“整理扑克牌”，核心是“将元素插入已排序序列的合适位置”，也被称为“倒叙冒泡”。
3.1 核心思想
- 初始认为数组的**第一个元素**是“已排序部分”，其余元素为“未排序部分”。
- 从“未排序部分”取第一个元素（`arr[i]`），与“已排序部分”的元素从后向前对比（倒叙）。
- 若“已排序部分”的元素大于当前元素，则将其向后移动；直到找到小于或等于当前元素的位置，将当前元素插入。
- 缺点：若插入的元素值较小，“已排序部分”的元素需要多次后移，效率较低。
3.2 时间复杂度
- **最坏情况/平均情况**：`O(n²)`（数组逆序时，每个元素需移动 `i` 次，总移动次数为 `1+2+...+(n-1) = n(n-1)/2`）。
- **最好情况**：`O(n)`（数组有序时，每个元素仅需对比1次，无需移动）。
3.3 Java实现
```java
public class InsertionSort {
public static void main(String[] args) {
int arr[] = {5, 7, 4, 2, 0, 3, 1, 6};
insertSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); // 输出：0 1 2 3 4 5 6 7
}
}
public static void insertSort(int[] arr) {
// 外层循环：i 是未排序部分的第一个元素索引（从1开始，0已有序）
for (int i = 1; i < arr.length; i++) {
// 内层循环：从已排序部分的末尾（i-1）向前对比，找插入位置
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
// 元素后移（相当于为当前元素腾出位置）
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
} else {
// 找到插入位置，提前终止（已排序部分无需继续对比）
break;
}
}
}
}
}
```
四、希尔排序（Shell Sort）
希尔排序是插入排序的优化版，也叫“缩小增量排序”，通过“分组排序”减少插入排序的后移次数，大幅提升效率。
4.1 核心思想
- 核心：**先分组，再组内排序，逐步缩小分组间隔**，最终间隔为1时完成全局排序。
- 步骤：
1. 确定初始分组间隔（通常为数组长度的一半，如 `gap = arr.length / 2`）。
2. 按间隔 `gap` 将数组分为多个小组（如 `gap=4` 时，索引0与4、1与5、2与6、3与7为一组）。
3. 对每个小组执行“插入排序”，使小组内元素有序。
4. 缩小间隔（如 `gap = gap / 2`），重复步骤2-3，直到 `gap=1`。
5. 当 `gap=1` 时，数组已接近有序，仅需少量移动即可完成最终排序。
4.2 时间复杂度
- 希尔排序的时间复杂度与“间隔序列”相关，本文采用“折半间隔”（`gap = gap/2`），时间复杂度为 `O(n log₂n)`。
- 相比插入排序的 `O(n²)`，希尔排序在处理中大型数组时效率提升显著。
4.3 Java实现
以长度为8的数组为例，间隔依次为4、2、1：
```java
public class ShellSort {
public static void main(String[] args) {
int arr[] = {5, 7, 4, 2, 0, 3, 1, 6};
sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); // 输出：0 1 2 3 4 5 6 7
}
}
public static void sort(int[] arr) {
// 第一轮：间隔 gap=4（数组长度8/2=4）
for (int j = 4; j < arr.length; j++) {
// 组内插入排序（每组元素间隔4）
for (int i = j - 4; i >= 0; i -= 4) {
if (arr[i] > arr[i + 4]) {
int temp = arr[i];
arr[i] = arr[i + 4];
arr[i + 4] = temp;
}
}
}
// 第二轮：间隔 gap=2（4/2=2）
for (int j = 2; j < arr.length; j++) {
for (int i = j - 2; i >= 0; i -= 2) {
if (arr[i] > arr[i + 2]) {
int temp = arr[i];
arr[i] = arr[i + 2];
arr[i + 2] = temp;
}
}
}
// 第三轮：间隔 gap=1（2/2=1），此时数组接近有序
for (int j = 1; j < arr.length; j++) {
for (int i = j - 1; i >= 0; i -= 1) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
}
```
通用优化版（动态计算间隔）
上述代码为了直观展示分组过程，硬编码了间隔；实际开发中可通过循环动态计算间隔：
```java
public static void shellSortOptimized(int[] arr) {
// 动态计算间隔：从 length/2 开始，逐步缩小为1
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 按间隔分组，组内插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
// 找当前元素在组内的插入位置
while (j - gap >= 0 && temp < arr[j - gap]) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
```
五、四大排序算法对比总结
| 排序算法 | 核心思想 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 适用场景 |
| 冒泡排序 | 前后两两对比交换 | O(n²) | O(1) | 稳定 | 小规模数组、近乎有序数组 |
| 简单选择排序 | 找最小值与未排序首元素交换 | O(n²) | O(1) | 不稳定 | 小规模数组、交换成本高场景 |
| 插入排序 | 元素插入已排序序列 | O(n²) | O(1) | 稳定 | 小规模数组、近乎有序数组 |
| 希尔排序 | 分组排序 + 缩小增量 | O(n log₂n) | O(1) | 不稳定 | 中大规模数组 |
六、总结
本文讲解的四种排序算法均为“内部排序”（数据在内存中完成排序），其中冒泡、选择、插入排序属于“简单排序”，时间复杂度为 `O(n²)`，适合小规模数据；希尔排序通过分组优化，时间复杂度降至 `O(n log₂n)`，更适合中大规模数据。
建议初学者先理解每种算法的核心思想，再通过手动模拟（如用小数组走流程）和代码实现加深记忆，后续可进一步学习归并、快速等更高效的排序算法。
更多推荐
16
0- 0
已为社区贡献1条内容
所有评论(0)