01-排序算法

💡 核心结论

排序算法本质

  • 目标：将无序数据按某种规则排列成有序

  • 关键指标：时间复杂度、空间复杂度、稳定性

  • 稳定性：相等元素排序后相对位置不变

  • 选择：根据数据规模、是否原地、是否稳定来选择

算法对比（必须记住）

算法

平均

最坏

最好

空间

稳定

适用场景

冒泡

O(n²)

O(n²)

O(n)

O(1)

✅

小规模、教学

选择

O(n²)

O(n²)

O(n²)

O(1)

❌

写操作代价高

插入

O(n²)

O(n²)

O(n)

O(1)

✅

小规模、近似有序

希尔

O(n^1.3)

O(n²)

O(n)

O(1)

❌

中等规模

归并

O(n log n)

O(n log n)

O(n log n)

O(n)

✅

稳定排序、链表

快排

O(n log n)

O(n²)

O(n log n)

O(log n)

❌

通用首选

堆排序

O(n log n)

O(n log n)

O(n log n)

O(1)

❌

原地排序

计数

O(n+k)

O(n+k)

O(n+k)

O(k)

✅

整数、范围小

桶排序

O(n+k)

O(n²)

O(n)

O(n+k)

✅

均匀分布

基数

O(d(n+k))

O(d(n+k))

O(d(n+k))

O(n+k)

✅

多关键字

选择建议

  • 通用场景：快速排序（平均最快）

  • 需要稳定：归并排序

  • 空间受限：堆排序（原地）

  • 小规模：插入排序（常数小）

  • 近似有序：插入排序

  • 整数范围小：计数排序

  • 链表排序：归并排序

核心思想

  • 比较排序：通过比较决定顺序，下界O(n log n)

  • 非比较排序：利用特殊性质，可以O(n)

  • 分治思想：归并、快排

  • 减治思想：插入、选择

  • 堆结构：堆排序

🔵 冒泡排序

原理

重复遍历，比较相邻元素，逆序则交换，每次把最大元素”冒泡”到末尾。

时间复杂度

  • 最好：O(n) - 已有序，一次遍历

  • 平均：O(n²)

  • 最坏：O(n²) - 逆序

优化

  • 添加flag：一轮没交换则提前结束

  • 记录最后交换位置：减少比较次数

🔴 选择排序

原理

每次从未排序部分选择最小元素，放到已排序部分末尾。

时间复杂度

  • 始终O(n²)，无论数据状态

  • 交换次数O(n)，少于冒泡

🟡 插入排序

原理

将元素插入到已排序部分的正确位置。

时间复杂度

  • 最好：O(n) - 已有序

  • 平均：O(n²)

  • 适合小规模或近似有序数据

🟢 归并排序

原理

分治策略：分割→递归排序→合并。

特点

  • 稳定排序

  • 时间稳定：O(n log n)

  • 空间O(n)：需要额外数组

  • 适合链表：不需要随机访问

应用

  • 外部排序

  • 求逆序对

  • 链表排序

🟣 快速排序

原理

选择pivot，分区使左边<pivot，右边>pivot，递归排序。

特点

  • 平均最快：O(n log n)

  • 最坏O(n²)：已排序数据，需要随机化或三数取中

  • 原地排序：空间O(log n)递归栈

  • 不稳定

优化

  • 三数取中选pivot

  • 小规模用插入排序

  • 三路快排处理重复元素

🟠 堆排序

原理

建最大堆，反复取堆顶放到末尾，调整堆。

特点

  • 时间稳定：O(n log n)

  • 原地排序：O(1)额外空间

  • 不稳定

⚪ 非比较排序

计数排序

  • 适用：整数，范围k不大（k < n log n）

  • 时间：O(n + k)

  • 空间：O(k)

  • 稳定

桶排序

  • 适用：数据均匀分布

  • 时间：O(n)（理想情况）

  • 空间：O(n + k)

基数排序

  • 适用：多关键字排序

  • 时间：O(d(n + k))，d为位数

  • 空间：O(n + k)

🎯 经典应用

1. 第K大元素

# 快速选择：O(n)平均
def findKthLargest(nums, k):
    return quickSelect(nums, len(nums) - k)

# 堆：O(n log k)
def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]

2. 数组中的第K个最大元素

快速选择 > 堆 > 排序

3. 合并K个有序链表

最小堆：O(n log k)

4. 求逆序对

归并排序：O(n log n)

📚 LeetCode练习

基础

应用

💡 面试建议

必须手写

  • 快速排序

  • 归并排序

  • 堆排序

必须理解

  • 时间复杂度分析

  • 稳定性的应用

  • 优化技巧

常见问题

  • 为什么快排平均最快？

    • 缓存友好、原地排序、常数因子小

  • 什么时候用归并？

    • 需要稳定性、链表排序、外部排序

  • 堆排序的优势？

    • 原地、最坏O(n log n)、适合Top K

🔧 优化技巧

1. 小规模用插入

if len(arr) < 10:
    insertion_sort(arr)

2. 快排优化

  • 随机化pivot

  • 三数取中

  • 三路快排

3. 混合排序

# 归并排序 + 插入排序
def merge_sort(arr):
    if len(arr) < 10:
        return insertion_sort(arr)
    # 继续归并

🎯 总结

排序是算法基础，务必掌握：

  1. 理解原理：每种排序的核心思想

  2. 手写实现：至少快排、归并、堆排序

  3. 复杂度分析：时间、空间、稳定性

  4. 应用场景：知道何时用何种排序

  5. 优化技巧：混合排序、随机化等

💻 完整代码实现

Python 实现

  1"""
  2经典排序算法实现
  3"""
  4
  5def bubble_sort(arr):
  6    """冒泡排序：O(n²)
  7    重复遍历，相邻元素逆序则交换
  8    """
  9    n = len(arr)
 10    for i in range(n):
 11        swapped = False
 12        for j in range(n - i - 1):
 13            if arr[j] > arr[j + 1]:
 14                arr[j], arr[j + 1] = arr[j + 1], arr[j]
 15                swapped = True
 16        if not swapped:  # 优化：一轮没交换则已有序
 17            break
 18    return arr
 19
 20
 21def selection_sort(arr):
 22    """选择排序：O(n²)
 23    每次选择最小元素放到已排序部分末尾
 24    """
 25    n = len(arr)
 26    for i in range(n):
 27        min_idx = i
 28        for j in range(i + 1, n):
 29            if arr[j] < arr[min_idx]:
 30                min_idx = j
 31        arr[i], arr[min_idx] = arr[min_idx], arr[i]
 32    return arr
 33
 34
 35def insertion_sort(arr):
 36    """插入排序：O(n²)
 37    将元素插入到已排序部分的正确位置
 38    """
 39    for i in range(1, len(arr)):
 40        key = arr[i]
 41        j = i - 1
 42        while j >= 0 and arr[j] > key:
 43            arr[j + 1] = arr[j]
 44            j -= 1
 45        arr[j + 1] = key
 46    return arr
 47
 48
 49def merge_sort(arr):
 50    """归并排序：O(n log n)
 51    分治策略：分割→递归排序→合并
 52    """
 53    if len(arr) <= 1:
 54        return arr
 55    
 56    mid = len(arr) // 2
 57    left = merge_sort(arr[:mid])
 58    right = merge_sort(arr[mid:])
 59    
 60    return merge(left, right)
 61
 62
 63def merge(left, right):
 64    """合并两个有序数组"""
 65    result = []
 66    i = j = 0
 67    
 68    while i < len(left) and j < len(right):
 69        if left[i] <= right[j]:
 70            result.append(left[i])
 71            i += 1
 72        else:
 73            result.append(right[j])
 74            j += 1
 75    
 76    result.extend(left[i:])
 77    result.extend(right[j:])
 78    return result
 79
 80
 81def quick_sort(arr):
 82    """快速排序：O(n log n)平均
 83    选择pivot，分区，递归
 84    """
 85    if len(arr) <= 1:
 86        return arr
 87    
 88    pivot = arr[len(arr) // 2]
 89    left = [x for x in arr if x < pivot]
 90    middle = [x for x in arr if x == pivot]
 91    right = [x for x in arr if x > pivot]
 92    
 93    return quick_sort(left) + middle + quick_sort(right)
 94
 95
 96def quick_sort_inplace(arr, low=0, high=None):
 97    """原地快速排序"""
 98    if high is None:
 99        high = len(arr) - 1
100    
101    if low < high:
102        pi = partition(arr, low, high)
103        quick_sort_inplace(arr, low, pi - 1)
104        quick_sort_inplace(arr, pi + 1, high)
105    
106    return arr
107
108
109def partition(arr, low, high):
110    """分区函数"""
111    pivot = arr[high]
112    i = low - 1
113    
114    for j in range(low, high):
115        if arr[j] <= pivot:
116            i += 1
117            arr[i], arr[j] = arr[j], arr[i]
118    
119    arr[i + 1], arr[high] = arr[high], arr[i + 1]
120    return i + 1
121
122
123def heap_sort(arr):
124    """堆排序：O(n log n)
125    建最大堆，反复取堆顶
126    """
127    n = len(arr)
128    
129    # 建堆
130    for i in range(n // 2 - 1, -1, -1):
131        heapify(arr, n, i)
132    
133    # 排序
134    for i in range(n - 1, 0, -1):
135        arr[0], arr[i] = arr[i], arr[0]
136        heapify(arr, i, 0)
137    
138    return arr
139
140
141def heapify(arr, n, i):
142    """堆调整"""
143    largest = i
144    left = 2 * i + 1
145    right = 2 * i + 2
146    
147    if left < n and arr[left] > arr[largest]:
148        largest = left
149    if right < n and arr[right] > arr[largest]:
150        largest = right
151    
152    if largest != i:
153        arr[i], arr[largest] = arr[largest], arr[i]
154        heapify(arr, n, largest)
155
156
157def counting_sort(arr):
158    """计数排序：O(n + k)
159    适用于整数，范围不大
160    """
161    if not arr:
162        return arr
163    
164    min_val, max_val = min(arr), max(arr)
165    range_size = max_val - min_val + 1
166    count = [0] * range_size
167    
168    # 计数
169    for num in arr:
170        count[num - min_val] += 1
171    
172    # 累加
173    for i in range(1, range_size):
174        count[i] += count[i - 1]
175    
176    # 输出
177    output = [0] * len(arr)
178    for num in reversed(arr):  # 逆序保证稳定性
179        index = count[num - min_val] - 1
180        output[index] = num
181        count[num - min_val] -= 1
182    
183    return output
184
185
186def test_sorting_algorithms():
187    """测试所有排序算法"""
188    import random
189    import time
190    
191    test_cases = [
192        ([5, 2, 8, 1, 9], "小规模随机"),
193        ([1, 2, 3, 4, 5], "已排序"),
194        ([5, 4, 3, 2, 1], "逆序"),
195        ([3, 3, 2, 1, 2], "重复元素"),
196        (list(range(1000, 0, -1)), "大规模逆序")
197    ]
198    
199    algorithms = [
200        ("冒泡排序", bubble_sort),
201        ("选择排序", selection_sort),
202        ("插入排序", insertion_sort),
203        ("归并排序", merge_sort),
204        ("快速排序", quick_sort),
205        ("原地快排", lambda arr: quick_sort_inplace(arr.copy())),
206        ("堆排序", heap_sort),
207        ("计数排序", counting_sort)
208    ]
209    
210    print("=== 排序算法测试 ===\n")
211    
212    for arr, desc in test_cases[:4]:  # 跳过大规模测试
213        print(f"测试用例: {desc}")
214        print(f"原数组: {arr[:10]}{'...' if len(arr) > 10 else ''}")
215        
216        for name, func in algorithms:
217            test_arr = arr.copy()
218            start = time.time()
219            result = func(test_arr)
220            elapsed = time.time() - start
221            
222            is_sorted = result == sorted(arr)
223            status = "✅" if is_sorted else "❌"
224            print(f"{status} {name:12s}: {elapsed*1000:.3f}ms")
225        
226        print()
227
228
229if __name__ == '__main__':
230    test_sorting_algorithms()
231

C++ 实现

  1/**
  2 * 经典排序算法实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <algorithm>
  8
  9using namespace std;
 10
 11// 冒泡排序
 12void bubbleSort(vector<int>& arr) {
 13    int n = arr.size();
 14    for (int i = 0; i < n; i++) {
 15        bool swapped = false;
 16        for (int j = 0; j < n - i - 1; j++) {
 17            if (arr[j] > arr[j + 1]) {
 18                swap(arr[j], arr[j + 1]);
 19                swapped = true;
 20            }
 21        }
 22        if (!swapped) break;
 23    }
 24}
 25
 26// 选择排序
 27void selectionSort(vector<int>& arr) {
 28    int n = arr.size();
 29    for (int i = 0; i < n; i++) {
 30        int minIdx = i;
 31        for (int j = i + 1; j < n; j++) {
 32            if (arr[j] < arr[minIdx]) {
 33                minIdx = j;
 34            }
 35        }
 36        swap(arr[i], arr[minIdx]);
 37    }
 38}
 39
 40// 插入排序
 41void insertionSort(vector<int>& arr) {
 42    int n = arr.size();
 43    for (int i = 1; i < n; i++) {
 44        int key = arr[i];
 45        int j = i - 1;
 46        while (j >= 0 && arr[j] > key) {
 47            arr[j + 1] = arr[j];
 48            j--;
 49        }
 50        arr[j + 1] = key;
 51    }
 52}
 53
 54// 归并排序
 55void merge(vector<int>& arr, int left, int mid, int right) {
 56    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
 57    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
 58    
 59    int i = 0, j = 0, k = left;
 60    
 61    while (i < L.size() && j < R.size()) {
 62        if (L[i] <= R[j]) {
 63            arr[k++] = L[i++];
 64        } else {
 65            arr[k++] = R[j++];
 66        }
 67    }
 68    
 69    while (i < L.size()) arr[k++] = L[i++];
 70    while (j < R.size()) arr[k++] = R[j++];
 71}
 72
 73void mergeSortHelper(vector<int>& arr, int left, int right) {
 74    if (left < right) {
 75        int mid = left + (right - left) / 2;
 76        mergeSortHelper(arr, left, mid);
 77        mergeSortHelper(arr, mid + 1, right);
 78        merge(arr, left, mid, right);
 79    }
 80}
 81
 82void mergeSort(vector<int>& arr) {
 83    mergeSortHelper(arr, 0, arr.size() - 1);
 84}
 85
 86// 快速排序
 87int partition(vector<int>& arr, int low, int high) {
 88    int pivot = arr[high];
 89    int i = low - 1;
 90    
 91    for (int j = low; j < high; j++) {
 92        if (arr[j] <= pivot) {
 93            i++;
 94            swap(arr[i], arr[j]);
 95        }
 96    }
 97    swap(arr[i + 1], arr[high]);
 98    return i + 1;
 99}
100
101void quickSortHelper(vector<int>& arr, int low, int high) {
102    if (low < high) {
103        int pi = partition(arr, low, high);
104        quickSortHelper(arr, low, pi - 1);
105        quickSortHelper(arr, pi + 1, high);
106    }
107}
108
109void quickSort(vector<int>& arr) {
110    quickSortHelper(arr, 0, arr.size() - 1);
111}
112
113// 堆排序
114void heapify(vector<int>& arr, int n, int i) {
115    int largest = i;
116    int left = 2 * i + 1;
117    int right = 2 * i + 2;
118    
119    if (left < n && arr[left] > arr[largest])
120        largest = left;
121    if (right < n && arr[right] > arr[largest])
122        largest = right;
123    
124    if (largest != i) {
125        swap(arr[i], arr[largest]);
126        heapify(arr, n, largest);
127    }
128}
129
130void heapSort(vector<int>& arr) {
131    int n = arr.size();
132    
133    // 建堆
134    for (int i = n / 2 - 1; i >= 0; i--) {
135        heapify(arr, n, i);
136    }
137    
138    // 排序
139    for (int i = n - 1; i > 0; i--) {
140        swap(arr[0], arr[i]);
141        heapify(arr, i, 0);
142    }
143}
144
145// 打印数组
146void printArray(const vector<int>& arr, const string& name) {
147    cout << name << ": [";
148    for (size_t i = 0; i < arr.size(); i++) {
149        cout << arr[i];
150        if (i < arr.size() - 1) cout << ", ";
151    }
152    cout << "]" << endl;
153}
154
155int main() {
156    cout << "=== 排序算法演示 ===" << endl << endl;
157    
158    vector<int> original = {5, 2, 8, 1, 9, 3, 7};
159    
160    vector<int> arr = original;
161    bubbleSort(arr);
162    printArray(arr, "冒泡排序");
163    
164    arr = original;
165    selectionSort(arr);
166    printArray(arr, "选择排序");
167    
168    arr = original;
169    insertionSort(arr);
170    printArray(arr, "插入排序");
171    
172    arr = original;
173    mergeSort(arr);
174    printArray(arr, "归并排序");
175    
176    arr = original;
177    quickSort(arr);
178    printArray(arr, "快速排序");
179    
180    arr = original;
181    heapSort(arr);
182    printArray(arr, "堆排序");
183    
184    return 0;
185}