当前位置：首页 > web >正文

排序算法详解

web 2025/5/16 6:20:25

排序算法全面解析

排序算法是计算机科学中最基础也最重要的算法之一。它将一组数据（例如数字列表、字符串集合）按照特定的顺序（升序或降序）重新排列。高效的排序算法对于优化其他算法（如搜索和合并算法）的效率至关重要。

一、排序算法的基本思想与分类

1. 什么是排序？

排序是将一个记录的任意序列重新排列成一个按键值有序的序列的过程。这里的“键”是记录中用于比较的部分。

2. 为什么需要排序？

快速查找：在有序数据中查找特定元素远快于在无序数据中查找（例如二分查找）。
数据分析：排序后的数据更容易进行统计分析、识别模式或异常值。
算法基础：许多其他算法依赖于输入数据的有序性。
用户友好：向用户展示有序数据通常更直观、更易于理解。

3. 排序算法的分类

排序算法可以根据多个标准进行分类：

比较排序 vs. 非比较排序：
- 比较排序：通过比较元素之间的键值来确定它们的相对顺序（如冒泡排序、快速排序、归并排序）。其时间复杂度下限为 $\log N)$ （基于决策树模型）。
- 非比较排序：不通过比较键值，而是利用元素的特定属性（如数字的大小、范围）进行排序（如计数排序、基数排序、桶排序）。它们可以在特定条件下达到线性时间复杂度 $O (N)$ 。
稳定性：
- 稳定排序：如果两个具有相同键值的元素在排序前后的相对位置保持不变，则该排序算法是稳定的。
- 不稳定排序：可能改变相同键值元素的相对位置。
空间复杂度：
- 原地排序 (In-place)：排序过程中仅需要常数级别的额外空间（ $O (1)$ ），或者最多 $O(\log N)$ 的额外空间（如快速排序的递归栈）。
- 非原地排序 (Out-of-place / Not-in-place)：需要额外的存储空间来辅助排序，通常是 $O (N)$ （如归并排序）。
内部排序 vs. 外部排序：
- 内部排序：所有待排序数据都存储在内存中进行处理。
- 外部排序：数据量过大，无法一次性加载到内存中，需要借助外部存储（如磁盘）进行排序。

本文将重点介绍几种经典的比较排序算法。

二、冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

1. 思想

通过相邻元素之间的比较和交换，使得每一轮遍历都能将当前未排序部分的最大（或最小）元素“冒泡”到数列的末尾（或开头）。

2. 使用方式

主要用于教学目的，理解排序的基本概念。
在数据量非常小（例如 N < 10）的情况下，其简单性可能弥补其效率的不足。
可以用于检测数据是否已经基本有序（通过优化，如果一轮没有发生交换，则说明已排序）。

3. 使用流程

从数列的第一个元素开始，比较它和下一个元素。
如果当前元素大于（或小于，取决于排序顺序）下一个元素，则交换它们。
继续向后移动，对下一对相邻元素进行同样的比较和交换。
重复步骤1-3，直到到达数列的末尾。此时，最大的（或最小的）元素已经被放置在数列的正确位置。
缩小未排序部分的范围（排除已正确放置的元素），重复上述过程。
直到整个数列排序完成（例如，经过 N-1 轮，或者在一轮遍历中没有发生任何交换）。

4. 流程图 (文本表示)


START
|
V
Input array A of size N
|
V
Outer loop: i from 0 to N-2  (Represents passes)
|
V
Set swapped = false
|
V
Inner loop: j from 0 to N-2-i (Compare adjacent elements)
|
V
IF A[j] \> A[j+1] THEN  (For ascending order)
| Yes
V
SWAP(A[j], A[j+1])
|
V
Set swapped = true
|
No --+
|
V
Inner loop continues (next j)
|
V
Inner loop END
|
V
IF swapped == false THEN (Optimization: array is sorted)
| Yes
V
BREAK Outer loop
| No
V
Outer loop continues (next i)
|
V
Outer loop END
|
V
Output sorted array A
|
V
END

5. C/C++ 测试用例

#include <iostream>
#include <vector>
#include <algorithm> // For std::swapvoid printArray(const std::vector<int>& arr, const std::string& msg = "") {if (!msg.empty()) {std::cout << msg;}for (int x : arr) {std::cout << x << " ";}std::cout << std::endl;
}void bubbleSort(std::vector<int>& arr) {int n = arr.size();bool swapped;for (int i = 0; i < n - 1; ++i) {swapped = false;// Last i elements are already in placefor (int j = 0; j < n - 1 - i; ++j) {if (arr[j] > arr[j+1]) {std::swap(arr[j], arr[j+1]);swapped = true;}}// If no two elements were swapped by inner loop, then breakif (!swapped) {break;}// Optional: Print array after each pass// printArray(arr, "After pass " + std::to_string(i + 1) + ": ");}
}int main() {std::vector<int> arr1 = {64, 34, 25, 12, 22, 11, 90};std::cout << "Original array: ";printArray(arr1);bubbleSort(arr1);std::cout << "Sorted array: ";printArray(arr1); // Expected: 11 12 22 25 34 64 90std::vector<int> arr2 = {5, 1, 4, 2, 8};std::cout << "Original array: ";printArray(arr2);bubbleSort(arr2);std::cout << "Sorted array: ";printArray(arr2); // Expected: 1 2 4 5 8std::vector<int> arr3 = {1, 2, 3, 4, 5}; // Already sortedstd::cout << "Original array: ";printArray(arr3);bubbleSort(arr3);std::cout << "Sorted array: ";printArray(arr3); // Expected: 1 2 3 4 5std::vector<int> arr4 = {5, 4, 3, 2, 1}; // Reverse sortedstd::cout << "Original array: ";printArray(arr4);bubbleSort(arr4);std::cout << "Sorted array: ";printArray(arr4); // Expected: 1 2 3 4 5return 0;
}

6. 复杂度与特性

时间复杂度:
- 最坏情况 (Worst Case): $O(N^2)$ (当数组逆序时)
- 平均情况 (Average Case): $O(N^2)$
- 最好情况 (Best Case): $O (N)$ (当数组已经有序，且使用了swapped优化时)
空间复杂度: $O (1)$ (原地排序)
稳定性: 稳定 (相等的元素不会改变相对顺序)

三、归并排序 (Merge Sort)

归并排序是一种高效的、基于分治策略的排序算法。

1. 思想

分治法 (Divide and Conquer)：

分解 (Divide)：将待排序的 $N$ 个元素的序列分解成两个各含 $N /2$ 个元素的子序列。
解决 (Conquer)：递归地排序两个子序列。如果子序列的长度为1，则自然有序，递归结束。
合并 (Combine)：将两个已排序的子序列合并成一个最终的排序序列。

2. 使用方式

需要稳定排序的场景。
对于需要处理大规模数据，尤其是数据无法完全载入内存（外部排序）的情况，归并排序是很好的选择。
其 $\\log N)$ 的时间复杂度在最坏情况下依然保持，因此性能稳定。

3. 使用流程

mergeSort(array A, start, end):

如果 start >= end (基本情况：子数组只有0或1个元素)，则返回，因为已经有序。
计算中间点 mid = start + (end - start) / 2。
递归调用 mergeSort(A, start, mid) 对左半部分进行排序。
递归调用 mergeSort(A, mid + 1, end) 对右半部分进行排序。
调用 merge(A, start, mid, end) 将两个已排序的子数组 A[start...mid] 和 A[mid+1...end] 合并成一个有序数组。

merge(array A, start, mid, end):

创建两个临时数组 L 和 R，分别存储 A[start...mid] 和 A[mid+1...end]。
初始化三个指针：i 指向 L 的开头，j 指向 R 的开头，k 指向 A[start] (合并后数组的起始位置)。
比较 L[i] 和 R[j]：
- 如果 L[i] <= R[j]，则将 L[i] 复制到 A[k]，i 和 k 各自加1。
- 否则 (即 L[i] > R[j])，将 R[j] 复制到 A[k]，j 和 k 各自加1。
重复步骤3，直到 L 或 R 中的一个数组遍历完毕。
将 L 或 R 中剩余的元素（如果有的话）复制到 A 的末尾。

4. 流程图 (文本表示)

mergeSort(A, start, end):

START mergeSort(A, start, end)|V
IF start < end THEN| YesVmid = start + (end - start) / 2|VCALL mergeSort(A, start, mid)  // Sort left half|VCALL mergeSort(A, mid + 1, end) // Sort right half|VCALL merge(A, start, mid, end) // Merge sorted halves|No --+ (Base case: array is of size 0 or 1, already sorted)|V
RETURN

merge(A, start, mid, end):

START merge(A, start, mid, end)|Vn1 = mid - start + 1  // Size of left subarrayn2 = end - mid        // Size of right subarray|VCreate temp arrays L[n1], R[n2]|VCopy A[start...mid] to LCopy A[mid+1...end] to R|Vi = 0 (pointer for L), j = 0 (pointer for R), k = start (pointer for A)|VWHILE i < n1 AND j < n2 DO|VIF L[i] <= R[j] THEN| YesVA[k] = L[i]i = i + 1ELSE| NoVA[k] = R[j]j = j + 1END IF|Vk = k + 1LOOP|VWHILE i < n1 DO // Copy remaining elements of L, if anyA[k] = L[i]i = i + 1k = k + 1LOOP|VWHILE j < n2 DO // Copy remaining elements of R, if anyA[k] = R[j]j = j + 1k = k + 1LOOP|V
RETURN

5. C/C++ 测试用例

#include <iostream>
#include <vector>
#include <algorithm> // For std::vector operations if needed// printArray function from Bubble Sort example can be reused
// void printArray(const std::vector<int>& arr, const std::string& msg = "");// Merges two subarrays of arr[].
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// Create temp arraysstd::vector<int> L(n1), R(n2);// Copy data to temp arrays L[] and R[]for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// Merge the temp arrays back into arr[left..right]int i = 0; // Initial index of first subarrayint j = 0; // Initial index of second subarrayint k = left; // Initial index of merged subarraywhile (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// Copy the remaining elements of L[], if there are anywhile (i < n1) {arr[k] = L[i];i++;k++;}// Copy the remaining elements of R[], if there are anywhile (j < n2) {arr[k] = R[j];j++;k++;}
}// Main function that sorts arr[left..right] using merge()
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {// Same as (left+right)/2, but avoids overflow for large left and rightint mid = left + (right - left) / 2;// Sort first and second halvesmergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}// Helper printArray for this standalone section if needed
void printArrayMerge(const std::vector<int>& arr, const std::string& msg = "") {if (!msg.empty()) {std::cout << msg;}for (int x : arr) {std::cout << x << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr1 = {64, 34, 25, 12, 22, 11, 90};std::cout << "Original array: ";printArrayMerge(arr1);mergeSort(arr1, 0, arr1.size() - 1);std::cout << "Sorted array (Merge Sort): ";printArrayMerge(arr1); // Expected: 11 12 22 25 34 64 90std::vector<int> arr2 = {38, 27, 43, 3, 9, 82, 10};std::cout << "Original array: ";printArrayMerge(arr2);mergeSort(arr2, 0, arr2.size() - 1);std::cout << "Sorted array (Merge Sort): ";printArrayMerge(arr2); // Expected: 3 9 10 27 38 43 82return 0;
}

6. 复杂度与特性

时间复杂度:
- 最坏情况: $\\log N)$
- 平均情况: $\\log N)$
- 最好情况: $\\log N)$ (严格来说，某些实现对已排序数据可以优化到 $O (N)$ ，但经典分治是 $\\log N$ )
空间复杂度: $O (N)$ (需要额外的数组进行合并，非原地排序)
稳定性: 稳定

四、快速排序 (Quick Sort)

快速排序是另一种采用分治策略的高效排序算法。它通常比其他 $\\log N)$ 算法在实践中更快，但这依赖于良好的基准（pivot）选择。

1. 思想

选择基准 (Pick a Pivot)：从数组中选择一个元素作为基准。
分区 (Partition)：重新排列数组，所有小于基准的元素都移动到基准的左边，所有大于基准的元素都移动到基准的右边。相等的元素可以到任何一边。在此过程之后，基准元素处于其最终排序位置。这个操作称为分区操作。
递归 (Recurse)：递归地对基准左边和右边的子数组进行快速排序。

2. 使用方式

当对平均性能有较高要求，且不需要稳定排序时，快速排序是首选。
广泛应用于各种系统级排序任务中。
由于其原地性（或近似原地，仅需 $O(\\log N)$ 栈空间），对于内存限制较严格的场景优于归并排序。

3. 使用流程

quickSort(array A, low, high):

如果 low < high：
a. 调用 partition(A, low, high) 来选择一个基准，并将数组分区。partition 函数返回基准元素的最终索引 pi。
b. 递归调用 quickSort(A, low, pi - 1) 对基准左边的子数组进行排序。
c. 递归调用 quickSort(A, pi + 1, high) 对基准右边的子数组进行排序。

partition(array A, low, high) (Lomuto partition scheme example):

选择 A[high] 作为基准 pivot。
初始化小于基准的元素区域的末尾索引 i = low - 1。
遍历从 low 到 high - 1 的元素 (用 j 表示)：
a. 如果 A[j] <= pivot，则 i 增加1，并交换 A[i] 和 A[j]。
交换 A[i + 1] 和 A[high] (基准元素)。
返回 i + 1 (基准的新索引)。

(注：有多种分区方案，如 Hoare partition scheme，其实现细节和性能略有不同。)

4. 流程图 (文本表示)

quickSort(A, low, high):

START quickSort(A, low, high)|V
IF low < high THEN| YesVpi = CALL partition(A, low, high)  // Get pivot index|VCALL quickSort(A, low, pi - 1)    // Sort left of pivot|VCALL quickSort(A, pi + 1, high)   // Sort right of pivot|No --+ (Base case: subarray has 0 or 1 element)|V
RETURN

partition(A, low, high) (Lomuto scheme):

START partition(A, low, high)|Vpivot = A[high] // Choose the last element as pivoti = low - 1     // Index of smaller element|VFOR j FROM low TO high - 1 DO|VIF A[j] <= pivot THEN| YesVi = i + 1SWAP(A[i], A[j])| NoVLOOP (next j)|VSWAP(A[i + 1], A[high]) // Place pivot in correct position|VRETURN i + 1           // Return pivot's index

5. C/C++ 测试用例

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap// printArray function from Bubble Sort example can be reused
// void printArray(const std::vector<int>& arr, const std::string& msg = "");// This function takes last element as pivot, places
// the pivot element at its correct position in sorted
// array, and places all smaller (smaller than pivot)
// to left of pivot and all greater elements to right of pivot
int partition(std::vector<int>& arr, int low, int high) {int pivot = arr[high]; // Pivotint i = (low - 1);   // Index of smaller elementfor (int j = low; j <= high - 1; j++) {// If current element is smaller than or equal to pivotif (arr[j] <= pivot) {i++; // Increment index of smaller elementstd::swap(arr[i], arr[j]);}}std::swap(arr[i + 1], arr[high]);return (i + 1);
}// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
void quickSort(std::vector<int>& arr, int low, int high) {if (low < high) {// pi is partitioning index, arr[p] is now at right placeint pi = partition(arr, low, high);// Separately sort elements before partition and after partitionquickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// Helper printArray for this standalone section if needed
void printArrayQuick(const std::vector<int>& arr, const std::string& msg = "") {if (!msg.empty()) {std::cout << msg;}for (int x : arr) {std::cout << x << " ";}std::cout << std::endl;
}int main() {std::vector<int> arr1 = {64, 34, 25, 12, 22, 11, 90};std::cout << "Original array: ";printArrayQuick(arr1);quickSort(arr1, 0, arr1.size() - 1);std::cout << "Sorted array (Quick Sort): ";printArrayQuick(arr1); // Expected: 11 12 22 25 34 64 90std::vector<int> arr2 = {10, 7, 8, 9, 1, 5};std::cout << "Original array: ";printArrayQuick(arr2);quickSort(arr2, 0, arr2.size() - 1);std::cout << "Sorted array (Quick Sort): ";printArrayQuick(arr2); // Expected: 1 5 7 8 9 10return 0;
}

6. 复杂度与特性

时间复杂度:
- 最坏情况: $O(N^2)$ (当基准选择最差，例如数组已排序或逆序，且每次都选到最小/最大元素作为基准)
- 平均情况: $\\log N)$
- 最好情况: $\\log N)$ (当基准每次都能均分数组)
空间复杂度: $O(\\log N)$ (递归栈空间，平均情况)。最坏情况下（退化为链表）可能达到 $O (N)$ 。
稳定性: 不稳定 (在分区过程中，相等元素的相对顺序可能改变)

优化：

基准选择：随机选择基准、三数取中法（median-of-three）可以大大降低遇到最坏情况的概率。
小数组优化：当子数组规模小于某个阈值（如10-20个元素）时，改用插入排序，因为插入排序在小数据集上效率更高。
尾递归优化：可以减少递归深度。

五、排序算法比较总结

算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	备注
冒泡排序	$O(N^2)$	$O(N^2)$	$O (N)$	$O (1)$	稳定	简单，教学用，小数据可用
归并排序	$\\log N)$	$\\log N)$	$\\log N)$	$O (N)$	稳定	性能稳定，适用于外部排序
快速排序	$\\log N)$	$O(N^2)$	$\\log N)$	$O(\\log N)$	不稳定	平均性能好，常用
(插入排序)	$O(N^2)$	$O(N^2)$	$O (N)$	$O (1)$	稳定	适用于近乎有序或小数据

六、开源项目中的使用案例

排序算法是基础构件，在众多开源项目中都有应用。

C++ Standard Library (std::sort):
- 使用：GNU libstdc++ 中的 std::sort 通常实现为 Introsort。Introsort 是一种混合排序算法，它以快速排序为主，当递归深度过深（可能导致 $O(N^2)$ 复杂度）时切换到堆排序 (Heapsort)，而对于小规模的子数组（分区大小小于某个阈值，通常16-30）则使用插入排序。这种混合策略结合了快速排序的平均高性能、堆排序的最坏情况 $\\log N)$ 保证以及插入排序在小数组上的高效性。
- std::stable_sort 则通常使用归并排序或其变体，以保证稳定性。
Linux Kernel:
- 使用：内核代码中（例如 lib/sort.c）提供了一个通用的 sort() 函数。这个实现通常是基于堆排序或者归并排序的变体，因为它需要保证最坏情况下的性能，并且有时需要稳定性。例如，旧版本可能使用堆排序，新版本可能会使用一种称为 “bottom-up heapsort” 或类似归并排序的策略。内核对内存和性能的要求非常严格。
Python (list.sort() 和 sorted()):
- 使用：Python 使用 Timsort 算法。Timsort 是一种混合稳定排序算法，派生自归并排序和插入排序，设计用于在多种真实数据上表现良好。它利用了真实世界数据中常见的“有序子序列”（runs）。Timsort 在查找这些 runs 后，使用归并策略来合并它们。
Java (Arrays.sort() 和 Collections.sort()):
- 使用：对于基本类型数组 (int[], double[] 等)，Java 使用双轴快速排序 (Dual-Pivot Quicksort)，这是一种快速排序的变体，通常比传统快速排序性能更好。
- 对于对象数组，如果需要稳定排序，或者元素数量较少时，会使用 Timsort（类似于 Python 的实现，保证 $\\log N)$ 复杂度且稳定）。
数据库系统 (如 PostgreSQL, MySQL):
- 使用：当对查询结果进行 ORDER BY 操作时，如果数据量小且能装入内存，可能会使用快速排序或堆排序等。如果数据量巨大，无法一次性载入内存，数据库会采用外部归并排序 (External Merge Sort)。外部归并排序将数据分块读入内存排序，将排序后的块写回磁盘，然后多路归并这些已排序的块。