八大经典排序算法

2025/2/21 22:34:42 来源：https://blog.csdn.net/qq_19406475/article/details/145713833 浏览: 次关键词：八大经典排序算法

八大经典排序算法

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)	整数排序/范围较小数据