八大经典算法>排序算法
目录
1. 算法概览
| 算法>排序算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 排序方式 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 | In-place |
| 选择排序 | O(n²) | O(1) | 不稳定 | In-place |
| 插入排序 | O(n²) | O(1) | 稳定 | In-place |
| 希尔排序 | O(n log n) | O(1) | 不稳定 | In-place |
| 归并排序 | O(n log n) | O(n) | 稳定 | Out-place |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | In-place |
| 堆排序 | O(n log n) | O(1) | 不稳定 | In-place |
| 计数排序 | O(n + k) | O(k) | 稳定 | Out-place |
2. 算法详解
2.1 冒泡排序
基本思想：通过相邻元素比较交换，使最大元素"浮"到末尾
动图演示：气泡从水底逐渐上浮的过程
void bubble_sort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int 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; // 提前终止优化}
}
2.2 选择排序
基本思想：每次选择最小元素放到已排序序列末尾
void selection_sort(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;}swap(&arr[i], &arr[min_idx]);}
}
2.3 插入排序
基本思想：将未排序元素插入已排序序列合适位置
void insertion_sort(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;}
}
2.4 希尔排序
基本思想：分组插入排序，逐步缩小间隔
void shell_sort(int arr[], int n) {for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j-gap] > temp; j -= gap)arr[j] = arr[j-gap];arr[j] = temp;}}
}
2.5 归并排序
基本思想：分治法，先拆分再合并有序子序列
void merge(int arr[], int l, int m, int r) {// 合并操作实现
}void merge_sort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l)/2;merge_sort(arr, l, m);merge_sort(arr, m+1, r);merge(arr, l, m, r);}
}
2.6 快速排序
基本思想：选取基准值进行分区排序
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i+1], &arr[high]);return i+1;
}void quick_sort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quick_sort(arr, low, pi-1);quick_sort(arr, pi+1, high);}
}
2.7 堆排序
基本思想：利用堆结构进行选择排序
void heapify(int arr[], int n, int i) {// 堆调整实现
}void heap_sort(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--) {swap(&arr[0], &arr[i]);heapify(arr, i, 0);}
}
2.8 计数排序
适用场景：整数排序，数据范围较小
void counting_sort(int arr[], int n) {int max = arr[0], min = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}int range = max - min + 1;int *count = calloc(range, sizeof(int));for (int i = 0; i < n; i++)count[arr[i] - min]++;int idx = 0;for (int i = 0; i < range; i++) {while (count[i]--) arr[idx++] = i + min;}free(count);
}
3. 性能对比
| 算法>排序算法 | 最佳情况 | 最差情况 | 适用场景 |
|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | 小规模数据/基本有序数据 |
| 快速排序 | O(n log n) | O(n²) | 通用排序/大规模随机数据 |
| 归并排序 | O(n log n) | O(n log n) | 链表排序/外部排序 |
| 堆排序 | O(n log n) | O(n log n) | 内存受限场景 |
| 计数排序 | O(n + k) | O(n + k) | 整数排序/范围较小数据 |
选择建议：
- 小规模数据：插入排序
- 通用场景：快速排序
- 稳定性要求：归并排序
- 内存敏感：堆排序
- 特殊场景：计数排序（数据范围小）
完整代码实现建议在本地IDE中测试运行，理解算法原理后尝试手写实现
