排序算法详解、应用对比与C语言实现

四种经典排序算法详解（原理+动图+代码）

一、排序算法的重要性

排序算法是计算机科学领域最基础的算法之一，在数据库索引、搜索引擎优化、大数据分析等领域有广泛应用。根据Stack Overflow 2022开发者调查，超过83%的面试会考察算法实现能力，其中排序算法是必考题型。

排序算法应用场景
（图示：电商平台价格排序、学生成绩排名等实际应用场景）

二、基础排序算法详解

2.1 冒泡排序（Bubble Sort）

算法原理

通过相邻元素两两比较，将最大值"冒泡"到数组末尾。每轮遍历减少一个比较元素。

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int 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;}}}
}

过程演示（以数组[5,3,8,6,4]为例）

初始状态：5 3 8 6 4
第1轮：
3 5 8 6 4 → 3 5 6 8 4 → 3 5 6 4 8
第2轮：
3 5 6 4 → 3 5 4 6 
第3轮： 
3 5 4 → 3 4 5
第4轮：
3 4 → 完成排序

2.2 插入排序（Insertion Sort）

算法特点

时间复杂度：O(n²)（最坏）
空间复杂度：O(1)
稳定排序
适合小规模数据或基本有序数据

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;}
}

过程演示（以数组[5, 2, 9, 1, 5]为例）

未排序部分: [5, 2, 9, 1, 5]
已排序部分: []
第一步：
将第一个元素（5）视为已排序部分。
未排序部分: [2, 9, 1, 5]
已排序部分: [5]
第二步：
取未排序部分的第一个元素（2），与已排序部分的元素比较。
2 小于 5，将 5 向后移动，插入 2。
未排序部分: [9, 1, 5]
已排序部分: [2, 5]
第三步：
取未排序部分的下一个元素（9），与已排序部分的元素比较。
9 大于 5，直接插入到已排序部分的末尾。
未排序部分: [1, 5]
已排序部分: [2, 5, 9]
第四步：
取未排序部分的下一个元素（1），与已排序部分的元素比较。
1 小于 9，将 9 向后移动。
1 小于 5，将 5 向后移动。
1 小于 2，将 2 向后移动，插入 1。
未排序部分: [5]
已排序部分: [1, 2, 5, 9]
第五步：
取未排序部分的最后一个元素（5），与已排序部分的元素比较。
5 小于 9，将 9 向后移动。
5 等于已排序部分的最后一个元素（也是5），直接插入到该位置（或者保持不变，因为相等）。
未排序部分: []
已排序部分: [1, 2, 5, 5, 9]最终排序结果：
[1, 2, 5, 5, 9]

三、高效排序算法解析

3.1 快速排序（Quick Sort）

核心思想

分治策略：选取基准值（pivot），将数组划分为两个子数组，递归排序。

int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high-1; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i+1], &arr[high]);return (i + 1);
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

快速排序分区过程图示
在这里插入图片描述

3.2 归并排序（Merge Sort）

算法优势

稳定排序
时间复杂度稳定O(n log n)
适合链表结构排序
可用于外部排序

void merge(int arr[], int l, int m, int r) {// 合并两个有序子数组int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 处理剩余元素while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}

归并排序过程图示
在这里插入图片描述

四、排序算法综合对比

算法	时间复杂度（平均）	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(1)	稳定	教学演示
快速排序	O(n log n)	O(log n)	不稳定	通用排序
归并排序	O(n log n)	O(n)	稳定	大数据量、外部排序
堆排序	O(n log n)	O(1)	不稳定	内存受限场景

扩展：主流排序算法综合对比
在这里插入图片描述

五、工程实践建议

小数据量（n < 100）：优先使用插入排序
通用场景：采用快速排序（如C语言qsort函数）
稳定性要求：选择归并排序（如Java的Arrays.sort）
内存敏感：使用堆排序
数据基本有序：考虑冒泡排序优化版

// 优化版冒泡排序（增加交换标志）
void optimizedBubbleSort(int arr[], int n) {int swapped;for (int i = 0; i < n-1; i++) {swapped = 0;for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(&arr[j], &arr[j+1]);swapped = 1;}}if (!swapped) break;}
}