排序

三路快排（原地）¶

In [25]:

Copied!





def quick_sort_3way(nums):

    def sort(low, high):
        # 区间长度小于等于1时，结束递归
        if high <= low:
            return
        # 选取当前区间第一个元素作为基准值
        pivot = nums[low]
        lt = low    # 小于区的右边界
        gt = high   # 大于区的左边界
        i = low + 1 # 当前扫描指针
        """
        nums[low : lt-1] < pivot
        nums[lt : i-1] == pivot
        nums[i : gt] 未处理
        nums[gt+1 : high] > pivot
        """
        # 扫描到大于区间的左边界，表示全部元素已扫描
        while i <= gt:
            # 当前元素小于基准
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
            else:
                i += 1
        sort(low, lt - 1)
        sort(gt + 1, high)
    sort(0, len(nums) - 1)
nums = [200, 100 ,6, 10, 4, 10]
quick_sort_3way(nums)
nums
def quick_sort_3way(nums):

    def sort(low, high):
        # 区间长度小于等于1时，结束递归
        if high <= low:
            return
        # 选取当前区间第一个元素作为基准值
        pivot = nums[low]
        lt = low    # 小于区的右边界
        gt = high   # 大于区的左边界
        i = low + 1 # 当前扫描指针
        """
        nums[low : lt-1] < pivot
        nums[lt : i-1] == pivot
        nums[i : gt] 未处理
        nums[gt+1 : high] > pivot
        """
        # 扫描到大于区间的左边界，表示全部元素已扫描
        while i <= gt:
            # 当前元素小于基准
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
            else:
                i += 1
        sort(low, lt - 1)
        sort(gt + 1, high)
    sort(0, len(nums) - 1)
nums = [200, 100 ,6, 10, 4, 10]
quick_sort_3way(nums)
nums

Out[25]:

[4, 6, 10, 10, 100, 200]

完整状态追踪：nums = [200, 100, 6, 10, 4, 10]¶

第一层：sort(0, 5)，pivot = 200¶

初始：[200, 100,  6, 10,  4, 10]
       lt↑                   gt↑
            i↑

i=1: 100 < 200 → swap(lt=0, i=1) → [100, 200,  6, 10,  4, 10]，lt=1, i=2
i=2:   6 < 200 → swap(lt=1, i=2) → [100,   6,200, 10,  4, 10]，lt=2, i=3
i=3:  10 < 200 → swap(lt=2, i=3) → [100,   6, 10,200,  4, 10]，lt=3, i=4
i=4:   4 < 200 → swap(lt=3, i=4) → [100,   6, 10,  4,200, 10]，lt=4, i=5
i=5:  10 < 200 → swap(lt=4, i=5) → [100,   6, 10,  4, 10,200]，lt=5, i=6

结束：[100,  6, 10,  4, 10 | 200 |]
      <200区间[0..4]         ==区  >区(空)

递归：sort(0, 4) ／ sort(6, 5) 退出

第二层：sort(0, 4)，pivot = 100¶

初始：[100,  6, 10,  4, 10]
       lt↑               gt↑
            i↑

i=1:  6 < 100 → swap(lt=0, i=1) → [ 6,100, 10,  4, 10]，lt=1, i=2
i=2: 10 < 100 → swap(lt=1, i=2) → [ 6, 10,100,  4, 10]，lt=2, i=3
i=3:  4 < 100 → swap(lt=2, i=3) → [ 6, 10,  4,100, 10]，lt=3, i=4
i=4: 10 < 100 → swap(lt=3, i=4) → [ 6, 10,  4, 10,100]，lt=4, i=5

结束：[ 6, 10,  4, 10 | 100 |]
      <100区间[0..3]    ==区  >区(空)

递归：sort(0, 3) ／ sort(5, 4) 退出

第三层：sort(0, 3)，pivot = 6¶

初始：[ 6, 10,  4, 10]
       lt↑          gt↑
            i↑

i=1: 10 > 6 → swap(i=1, gt=3) → [ 6, 10,  4, 10]（值相同）, gt=2, i不动
i=1: 10 > 6 → swap(i=1, gt=2) → [ 6,  4, 10, 10]，         gt=1, i不动
i=1:  4 < 6 → swap(lt=0, i=1) → [ 4,  6, 10, 10]，lt=1, i=2

结束：[ 4 | 6 | 10, 10]
      <6区  ==区  >6区[2..3]

递归：sort(0, 0) 退出／ sort(2, 3)

第四层：sort(2, 3)，pivot = 10¶

初始：[10, 10]
       lt↑  gt↑
            i↑

i=3: 10 == 10 → i=4

结束：[| 10, 10 |]
      <区(空) ==区  >区(空)

递归全部退出。

最终结果¶

[4, 6, 10, 10, 100, 200] ✓

为何 `gt -= 1` 时不能 `i += 1`¶

三个分支的逻辑不对称，根本原因在于换过来的元素是否已被检查过：

分支	换来的元素来自哪里	是否已检查	能否推进 i
`nums[i] < pivot`	`nums[lt]`，必然是 `== pivot` 的元素	已知，无需再判断	✅ `i += 1`
`nums[i] == pivot`	无交换	当前元素已判断完毕	✅ `i += 1`
`nums[i] > pivot`	`nums[gt]`，来自未处理区，值未知	未检查	❌ 不能推进

当 nums[i] > pivot 时，把 nums[gt] 换到位置 i 后，这个新来的元素可能小于、等于或大于 pivot，必须在下一轮重新判断。若此时贸然 i += 1，这个元素就被永远跳过，导致排序错误。

三路快排（非原地）¶

In [9]:

Copied!





import random
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = random.choice(nums)
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    l_list = quick_sort(left)
    r_list = quick_sort(right)
    return l_list + middle + r_list
arr = [10, 7, 8, 9, 1, 20]
sorted_arr = quick_sort(arr)
print(f"原始数组: {arr}")
print(f"排序后数组: {sorted_arr}")
import random
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = random.choice(nums)
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    l_list = quick_sort(left)
    r_list = quick_sort(right)
    return l_list + middle + r_list
arr = [10, 7, 8, 9, 1, 20]
sorted_arr = quick_sort(arr)
print(f"原始数组: {arr}")
print(f"排序后数组: {sorted_arr}")

原始数组: [10, 7, 8, 9, 1, 20]
排序后数组: [1, 7, 8, 9, 10, 20]

快速排序复杂度分析

一、每层的代价：O(n)

left   = [x for x in arr if x < pivot]
right  = [x for x in arr if x > pivot]
middle = [x for x in arr if x == pivot]
return quick_sort_basic(left) + middle + quick_sort_basic(right)

每次调用做两件事：三次列表推导式遍历 O(n)，以及列表拼接（Python + 会申请新内存逐元素复制）O(n)，合计单次调用代价为 O(n)。

二、时间复杂度：O(n log n)

时间复杂度的分析使用递归树横向分层模型，这是一种统计总工作量的思维工具，与实际执行顺序无关。

将递归树按层切割，观察每一层所有子问题处理的元素总数：

第 1 层：[10, 7, 8, 9, 1, 5]              → 处理 6 个元素
第 2 层：[1, 5, 7]        [9, 10]          → 合计 6 个
第 3 层：[1]  [5]  [7]    [9]  [10]        → 合计 6 个

每一层所有子问题的元素总数始终为 n，每层代价为 O(n)。pivot 随机选取时，平均每次将数组折半，递归树共 O(log n) 层。

$$T(n) = O(n) \times O(\log n) = O(n \log n)$$

最坏情况下（每次 pivot 取到边界值），树退化为一条链，深度变为 O(n)，总时间退化为 O(n²)。

三、空间复杂度：O(n)

这里需要区分分析模型与实际执行，两者回答的是不同问题。

实际执行：深度优先

Python 递归是深度优先执行的，并非同时处理某一整层：

quick_sort_basic([10,7,8,9,1,5])
  └─ quick_sort_basic(left)        ← 一路递归到底
       └─ quick_sort_basic(left)
            └─ ... 到 len<=1 返回
  ← 左边全部完成，才开始
  └─ quick_sort_basic(right)

因此，任意时刻内存中存活的，只有从根到当前节点这一条路径上的临时列表，而非某一整层的所有列表。

内存峰值计算

这条路径上每层的列表大小平均折半：

$$n + \frac{n}{2} + \frac{n}{4} + \cdots + 1 = 2n = O(n)$$

因此内存峰值为 O(n)。

两种视角的对比

分析视角	回答的问题	结论
递归树横向分层	总计算量是多少？	O(n log n)
实际深度优先执行	内存峰值是多少？	O(n)

与原地快排对比： 原地快排不创建临时列表，空间仅来自调用栈本身，为 O(log n)。本实现额外创建了 left/middle/right 列表，使峰值从 O(log n) 升至 O(n)，是此实现相对于原地排序的主要代价。

四、汇总

	平均情况	最坏情况
时间复杂度	O(n log n)	O(n²)
空间复杂度（峰值）	O(n)	O(n)
递归深度	O(log n)	O(n)

排序算法系统总结¶

一、排序算法核心评价指标¶

排序算法通常从三个维度评价：

指标	含义
时间复杂度	最好 / 平均 / 最坏情况
空间复杂度	是否需要额外辅助空间
稳定性	相同元素排序后相对顺序是否改变

补充面试常问指标：

指标	含义
是否原地排序	是否只使用 O(1) 额外空间（递归栈除外）
是否基于比较	是否依赖元素大小比较

二、基础比较排序¶

基础排序是理解高级排序的基础。

排序思想发展路径：

冒泡排序
→ 选择排序
→ 插入排序
→ 希尔排序

2.1 冒泡排序（稳定原地排序）¶

思想：

相邻元素两两比较，将较大元素逐步交换到数组末尾。

标准实现：

def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:
            break

复杂度：

指标	值
最好	O(n)
平均	O(n²)
最坏	O(n²)
空间	O(1)
稳定	是
是否原地	是

适用场景：

数据基本有序时效率较高

2.2 选择排序（原地但不稳定）¶

思想：

每轮选择未排序区最小元素放入已排序区末尾。

def selection_sort(nums):
    n = len(nums)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]

关键特点：

交换次数最少（最多 n 次）

复杂度：

指标	值
时间复杂度	O(n²)
空间复杂度	O(1)
稳定性	否
是否原地	是

注意：

选择排序不能减少比较次数，因此无法突破 O(n²)

2.3 插入排序（稳定原地排序）¶

思想：

维护一个已排序区，将新元素插入正确位置。

def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key

复杂度：

指标	值
最好	O(n)
平均	O(n²)
最坏	O(n²)
空间	O(1)
稳定	是
是否原地	是

特点：

小规模数据排序最佳选择之一

工程排序的重要子模块

2.4 希尔排序（插入排序优化版）¶

思想：

通过 gap 分组降低移动距离。

def shell_sort(nums):
    n = len(nums)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            key = nums[i]
            j = i
            while j >= gap and nums[j - gap] > key:
                nums[j] = nums[j - gap]
                j -= gap
            nums[j] = key
        gap //= 2

复杂度：

依赖 gap 序列：

指标	值
平均复杂度	优于 O(n²)
最坏复杂度	O(n²)
空间复杂度	O(1)
稳定性	否
是否原地	是

说明：

不存在统一精确复杂度表达式

三、分治排序（核心面试重点）¶

包括：

归并排序
快速排序

3.1 归并排序（稳定但非原地）¶

思想：

递归拆分数组后再合并有序数组。

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    
    mid = len(nums) // 2
    
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    
    return merge(left, right)


def merge(left, right):

    result = []
    
    i = j = 0
    
    while i < len(left) and j < len(right):
        
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

复杂度：

指标	值
时间复杂度	O(n log n)
空间复杂度	O(n)
稳定性	是
是否原地	否

说明：

标准实现需要辅助数组

链表排序优选归并排序

3.2 快速排序（最重要排序算法）¶

核心思想：

Partition 分区

小于 pivot
pivot
大于 pivot

递归排序左右区域

3.2.1 Lomuto 分区¶

简单直观版本

def lomuto_partition(nums, low, high):
    
    pivot = nums[high]
    
    i = low - 1
    
    for j in range(low, high):
        
        if nums[j] <= pivot:
            
            i += 1
            
            nums[i], nums[j] = nums[j], nums[i]
    
    nums[i + 1], nums[high] = nums[high], nums[i + 1]
    
    return i + 1


def quick_sort_lomuto(nums, low, high):
    
    if low < high:
        
        pi = lomuto_partition(nums, low, high)
        
        quick_sort_lomuto(nums, low, pi - 1)
        
        quick_sort_lomuto(nums, pi + 1, high)

特点：

实现简单

交换次数较多

3.2.2 Hoare 分区¶

效率更高版本

def hoare_partition(nums, low, high):

    pivot = nums[low]
    
    i = low - 1
    j = high + 1
    
    while True:
        
        i += 1
        
        while nums[i] < pivot:
            i += 1
        
        j -= 1
        
        while nums[j] > pivot:
            j -= 1
        
        if i >= j:
            return j
        
        nums[i], nums[j] = nums[j], nums[i]


def quick_sort_hoare(nums, low, high):

    if low < high:
        
        pi = hoare_partition(nums, low, high)
        
        quick_sort_hoare(nums, low, pi)
        
        quick_sort_hoare(nums, pi + 1, high)

特点：

交换次数更少

性能优于 Lomuto

3.2.3 三路快排（处理重复元素最优方案）¶

思想：

分为三段：

< pivot
= pivot
> pivot

def quick_sort_3way(nums, low, high):

    if low >= high:
        return
    
    pivot = nums[low]
    
    lt = low
    gt = high
    
    i = low + 1
    
    while i <= gt:
        
        if nums[i] < pivot:
            
            nums[lt], nums[i] = nums[i], nums[lt]
            
            lt += 1
            
            i += 1
        
        elif nums[i] > pivot:
            
            nums[gt], nums[i] = nums[i], nums[gt]
            
            gt -= 1
        
        else:
            i += 1
    
    
    quick_sort_3way(nums, low, lt - 1)
    
    quick_sort_3way(nums, gt + 1, high)

复杂度：

指标	值
平均复杂度	O(n log n)
最坏复杂度	O(n²)
空间复杂度	O(log n)
稳定性	否
是否原地	是

说明：

重复元素多时优势明显

快排工程优化策略总结¶

工程级优化包括：

随机 pivot
三数取中 pivot
三路切分
小数组使用插入排序
递归深度过大切换堆排序

形成：

introsort
pdqsort

四、堆排序（原地非稳定排序）¶

思想：

构建最大堆

依次交换堆顶元素

def heapify(nums, n, i):

    largest = i
    
    l = 2 * i + 1
    r = 2 * i + 2
    
    if l < n and nums[l] > nums[largest]:
        largest = l
    
    if r < n and nums[r] > nums[largest]:
        largest = r
    
    if largest != i:
        
        nums[i], nums[largest] = nums[largest], nums[i]
        
        heapify(nums, n, largest)


def heap_sort(nums):

    n = len(nums)
    
    for i in range(n // 2 - 1, -1, -1):
        heapify(nums, n, i)
    
    for i in range(n - 1, 0, -1):
        
        nums[0], nums[i] = nums[i], nums[0]
        
        heapify(nums, i, 0)

复杂度：

指标	值
时间复杂度	O(n log n)
空间复杂度	O(1)
稳定性	否
是否原地	是

说明：

递归实现存在 O(log n) 调用栈空间

五、非比较排序¶

突破比较排序下界：

O(n log n)

5.1 计数排序¶

适用于：

整数范围有限场景

复杂度：

O(n + k)

稳定性：

取决于实现方式（可稳定）

空间：

O(k)

5.2 桶排序¶

思想：

分桶 + 桶内排序

复杂度：

平均：

O(n)

最坏：

O(n²)

稳定性：

取决于桶内排序方式

5.3 基数排序¶

思想：

按位排序

依赖稳定排序作为子过程

复杂度：

O(d(n+k))

稳定性：

可稳定（前提子排序稳定）

六、工程级排序算法¶

现代语言排序采用混合排序策略

Timsort¶

使用语言：

Python

Java

结构：

归并排序
+
插入排序
+
run 检测

特点：

稳定排序

利用局部有序性

Introsort¶

结构：

快速排序
+
堆排序
+
插入排序

特点：

防止退化

C++ STL 使用

pdqsort¶

结构：

三路快排
+
模式检测
+
堆排序 fallback
+
插入排序优化

特点：

现代最快通用排序之一

Rust / Go 使用

七、排序算法综合对比表¶

算法	平均时间	最坏时间	空间	稳定	原地
冒泡排序	O(n²)	O(n²)	O(1)	是	是
选择排序	O(n²)	O(n²)	O(1)	否	是
插入排序	O(n²)	O(n²)	O(1)	是	是
希尔排序	优于 O(n²)	O(n²)	O(1)	否	是
归并排序	O(n log n)	O(n log n)	O(n)	是	否
快速排序	O(n log n)	O(n²)	O(log n)	否	是
三路快排	O(n log n)	O(n²)	O(log n)	否	是
堆排序	O(n log n)	O(n log n)	O(1)	否	是
计数排序	O(n+k)	O(n+k)	O(k)	可稳定	否
桶排序	O(n)	O(n²)	O(n)	可稳定	否
基数排序	O(d(n+k))	O(d(n+k))	O(n+k)	可稳定	否

八、面试建议排序算法掌握优先级¶

推荐掌握顺序：

第一优先级：

快速排序（三路）
归并排序
堆排序

第二优先级：

插入排序
希尔排序

第三优先级：

计数排序
桶排序
基数排序

工程级理解即可：

Timsort
Introsort
pdqsort

快速选择¶

你的判断也是对的。很多场景下我们只需要找到"第 k 大/小的元素"，而不需要整个数组有序。快速选择正是利用快速排序的分区思想，每次分区后根据 k 与各区间边界的位置关系，只递归进入目标所在的那一侧，丢弃另一侧，从而将平均时间复杂度从 O(n log n) 降至 O(n)。

常见算法中与"选择"相关的算法主要有三个：

算法	平均时间	最坏时间	特点
快速选择	O(n)	O(n²)	最常用，实现简单
堆选择	O(n log k)	O(n log k)	适合数据流、k 较小的场景
BFPRT（中位数的中位数）	O(n)	O(n)	理论最优，常数大，工程少用

面试和工程中绝大多数情况只需掌握快速选择即可。

核心思想对比快速排序¶

快速排序在分区后两侧都要递归，快速选择在分区后只递归目标所在的一侧。每次递归问题规模平均减半，因此总工作量是 n + n/2 + n/4 + ... ≈ 2n，即 O(n)。这是快速选择效率远高于先排序再取值的根本原因。

In [ ]:

Copied!





import random

def quick_select(nums, k):
    """
    返回 nums 中第 k 小的元素（k 从 1 开始）
    例如 k=1 返回最小值，k=len(nums) 返回最大值
    """

    def select(low, high, k):
        # 区间只有一个元素，直接返回
        if low == high:
            return nums[low]

        # 随机选取 pivot，避免最坏情况
        pivot_index = random.randint(low, high)
        nums[low], nums[pivot_index] = nums[pivot_index], nums[low]

        # 三路分区，与三路快排完全相同
        pivot = nums[low]
        lt = low        # 小于区右边界
        gt = high       # 大于区左边界
        i = low + 1     # 当前扫描指针

        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
                # 注意：不能 i += 1，换来的元素未经检查
            else:
                i += 1

        # 分区结束后：
        # nums[low..lt-1] < pivot，共 lt - low 个
        # nums[lt..gt]   == pivot，共 gt - lt + 1 个
        # nums[gt+1..high] > pivot
        # 注意这里的第k大，按照升序，应该是k-1
        if k-1 <= lt-1:
            # 第 k 小在小于区
            return select(low, lt - 1, k)
        elif k-1 >= gt + 1:
            # 第 k 小在大于区
            return select(gt + 1, high, k)
        else:
            # 第 k 小恰好在等于区，直接返回 pivot
            return pivot

    return select(0, len(nums) - 1, k)
# 如果想要找第K大，
# 则 return select(0, n - 1, n - k + 1)
# 第 k 大 = 第 (n-k+1) 小

# 测试
nums = [3, 2, 1, 5, 6, 4] 
print(quick_select(nums, 2))  # 输出 2，第 2 小
print(quick_select(nums, 5))  # 输出 5，第 5 小
import random

def quick_select(nums, k):
    """
    返回 nums 中第 k 小的元素（k 从 1 开始）
    例如 k=1 返回最小值，k=len(nums) 返回最大值
    """

    def select(low, high, k):
        # 区间只有一个元素，直接返回
        if low == high:
            return nums[low]

        # 随机选取 pivot，避免最坏情况
        pivot_index = random.randint(low, high)
        nums[low], nums[pivot_index] = nums[pivot_index], nums[low]

        # 三路分区，与三路快排完全相同
        pivot = nums[low]
        lt = low        # 小于区右边界
        gt = high       # 大于区左边界
        i = low + 1     # 当前扫描指针

        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[gt], nums[i] = nums[i], nums[gt]
                gt -= 1
                # 注意：不能 i += 1，换来的元素未经检查
            else:
                i += 1

        # 分区结束后：
        # nums[low..lt-1] < pivot，共 lt - low 个
        # nums[lt..gt]   == pivot，共 gt - lt + 1 个
        # nums[gt+1..high] > pivot
        # 注意这里的第k大，按照升序，应该是k-1
        if k-1 <= lt-1:
            # 第 k 小在小于区
            return select(low, lt - 1, k)
        elif k-1 >= gt + 1:
            # 第 k 小在大于区
            return select(gt + 1, high, k)
        else:
            # 第 k 小恰好在等于区，直接返回 pivot
            return pivot

    return select(0, len(nums) - 1, k)
# 如果想要找第K大，
# 则 return select(0, n - 1, n - k + 1)
# 第 k 大 = 第 (n-k+1) 小

# 测试
nums = [3, 2, 1, 5, 6, 4] 
print(quick_select(nums, 2))  # 输出 2，第 2 小
print(quick_select(nums, 5))  # 输出 5，第 5 小

2
5

排序

三路快排（原地）¶

完整状态追踪：nums = [200, 100, 6, 10, 4, 10]¶

第一层：sort(0, 5)，pivot = 200¶

第二层：sort(0, 4)，pivot = 100¶

第三层：sort(0, 3)，pivot = 6¶

第四层：sort(2, 3)，pivot = 10¶

最终结果¶

为何 gt -= 1 时不能 i += 1¶

三路快排（非原地）¶

排序算法系统总结¶

一、排序算法核心评价指标¶

二、基础比较排序¶

2.1 冒泡排序（稳定原地排序）¶

2.2 选择排序（原地但不稳定）¶

2.3 插入排序（稳定原地排序）¶

2.4 希尔排序（插入排序优化版）¶

三、分治排序（核心面试重点）¶

3.1 归并排序（稳定但非原地）¶

3.2 快速排序（最重要排序算法）¶

3.2.1 Lomuto 分区¶

3.2.2 Hoare 分区¶

3.2.3 三路快排（处理重复元素最优方案）¶

快排工程优化策略总结¶

四、堆排序（原地非稳定排序）¶

五、非比较排序¶

5.1 计数排序¶

5.2 桶排序¶

5.3 基数排序¶

六、工程级排序算法¶

Timsort¶

Introsort¶

pdqsort¶

七、排序算法综合对比表¶

八、面试建议排序算法掌握优先级¶

快速选择¶

核心思想对比快速排序¶

为何 `gt -= 1` 时不能 `i += 1`¶