八大经典排序算法

八大经典排序算法 目录 算法概览算法详解 冒泡排序选择排序插入排序希尔排序归并排序快速排序堆排序计数排序 性能对比

---

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中测试运行，理解算法原理后尝试手写实现