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

常见排序算法详解与C语言实现

news 2025/6/6 10:18:04

1. 冒泡排序(Bubble Sort)

2. 选择排序(Selection Sort)

3. 插入排序(Insertion Sort)

4. 希尔排序(Shell Sort)

5. 堆排序(Heap Sort)

6. 快速排序(Quick Sort)

7. 归并排序(Merge Sort)

总结

引言

排序算法是计算机科学中最基础也是最重要的算法之一。本文将详细介绍七种常见的排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序和归并排序，并给出每种算法的C语言实现代码。

1. 冒泡排序(Bubble Sort)

冒泡排序是最简单的排序算法之一，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，直到列表排序完成。

演示：
初始数组：[5, 3, 8, 6, 2]

第一轮：

比较5和3 → 交换 → [3,5,8,6,2]
比较5和8 → 不交换
比较8和6 → 交换 → [3,5,6,8,2]
比较8和2 → 交换 → [3,5,6,2,8] (8已到位)

第二轮：

比较3和5 → 不交换
比较5和6 → 不交换
比较6和2 → 交换 → [3,5,2,6,8] (6已到位)

第三轮：

比较3和5 → 不交换
比较5和2 → 交换 → [3,2,5,6,8] (5已到位)

第四轮：

比较3和2 → 交换 → [2,3,5,6,8] (排序完成)

void bob(int *a, int size)
{// 外层循环控制排序轮数for (int i = 0; i < size; i++){// 内层循环控制每轮比较次数for (int j = i + 1; j < size; j++){// 如果前一个元素大于后一个元素，则交换if (a[i] > a[j]){int temp = a[i];a[i] = a[j];a[j] = temp;}}}
}

时间复杂度：

最好情况：O(n)（已经排序的情况）
平均和最坏情况：O(n²)

空间复杂度：O(1)

2. 选择排序(Selection Sort)

选择排序每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。

演示：
初始数组：[5, 3, 8, 6, 2]

第一轮：

找到最小值2 → 与5交换 → [2,3,8,6,5] (2已到位)

第二轮：

在[3,8,6,5]中找到最小值3 → 已在位置 → [2,3,8,6,5]

第三轮：

在[8,6,5]中找到最小值5 → 与8交换 → [2,3,5,6,8] (5已到位)

第四轮：

在[6,8]中找到最小值6 → 已在位置 → [2,3,5,6,8] (排序完成)

void sel(int *a, int size)
{// 外层循环控制已排序部分的末尾for (int i = 0; i < size; i++){int min_index = i;  // 假设当前元素是最小的// 内层循环查找未排序部分的最小元素for (int j = i + 1; j < size; j++){// 如果找到更小的元素，更新最小元素索引if (a[min_index] > a[j]){min_index = j;}}// 如果最小元素不是当前元素，则交换if (min_index != i){swap(&a[i], &a[min_index]);}}
}

时间复杂度：始终为O(n²)

空间复杂度：O(1)

3. 插入排序(Insertion Sort)

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

演示：
初始数组：[5, 3, 8, 6, 2]

第一步：

已排序[5], 未排序[3,8,6,2]
插入3 → 3<5 → [3,5,8,6,2]

第二步：

已排序[3,5], 未排序[8,6,2]
插入8 → 8>5 → [3,5,8,6,2]

第三步：

已排序[3,5,8], 未排序[6,2]
插入6 → 6<8 → [3,5,6,8,2]

第四步：

已排序[3,5,6,8], 未排序[2]
插入2 → 2<8 → 2<6 → 2<5 → 2<3 → [2,3,5,6,8] (排序完成)

void insert(int *a, int size)
{// 从第二个元素开始（第一个元素视为已排序）for (int i = 1; i < size; i++){int k = a[i];   // 当前要插入的元素int j = i - 1;  // 已排序部分的最后一个元素索引// 将大于当前元素的已排序元素后移while (j >= 0 && a[j] > k){a[j + 1] = a[j];j--;}// 将当前元素插入到正确位置a[j + 1] = k;}
}

时间复杂度：

最好情况：O(n)（已经排序的情况）
平均和最坏情况：O(n²)

空间复杂度：O(1)

4. 希尔排序(Shell Sort)

希尔排序是插入排序的改进版本，通过将原始列表分成多个子列表来提高插入排序的性能。

演示：
初始数组：[5, 3, 8, 6, 2, 9, 1, 7, 4]

第一轮(间隔=4)：

子序列1：[5,2,4] → 排序后[2,4,5]
子序列2：[3,9] → 排序后[3,9]
子序列3：[8,1] → 排序后[1,8]
子序列4：[6,7] → 排序后[6,7]
数组变为：[2,3,1,6,4,9,8,7,5]

第二轮(间隔=2)：

子序列1：[2,1,4,8,5] → 排序后[1,2,4,5,8]
子序列2：[3,6,9,7] → 排序后[3,6,7,9]
数组变为：[1,3,2,6,4,7,5,9,8]

第三轮(间隔=1)：

标准插入排序 → [1,2,3,4,5,6,7,8,9]

void shell(int *a, int size)
{// 初始间隔为数组长度的一半，逐步缩小间隔for (int gap = size / 2; gap > 0; gap /= 2){// 对每个间隔分组进行插入排序for (int i = gap; i < size; i++){int temp = a[i];  // 当前要插入的元素int j;// 组内插入排序for (j = i; j >= gap && a[j - gap] > temp; j -= gap){a[j] = a[j - gap];}a[j] = temp;  // 插入元素到正确位置}}
}

时间复杂度：取决于间隔序列，最好可达O(n log²n)

空间复杂度：O(1)

5. 堆排序(Heap Sort)

堆排序利用堆这种数据结构所设计的一种排序算法，是一种选择排序。

演示：
初始数组：[5, 3, 8, 6, 2]

构建最大堆：

从最后一个非叶子节点(6)开始调整：
- 6>2 → 不交换
调整节点3：
- 3<8 → 交换 → [5,8,3,6,2]
- 3无子节点 → 停止
调整节点5：
- 5<8 → 交换 → [8,5,3,6,2]
- 5>2 → 不交换

堆排序过程：

交换堆顶8和末尾2 → [2,5,3,6,8] (8已排序)
调整堆：
- 2<5 → 交换 → [5,2,3,6,8]
- 2<3 → 交换 → [5,3,2,6,8]
交换堆顶5和末尾2 → [2,3,5,6,8] (5,6,8已排序)
调整堆：
- 2<3 → 交换 → [3,2,5,6,8]
交换堆顶3和末尾2 → [2,3,5,6,8] (排序完成)

void heapify(int *a, int size, int i)
{int largest = i;         // 初始化最大元素为当前节点int left = i * 2 + 1;    // 左子节点索引int right = i * 2 + 2;   // 右子节点索引// 如果左子节点存在且大于当前最大节点if (left < size && a[left] > a[largest]){largest = left;}// 如果右子节点存在且大于当前最大节点if (right < size && a[right] > a[largest]){largest = right;}// 如果最大节点不是当前节点，交换并继续调整if (largest != i){swap(&a[i], &a[largest]);heapify(a, size, largest);}
}void heapsort(int *a, int size)
{// 构建最大堆（从最后一个非叶子节点开始）for (int i = size / 2 - 1; i >= 0; i--){heapify(a, size, i);}// 逐个提取堆顶元素（最大值）并调整堆for (int i = size - 1; i >= 0; i--){// 将堆顶元素（最大值）与当前末尾元素交换swap(&a[0], &a[i]);// 调整剩余元素使其保持堆性质heapify(a, i, 0);}
}

时间复杂度：O(n logn)

空间复杂度：O(1)

6. 快速排序(Quick Sort)

快速排序是一种分治算法，它选择一个"基准"元素，将数组分为两部分，一部分小于基准，一部分大于基准，然后递归地对这两部分进行排序。

演示：
初始数组：[5, 3, 8, 6, 2]

第一轮(基准=2)：

2是最小值 → 分区后：[2,5,3,8,6]
左子数组空，右子数组[5,3,8,6]

第二轮(基准=6)：

分区过程：
- 5<6 → i=0 → [5,3,8,6]
- 3<6 → i=1 → [5,3,8,6]
- 8>6 → 不移动
交换a[i+1]和基准 → [5,3,6,8]
左子数组[5,3], 右子数组[8]

第三轮(左子数组基准=3)：

分区后：[3,5]
排序完成

最终结果：[2,3,5,6,8]

void quicksort(int *a, int left, int right)
{if (left < right){// 选择最后一个元素作为基准值int pivot = a[right];int i = left - 1;  // 小于基准值的元素分界点// 分区过程：将所有小于等于基准的元素移到左边for (int j = left; j < right; j++){if (a[j] <= pivot){i++;swap(&a[i], &a[j]);}}// 将基准值放到正确位置swap(&a[i + 1], &a[right]);int pivot_index = i + 1;// 递归排序左右两部分quicksort(a, left, pivot_index - 1);quicksort(a, pivot_index + 1, right);}
}

时间复杂度：

最好和平均情况：O(n logn)
最坏情况：O(n²)（当数组已经排序或逆序时）

空间复杂度：O(logn)（递归调用栈）

7. 归并排序(Merge Sort)

归并排序是一种分治算法，它将数组分成两半，递归地对每一半进行排序，然后将两个有序的半部分合并成一个有序的整体。

演示：
初始数组：[5, 3, 8, 6, 2]

拆分过程：
[5,3,8,6,2] → [5,3,8]和[6,2]
[5,3,8] → [5,3]和[8]
[5,3] → [5]和[3]
[6,2] → [6]和[2]

合并过程：

合并[5]和[3] → [3,5]
合并[3,5]和[8] → [3,5,8]
合并[6]和[2] → [2,6]
合并[3,5,8]和[2,6]：
- 比较3和2 → 取2 → [2]
- 比较3和6 → 取3 → [2,3]
- 比较5和6 → 取5 → [2,3,5]
- 比较8和6 → 取6 → [2,3,5,6]
- 剩余8 → [2,3,5,6,8]

void merge(int *a, int l, int m, int r)
{int n1 = m - l + 1;  // 左子数组长度int n2 = r - m;       // 右子数组长度int i, j, k;// 分配临时数组存储左右子数组int *L = (int *)malloc(n1 * sizeof(int));int *R = (int *)malloc(n2 * sizeof(int));// 拷贝数据到临时数组for (i = 0; i < n1; i++){L[i] = a[l + i];}for (j = 0; j < n2; j++){R[j] = a[m + 1 + j];}// 合并两个有序子数组i = 0;     // 左子数组索引j = 0;     // 右子数组索引k = l;     // 合并后数组索引while (i < n1 && j < n2){if (L[i] <= R[j]){a[k] = L[i];i++;}else{a[k] = R[j];j++;}k++;}// 拷贝左子数组剩余元素while (i < n1){a[k] = L[i];i++;k++;}// 拷贝右子数组剩余元素while (j < n2){a[k] = R[j];j++;k++;}// 释放临时数组内存free(L);free(R);
}void mergeSort(int arr[], int left, int right)
{if (left < right){// 计算中间索引（防止整数溢出）int mid = left + (right - left) / 2;// 递归排序左半部分mergeSort(arr, left, mid);// 递归排序右半部分mergeSort(arr, mid + 1, right);// 合并两个已排序的子数组merge(arr, left, mid, right);}
}

时间复杂度：始终为O(n logn)

空间复杂度：O(n)（需要额外的存储空间）

总结

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n logn)~O(n²)	O(n logn)	O(n²)	O(1)	不稳定
堆排序	O(n logn)	O(n logn)	O(n logn)	O(1)	不稳定
快速排序	O(n logn)	O(n logn)	O(n²)	O(logn)	不稳定
归并排序	O(n logn)	O(n logn)	O(n logn)	O(n)	稳定