排序算法学习
c算法
本文介绍了C语言中常用的排序算法，包括内置库函数qsort()、简单排序算法如冒泡排序、选择排序和插入排序，以及高效排序算法如快速排序、归并排序和堆排序，还提及了线性时间排序方法如计数排序和基数排序。读者可以了解各类算法的实现原理、时间与空间复杂度及适用场景，从而根据实际需求选择合适算法，提升编程效率与代码性能。文章亮点在于详细对比了不同算法的优缺点，并提供了实用建议，帮助开发者优化排序操作。
目录
在C语言中，对数组进行排序有多种方式，主要可以分为以下几类：
1. 内置库函数
qsort() 函数
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int arr[] = {5, 2, 8, 1, 9};
int n = sizeof(arr)/sizeof(arr[0]);
qsort(arr, n, sizeof(int), compare);- 时间复杂度：平均 O(n log n)，最坏 O(n²)
- 特点：C标准库提供的快速排序实现
2. 简单排序算法
冒泡排序 (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;
}
}
}
}- 时间复杂度：O(n²)
- 空间复杂度：O(1)
选择排序 (Selection Sort)
void selectionSort(int arr[], int n) {
for(int i = 0; i < n-1; i++) {
int min_idx = i;
for(int j = i+1; j < n; j++) {
if(arr[j] < arr[min_idx])
min_idx = j;
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}- 时间复杂度：O(n²)
- 空间复杂度：O(1)
插入排序 (Insertion Sort)
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;
}
}- 时间复杂度：O(n²)（最坏），O(n)（最好，已排序）
- 空间复杂度：O(1)
3. 高效排序算法
快速排序 (Quick Sort)
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 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);
}- 时间复杂度：平均 O(n log n)，最坏 O(n²)
- 空间复杂度：O(log n)
归并排序 (Merge Sort)
void mergeSort(int arr[], int l, int r) {
if(l < r) {
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r) {
// 合并两个有序子数组
}- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
堆排序 (Heap Sort)
void heapSort(int arr[], int n) {
for(int i = n/2-1; i >= 0; i--)
heapify(arr, n, i);
for(int i = n-1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
// 构建最大堆
}- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
4. 线性时间排序（特定条件下）
计数排序 (Counting Sort)
- 时间复杂度：O(n + k)，k是数据范围
- 适用条件：整数排序，数据范围较小
基数排序 (Radix Sort)
- 时间复杂度：O(d(n + k))，d是数字位数
- 适用条件：整数排序
总结对比
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| qsort() | O(n log n) | O(n²) | O(log n) | 依赖实现 |
建议：
- 小数据量：插入排序
- 通用场景：qsort() 或快速排序
- 需要稳定性：归并排序
- 内存敏感：堆排序
- 特定条件：计数排序或基数排序