当前位置：首页 > news >正文

【数据结构】排序算法：冒泡与快速

news 2025/7/3 13:01:06

引言：排序算法的重要性

排序算法是计算机科学的基础核心，直接影响程序性能和资源消耗。在C语言开发中，理解不同排序算法的特性对编写高效代码至关重要。本文将深入分析两种经典排序算法：简单直观的冒泡排序和高效快速的快速排序，并提供完整的C语言实现。

冒泡排序：简单但低效

基本思想

冒泡排序通过相邻元素比较交换，使较大元素逐渐移动到数组末端，如同气泡上浮。

C语言实现

#include <stdio.h>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;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr)/sizeof(arr[0]);bubbleSort(arr, n);printf("排序结果：");for (int i=0; i<n; i++) printf("%d ", arr[i]);return 0;
}

性能分析

时间复杂度：
- 最优：O(n)（已排序数组，可添加标志位优化）
- 最差：O(n²)（完全逆序）
- 平均：O(n²)
空间复杂度：O(1)（原地排序）
稳定性：稳定（相等元素不交换）

优化版本（带提前终止）

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]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;swapped = 1;}}if (swapped == 0) break; // 无交换说明已有序}
}

快速排序：高效分治策略

基本思想

快速排序采用分治法：

选取基准元素（pivot）
将数组分为小于和大于基准的两部分
递归排序子数组

C语言实现

#include <stdio.h>// 分区函数
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++;// 交换元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准放到正确位置int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;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);}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr)/sizeof(arr[0]);quickSort(arr, 0, n-1);printf("排序结果：");for (int i=0; i<n; i++) printf("%d ", arr[i]);return 0;
}
性能分析

时间复杂度：
- 最优：O(n log n)（平衡分区）
- 最差：O(n²)（极端不平衡分区）
- 平均：O(n log n)
空间复杂度：O(log n)（递归栈空间）
稳定性：不稳定（分区可能改变相同元素顺序）

优化技巧

基准选择优化（避免最坏情况）：

// 三数取中法选择基准
int medianOfThree(int arr[], int low, int high) {int mid = low + (high - low)/2;if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);return mid;
}

小数组切换插入排序：

void quickSortOptimized(int arr[], int low, int high) {if (high - low < 10) { // 阈值可调整insertionSort(arr, low, high);return;}// 正常快速排序流程...
}

对比与选型指南

特性	冒泡排序	快速排序
时间复杂度	O(n²)	O(n log n)平均
空间复杂度	O(1)	O(log n)
稳定性	稳定	不稳定
适用场景	小规模或基本有序数据	通用大规模数据排序
代码复杂度	简单	中等

实际开发建议

优先考虑快速排序：适用于大多数通用排序需求
特殊场景选择：
- 数据量小（n<100）：冒泡或插入排序
- 需要稳定性：归并排序
- 内存受限：堆排序
工程实践：直接使用标准库函数（如C的qsort()）

C标准库qsort示例

#include <stdlib.h>int compare(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}int main() {int arr[] = {10, 5, 8, 1, 4};int n = sizeof(arr)/sizeof(arr[0]);qsort(arr, n, sizeof(int), compare);// 输出排序结果...return 0;
}