说说常见排序算法及时间复杂度（快排的原理和复杂度）？

## 1. 常见排序算法及复杂度对比 | 算法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | | ------------------------ | ---------- | ---------- | ---------- | ---------------- | --- | | **冒泡排序**（Bubble Sort） | O(n) | O(n²) | O(n²) | O(1) | 稳定 | | **选择排序**（Selection Sort） | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | | **插入排序**（Insertion Sort） | O(n) | O(n²) | O(n²) | O(1) | 稳定 | | **希尔排序**（Shell Sort） | O(n log n) | 约 O(n¹·³) | O(n²) | O(1) | 不稳定 | | **归并排序**（Merge Sort） | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | | **快速排序**（Quick Sort） | O(n log n) | O(n log n) | O(n²) | O(log n) \~ O(n) | 不稳定 | | **堆排序**（Heap Sort） | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | | **计数排序**（Counting Sort） | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | | **桶排序**（Bucket Sort） | O(n + k) | O(n + k) | O(n²) | O(n + k) | 稳定 | | **基数排序**（Radix Sort） | O(n·k) | O(n·k) | O(n·k) | O(n + k) | 稳定 | > 注：k 为数据范围或桶数，n 为元素个数。 ## 2. 快速排序原理 快速排序（Quick Sort）是**分治思想**的典型应用： 1. **选择基准值**（pivot） * 常用方法：选第一个元素、最后一个元素、随机选、三数取中（避免退化） 2. **分区（partition）** * 将数组分成两部分：小于基准值的放左边，大于基准值的放右边 3. **递归** * 对左右两个子序列递归重复步骤 1、2，直到子序列长度为 1 或 0 ### 核心分区代码（Lomuto 方案） ```java int partition(int[] arr, int left, int right) { int pivot = arr[right]; // 基准 int i = left; for (int j = left; j < right; j++) { if (arr[j] < pivot) { swap(arr, i, j); i++; } } swap(arr, i, right); return i; } void quickSort(int[] arr, int left, int right) { if (left < right) { int p = partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p + 1, right); } } ``` ## 3. 快速排序复杂度分析 * **平均时间复杂度**：O(n log n) * 每次分区约把数组分成两半： T(n) = 2·T(n/2) + O(n) → O(n log n) * **最好时间复杂度**：O(n log n) * 每次分区都正好一半一半 * **最坏时间复杂度**：O(n²) * 如果每次选到的 pivot 都是最大值或最小值（例如数组已排好序且不做随机化） * 分区极不均衡：T(n) = T(n-1) + O(n) → O(n²) * **空间复杂度**： * 递归栈深度平均 O(log n)，最坏 O(n) ## 4. 快排性能优化手段 1. **随机化基准** * 减少退化概率，例如 `pivot = arr[left + rand.nextInt(right - left + 1)]` 2. **三数取中** * 选 `left`、`mid`、`right` 中的中位数作 pivot 3. **小数组用插入排序** * 当子数组长度 < 10 时切换到插排 4. **尾递归优化** * 优先递归较小的一边，另一边用循环代替，减少栈深