以下为排序算法专题的全面总结，涵盖核心原理、应用场景、典型题目及大厂面试考点，并提供 Python/Java/C++ 三语言实现对比。

---

一、排序算法基础分类与原理

1. 分类维度

• 时间复杂度
  • O(n²)：冒泡、选择、插入排序
  • O(n log n)：快速、归并、堆排序
  • O(n)：计数、桶、基数排序（需数据特殊分布）
• 稳定性
  • 稳定：插入、归并、冒泡、基数排序（相等元素相对位置不变）
  • 不稳定：快速、堆、希尔、选择排序
• 空间复杂度
  • 原地排序（O(1)）：冒泡、选择、插入、希尔、堆、快速排序
  • 非原地排序：归并（O(n)）、计数（O(k)）、桶（O(n+k)）

2. 核心思想

• 分治：快速排序（选基准分区）、归并排序（先分后并）
• 选择极值：堆排序（建堆取顶）、选择排序（遍历选最小）
• 插入与调整：插入排序（有序区扩张）、希尔排序（增量分组插入）

---

二、十大排序算法详解与三语言实现

1. 快速排序（Quick Sort）

原理：选取枢轴（pivot）分区，递归排序子数组。
优化：三数取中法避免最坏情况（O(n²)）
三语言实现：

# Python
def quick_sort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

// Java
public 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);
    }
}
private 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, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

// C++
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);
    }
}
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

2. 归并排序（Merge Sort）

原理：递归分治，合并有序子序列。
应用场景：外部排序、链表排序（稳定且O(n log n)）
三语言实现：

# Python
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[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

// Java
public void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
private void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int[] L = new int[n1], R = new int[n2];
    System.arraycopy(arr, l, L, 0, n1);
    System.arraycopy(arr, m + 1, R, 0, n2);
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// C++
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

3. 堆排序（Heap Sort）

原理：构建最大堆，交换堆顶与末尾元素，调整堆
应用场景：Top K 问题、优先队列
C++ 优化示例：

void heapify(int arr[], int n, int i) {
    int largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

4. 线性排序（非比较类）

算法	适用条件	核心操作
计数排序	数据范围小（如0~100整数）	统计频次 → 累加频次 → 反向填充
桶排序	数据均匀分布	分桶 → 桶内排序 → 合并
基数排序	整数/字符串（按位分割）	LSD（从低位到高位分配收集）

---

三、大厂面试高频考点与典型题目

1. 高频考点

• 手写算法：快速排序分区函数、堆排序调整堆
• 时间复杂度分析：
  • 快排最坏情况（O(n²)）及优化（随机枢轴）
  • 归并排序空间复杂度（O(n)）与链表优化
• 稳定性辨析：为什么快速排序不稳定？ （分区交换破坏相对位置）
• 场景选择：
  • 海量数据+内存有限 → 归并排序（外部排序）
  • 数据基本有序 → 插入排序（O(n)）

2. 典型题目

1. 合并K个升序链表（LeetCode 23）
   解法：最小堆维护链表头节点（Java PriorityQueue）

   PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
   

2. 数组中的第K个最大元素（LeetCode 215）
   解法：快速选择（QuickSelect，平均O(n)）或堆排序（O(n log k)）
3. 颜色分类（荷兰国旗问题，LeetCode 75）
   解法：三向切分快速排序（一次遍历分区）

   # Python
   def sortColors(nums):
       lo, i, hi = 0, 0, len(nums) - 1
       while i <= hi:
           if nums[i] == 0:
               nums[lo], nums[i] = nums[i], nums[lo]
               lo += 1
               i += 1
           elif nums[i] == 2:
               nums[i], nums[hi] = nums[hi], nums[i]
               hi -= 1
           else:
               i += 1
   

---

四、排序算法综合对比与选型建议

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	通用首选（缓存友好）
归并排序	O(n log n)	O(n log n)	O(n)	稳定	外部排序、链表排序
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	Top K 问题、无递归栈限制
插入排序	O(n²)	O(n²)	O(1)	稳定	小规模或基本有序数据
计数排序	O(n + k)	O(n + k)	O(k)	稳定	小范围非负整数（如年龄排序）
基数排序	O(n × k)	O(n × k)	O(n + k)	稳定	电话号码、字符串字典序排序

选型指南：

• 数据规模小（n ≤ 100）：插入排序（稳定）或冒泡排序（教学用）
• 数据规模大+内存充足：快速排序（平均最快）
• 数据规模大+内存不足：归并排序（外部排序）
• 需稳定排序：归并排序（或插入排序用于小数据）
• 数据有范围限制：计数排序/桶排序

---

💡 大厂面试技巧：

1. 重点掌握 快速排序（手写分区）、归并排序（链表合并）、堆排序（建堆与调整）；
2. 辨析 稳定性场景（如数据库索引排序需稳定）；
3. 线性排序（计数/基数）常考 衍生问题（如基数排序处理浮点数）。