文章目录
本文将介绍常见排序算法，包括算法思想、代码实现（C++和Python）、时间复杂度对比及不同排序间的比较。
排序算法对比
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 适用场景 | 是否原地 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | 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 log n) | O(n log²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 log n) | O(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 +k) | O(n²) | O(n +k) | 稳定 | 均匀分布数据 | 否 |
| 基数排序 | O(d(n +k)) | O(d(n +k)) | O(d(n +k)) | O(n +k) | 稳定 | 多位数整数 | 否 |
算法逐一介绍
1. 冒泡排序（Bubble Sort）
- 思想：相邻元素比较交换，将最大元素逐步“冒泡”到末尾。
- 时间复杂度：
- 平均/最坏：O(n²)
- 最好（已有序）：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
C++代码：
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
bool swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped) break;
}
}
Python代码：
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
swapped = False
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
2. 选择排序（Selection Sort）
- 思想：每次选择最小元素放到已排序序列末尾。
- 时间复杂度：
- 平均/最好/最坏：O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
C++代码：
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) min_idx = j;
}
swap(arr[i], arr[min_idx]);
}
}
Python代码：
def selection_sort(arr):
n = len(arr)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
3. 插入排序（Insertion Sort）
- 思想：逐个将元素插入到已排序序列的正确位置。
- 时间复杂度：
- 平均/最坏：O(n²)
- 最好（已有序）：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
C++代码：
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i], j = i-1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
Python代码：
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j]:
arr[j+1] = arr[j]
j -=1
arr[j+1] = key
return arr
4. 希尔排序（Shell Sort）
- 思想：分组插入排序，逐步缩小间隔。
- 时间复杂度：O(n log n) ~ O(n²)（取决于间隔序列）
- 空间复杂度：O(1)
- 稳定性：不稳定
C++代码：
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], j;
for (j = i; j >= gap && arr[j-gap] > temp; j -= gap)
arr[j] = arr[j-gap];
arr[j] = temp;
}
}
}
Python代码：
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
5. 归并排序（Merge Sort）
- 思想：分治法，递归排序后合并。
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
- 稳定性：稳定
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) return;
int m = l + (r - l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
Python代码：
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L, R = arr[:mid], arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i +=1
else:
arr[k] = R[j]
j +=1
k +=1
while i < len(L):
arr[k] = L[i]
i +=1; k +=1
while j < len(R):
arr[k] = R[j]
j +=1; k +=1
return arr
6. 快速排序（Quick Sort）
- 思想：分治法，选基准分区，递归排序。
- 时间复杂度：
- 平均/最好：O(n log n)
- 最坏（已有序）：O(n²)
- 空间复杂度：O(log n)（递归栈）
- 稳定性：不稳定
C++代码：
int partition(int arr[], int low, int high) {
int pivot = arr[high], 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);
}
}
Python代码：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x <= pivot]
right = [x for x in arr[:-1] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
7. 堆排序（Heap Sort）
- 思想：构建最大堆，交换堆顶元素并调整堆。
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 稳定性：不稳定
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);
}
}
Python代码：
def heapify(arr, n, i):
largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n//2-1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
8. 计数排序（Counting Sort）
- 思想：统计元素出现次数，按顺序输出。
- 时间复杂度：O(n + k)（k为数据范围）
- 空间复杂度：O(k)
- 稳定性：稳定
C++代码：
void countingSort(int arr[], int n, int max_val) {
int output[n], count[max_val+1] = {0};
for (int i = 0; i < n; i++) count[arr[i]]++;
for (int i = 1; i <= max_val; i++) count[i] += count[i-1];
for (int i = n-1; i >=0; i--) output[--count[arr[i]]] = arr[i];
for (int i = 0; i < n; i++) arr[i] = output[i];
}
Python代码：
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
for num in arr:
count[num] +=1
i = 0
for num in range(max_val +1):
while count[num] >0:
arr[i] = num
i +=1
count[num] -=1
return arr
9. 桶排序（Bucket Sort）
- 思想：分桶后分别排序，合并结果。
- 时间复杂度：
- 平均：O(n + k)
- 最坏：O(n²)
- 空间复杂度：O(n + k)
- 稳定性：稳定（取决于桶内排序算法）
C++代码：
void bucketSort(float arr[], int n) {
vector<float> buckets[n];
for (int i = 0; i < n; i++) {
int bi = n * arr[i];
buckets[bi].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
sort(buckets[i].begin(), buckets[i].end());
int index = 0;
for (int i = 0; i < n; i++)
for (float num : buckets[i])
arr[index++] = num;
}
Python代码：
def bucket_sort(arr):
max_val, min_val = max(arr), min(arr)
bucket_size = (max_val - min_val) / len(arr)
buckets = [[] for _ in range(len(arr))]
for num in arr:
idx = int((num - min_val) // bucket_size)
if idx == len(buckets):
idx -=1
buckets[idx].append(num)
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
10. 基数排序（Radix Sort）
- 思想：按位排序，从低位到高位。
- 时间复杂度：O(d(n + k))（d为位数）
- 空间复杂度：O(n + k)
- 稳定性：稳定
C++代码：
void countingSortForRadix(int arr[], int n, int exp) {
int output[n], count[10] = {0};
for (int i = 0; i < n; i++) count[(arr[i]/exp)%10]++;
for (int i = 1; i < 10; i++) count[i] += count[i-1];
for (int i = n-1; i >=0; i--) {
output[count[(arr[i]/exp)%10]-1] = arr[i];
count[(arr[i]/exp)%10]--;
}
for (int i = 0; i < n; i++) arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max_val = *max_element(arr, arr+n);
for (int exp = 1; max_val/exp >0; exp *=10)
countingSortForRadix(arr, n, exp);
}
Python代码：
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp >0:
counting_sort_by_digit(arr, exp)
exp *=10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0]*n
count = [0]*10
for i in range(n):
index = (arr[i] // exp) %10
count[index] +=1
for i in range(1,10):
count[i] += count[i-1]
for i in range(n-1, -1, -1):
index = (arr[i] // exp) %10
output[count[index]-1] = arr[i]
count[index] -=1
for i in range(n):
arr[i] = output[i]
总结
- 冒泡、选择、插入排序：适用于小规模数据。
- 希尔排序：中等规模数据，优于插入排序。
- 归并、快速、堆排序：大规模数据，归并稳定但需额外空间，快速排序平均最快，堆排序原地排序。
- 计数、桶、基数排序：特定场景下高效（如整数范围小、均匀分布、多位数）。
非常好的问题！在数据结构与算法考试、面试（尤其是大厂）中，虽然排序算法很多，但常考的排序算法主要集中在下面这几种，因为它们代表了不同的思想和场景优化策略：
关于备考
✅ 必考 or 高频排序算法
| 排序算法 | 说明 / 考察点 | 为什么常考 |
|---|---|---|
| 快速排序 | 分治、原地、非稳定排序 | 最常用的高效通用排序，面试常要求手写 |
| 归并排序 | 分治、稳定排序、空间换时间 | 经常考在链表中排序（Leetcode经典） |
| 堆排序 | 二叉堆结构、原地排序、优先队列基础 | 常作为Top K 问题基础 |
| 插入排序 | 稳定、简单，考察基本理解 | 代码简单，适合考察写基础排序 |
| 计数排序 | 线性时间排序代表 | 理解适用范围 + 稳定排序基础 |
| 冒泡排序 | 教学用、面试中考“你写一个最基础排序” | 了解基本交换机制 |
| 桶/基数排序 | 高效但场景特定 | 高级笔试题中出现，用于浮点/大数据位排序 |
🎯 企业面试中高频考察点
- 写一个快速排序（原地/非递归）
- 链表使用归并排序排序 O(n log n)
- 从数据流中找第K大（堆排序）
- Top K 频率元素（堆 + 计数）
- 计数排序 vs 比较类排序差别（适用场景）
- 给定整数数组用基数排序排序
🧠 拓展建议
| 方向 | 建议练习题 |
|---|---|
| 📚 基础写法 | 快速排序、归并排序、堆排序手写 |
| 🔍 排序思想 | 比较类 vs 非比较类排序的适用场景 |
| 📈 排序优化 | 小数组用插入排序，大数组快速+归并 |
| 🧪 Leetcode | #215, #912, #148, #347, #451 等 |
🎯 排序算法面试核心知识清单
✅ 高频要求手写的排序算法
| 算法 | 重点考察方向 | 稳定性 | 原地 |
|---|---|---|---|
| 快速排序 | 分治思想、原地实现、递归/非递归 | ❌ | ✅ |
| 归并排序 | 分治思想、链表排序实现 | ✅ | ❌ |
| 堆排序 | 大顶堆构建、Top K 使用 | ❌ | ✅ |
| 插入排序 | 简单直接、部分有序数组快 | ✅ | ✅ |
🔝 面试高频 Leetcode 题目（附关键词）
| 题目编号 | 名称 | 涉及排序类型 | 难度 |
|---|---|---|---|
| #912 | 排序数组 | 快速/归并排序 | 🟠 中等 |
| #215 | 数组第K大元素 | 快排/堆排序 | 🟠 中等 |
| #347 | 前K高频元素 | 堆 + 计数排序思想 | 🟠 中等 |
| #148 | 链表排序 | 归并排序 | 🔵 困难 |
| #451 | 按频率排序 | 计数 + 自定义排序 | 🟠 中等 |
🧩 排序面试思维框架（你可以这样答）
🌟 经典问题：快速排序的时间复杂度？
- 平均：O(n log n)
- 最坏：O(n²)（已排序数组）
- 优化：三路快排、随机pivot
🌟 高级问题：为什么说归并适合链表？
- 不依赖随机访问
- 可以轻松实现O(1)空间的链表归并
- 稳定、时间复杂度始终 O(n log n)
🌟 扩展：非比较类排序的适用场景？
- 计数排序：整数，范围小
- 基数排序：整数、位数小（如手机号、身份证）
- 桶排序：小数、浮点数、分布均匀
🧠 排序算法复习笔记（面试 & 考试专用）
一、排序算法分类
| 分类 | 算法 | 稳定性 | 是否原地 | 时间复杂度（平均） | 时间复杂度（最坏） | 适用场景 |
|---|---|---|---|---|---|---|
| 比较类排序 | 冒泡、插入、选择、归并、快速、堆 | 插入/冒泡/归并 ✅ 其余 ❌ | 归并 ❌ 其余 ✅ | O(n^2)/O(nlogn) | O(n^2)/O(nlogn) | 通用排序 |
| 非比较类排序 | 计数、桶、基数 | ✅ | ❌ | O(n)/O(nk) | O(n)/O(nk) | 整数/位数小/范围有限的排序场景 |
二、常考排序算法精讲
1. 快速排序（Quick Sort）
- 思想：分治 + 原地交换
- 特点：高效，最常用，平均 O(nlogn)，最坏 O(n^2)
- 代码：C++/Python（略，见代码库）
- 常考形式：手写实现；找第K大元素；排序 + 去重
2. 归并排序（Merge Sort）
- 思想：分治 + 合并
- 特点：稳定，适合链表，空间复杂度 O(n)
- 常考形式：链表排序；大数据排序
3. 堆排序（Heap Sort）
- 思想：最大堆构建 + 弹出堆顶
- 特点：原地，不稳定，优先队列基础
- 常考形式：Top K 问题，最大/最小K个数
4. 插入排序（Insertion Sort）
- 思想：构建有序序列，将新元素插入
- 特点：适合小数组、基本有序场景
5. 计数排序（Counting Sort）
- 思想：统计频次 -> 回写数组
- 特点：非比较排序，稳定，O(n+k)，适合范围小的整数
6. 基数排序（Radix Sort）
- 思想：按位排序（低位到高位）
- 特点：适合大整数排序；与计数结合使用
三、面试高频题推荐
| Leetcode 编号 | 题目 | 重点算法 |
|---|---|---|
| 912 | Sort an Array | 快排 / 归并 |
| 215 | Kth Largest Element in Array | 快排 / 堆排序 |
| 347 | Top K Frequent Elements | 堆 + 计数排序思想 |
| 148 | Sort List | 归并（链表版） |
| 451 | Sort Characters by Frequency | 计数 + 自定义排序 |
四、应答框架 & 面试建议
1. 你知道哪些排序？哪种最好？
- 分析场景再选：快排适合通用，归并适合链表，计数适合整数范围小
2. 快排最坏时间复杂度？怎么优化？
- O(n^2)，优化方法：随机化 pivot，三路快排
3. 为什么归并适合链表？
- 链表不能随机访问，归并分治直接分中间节点，合并无需额外数组
4. 如何实现 Top K 问题？
- 小顶堆维护前 K 个元素，堆排序或快速选择法
五、实战建议
- 手写练习：快排（原地）、归并（链表）、堆构建
- 使用库时：记得
sort()默认用 IntroSort（快排+堆+插入） - 注意稳定性、是否原地、空间复杂度等细节
📌 建议每日刷 1-2 道经典题，注重思维过程而非背代码
📌 可搭配可视化工具（如 Visualgo.net）加深理解