快速排序与希尔排序实战解析

一、今天学习目标希尔排序插入排序升级版快速排序最常用、面试必考完整可运行代码复杂度对比二、希尔排序Shell Sort思想分组做插入排序逐步缩小增量gap最后 gap1 时就是普通插入排序但数组已经基本有序非常快// 希尔排序 void shellSort(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; } } }三、快速排序Quick Sort思想选一个基准 pivot小的放左边大的放右边递归左右两部分平均复杂度O(n log n)实际最快。// 交换 void swap(int *a, int *b) { int t *a; *a *b; *b t; } // 划分函数 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 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); } }四、完整测试代码#include stdio.h // swap、shellSort、quickSort、partition 都放这里 void printArr(int arr[], int n) { for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); } int main() { int arr1[] {9, 3, 7, 1, 5, 2, 8, 4, 6}; int n sizeof(arr1) / sizeof(arr1[0]); printf(原数组); printArr(arr1, n); shellSort(arr1, n); printf(希尔排序后); printArr(arr1, n); int arr2[] {9, 3, 7, 1, 5, 2, 8, 4, 6}; quickSort(arr2, 0, n - 1); printf(快速排序后); printArr(arr2, n); return 0; }运行结果原数组9 3 7 1 5 2 8 4 6 希尔排序后1 2 3 4 5 6 7 8 9 快速排序后1 2 3 4 5 6 7 8 9五、复杂度对比表格算法时间复杂度稳定性希尔O(n log n) ~ O(n²)不稳定快排O (n log n) 平均不稳定六、今日小练习对数组{6, 1, 8, 3, 5, 2, 7, 4}分别使用希尔排序、快速排序并输出结果。