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

一、今天学习目标

1. 希尔排序（插入排序升级版）
2. 快速排序（最常用、面试必考）
3. 完整可运行代码
4. 复杂度对比

二、希尔排序（Shell Sort）

思想：

• 分组做插入排序
• 逐步缩小增量（gap）
• 最后 gap=1 时就是普通插入排序，但数组已经基本有序，非常快

// 希尔排序 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

五、复杂度对比

表格

六、今日小练习

对数组{6, 1, 8, 3, 5, 2, 7, 4}分别使用希尔排序、快速排序并输出结果。