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

数据结构学习笔记：排序算法详解与C语言实现

ds 2025/7/19 1:26:25

一、冒泡排序

算法原理

通过重复遍历数组，比较相邻元素并交换位置，将较大的元素逐渐“浮”到数组末尾。

核心代码

void bubble_sort(int *a, int size) {for (int i = 0; i < size - 1; i++) {for (int j = 0; j < size - i - 1; j++) {if (a[j] > a[j + 1]) {int t = a[j];a[j] = a[j + 1];a[j + 1] = t;}}}
}

时间复杂度

最坏/平均：O(n²)
最好（已排序）：O(n)

二、插入排序

算法原理

将数组分为有序区和无序区，逐个将无序区元素插入到有序区的正确位置。

核心代码

void insert_sort(int *a, int size) {for (int i = 1; i < size; i++) {int t = a[i];int j;for (j = i - 1; j >= 0 && a[j] > t; j--) {a[j + 1] = a[j];}a[j + 1] = t;}
}

时间复杂度

最坏/平均：O(n²)
最好（已排序）：O(n)

三、选择排序

算法原理

每次从未排序部分找到最小值，与当前起始位置交换，逐步构建有序序列。

核心代码

void sel_sort(int *a, int size) {for (int i = 0; i < size - 1; i++) {int min_idx = i;for (int j = i + 1; j < size; j++) {if (a[j] < a[min_idx]) {min_idx = j;}}if (min_idx != i) {int t = a[i];a[i] = a[min_idx];a[min_idx] = t;}}
}

时间复杂度

最坏/平均/最好：O(n²)（交换次数少）

四、快速排序

算法原理

通过分治法，选择基准值（pivot），将数组分为小于和大于基准的两部分，递归排序子数组。

核心代码

void quick_sort(int *a, int start, int end) {if (start >= end) return;int i = start, j = end;int pivot = a[start]; // 基准值while (i < j) {while (i < j && a[j] >= pivot) j--;a[i] = a[j];while (i < j && a[i] <= pivot) i++;a[j] = a[i];}a[i] = pivot;quick_sort(a, start, i - 1);quick_sort(a, i + 1, end);
}

时间复杂度

最坏（已排序）：O(n²)
平均：O(n log n)
最好：O(n log n)

五、Shell排序

算法原理

通过分组插入排序，逐步减小组间距离（增量），最终实现整体排序。

核心代码

void shell_sort(int *a, int size) {for (int gap = size / 2; gap > 0; gap /= 2) {for (int i = gap; i < size; i++) {int t = a[i];int j;for (j = i; j >= gap && a[j - gap] > t; j -= gap) {a[j] = a[j - gap];}a[j] = t;}}
}

时间复杂度

最坏：O(n^(1.5))
平均：O(n^(1.3))
改进：通过优化增量序列可进一步提升效率。

六、归并排序

算法原理

分治法将数组拆分为子数组，递归排序后合并有序子数组。

核心代码

void merge_sort(int *a, int start, int end) {if (start >= end) return;int mid = (start + end) / 2;merge_sort(a, start, mid);merge_sort(a, mid + 1, end);// 合并int *temp = (int *)malloc((end - start + 1) * sizeof(int));int i = start, j = mid + 1, k = 0;while (i <= mid && j <= end) {if (a[i] < a[j])temp[k++] = a[i++];elsetemp[k++] = a[j++];}while (i <= mid) temp[k++] = a[i++];while (j <= end) temp[k++] = a[j++];// 复制回原数组for (int t = 0; t < k; t++) {a[start + t] = temp[t];}free(temp);
}

时间复杂度

最坏/平均/最好：O(n log n)
空间复杂度：O(n)

七、算法对比与选择

算法	时间复杂度（最坏）	空间复杂度	稳定性	适用场景
冒泡	O(n²)	O(1)	稳定	小规模或近有序数据
插入	O(n²)	O(1)	稳定	小规模或近有序数据
选择	O(n²)	O(1)	不稳定	交换操作成本低的场景
快速	O(n²)	O(log n)	不稳定	大规模数据（平均高效）
Shell	O(n^(1.5))	O(1)	不稳定	中等规模数据优化插入排序
归并	O(n log n)	O(n)	稳定	大规模数据需稳定性时