本文共 4026 字，大约阅读时间需要 13 分钟。

十大经典排序算法全解析

排序算法是计算机科学中最基础且应用最广的领域之一，它们通过不同的原理对数据进行重新排列，按照一定的顺序输出，从而完成任务。以下将以易懂的方式介绍十大经典排序算法，包括它们的工作原理、代码实现和时间复杂度等核心内容。

---

1.冒泡排序（Bubble Sort）

定义：

冒泡排序是一种简便的排序算法，其核心思想是通过多次交换相邻元素的位置来逐步使数据有序化。

工作原理：

冒泡排序从左向右检查相邻元素，如果前一个元素比后一个大，则交换位置。重复这一过程，直到没有更多的交换，数据即为排序完成。

优点：实现简单，常用于教学之用。

缺点：对于大规模数据，效率极差，时间复杂度达到O(n²)。

代码实现（伪代码）：

procedure BubbleSort(arr):
    n = 长度(arr)
    for i from 1 到 n-1:
        for j from i+1 到 n:
            如果 arr[j] < arr[i]:
                交换 arr[j] 和 arr[i]
    返回 arr

---

2.选择排序（Selection Sort）

定义：

选择排序通过在每一轮中选出当前最小的元素，将其放置在已排序位置，逐步完成整体排序。

工作原理：

首先将数据分为已排序区和未排序区。每轮从未排序区选出最小的元素放入已排序区，直到所有元素排序完成。

优点：稳定排序，适用于数据规模较小时。

缺点：时间复杂度始终为O(n²)，效率不如其他排序算法。

代码实现（伪代码）：

procedure SelectionSort(arr):
    n = 长度(arr)
    for i from 1 到 n-1:
        min = 最小值(arr[i...n])
        找到 min 的位置 k
        把 arr[k] 和 arr[i] 交换
    返回 arr

---

3.插入排序（Insertion Sort）

定义：

插入排序通过从未排序数据中逐一取出元素，插入到已排序序列的正确位置，使得数据逐步有序化。

工作原理：

从第二个元素开始，依次尝试在已排序序列中的适当位置插入当前元素。完成后，序列即为完全排序。

优点：通常实现为In-place排序，占用额外内存空间最少。

缺点：在最坏情况下，时间复杂度达到O(n²)，与冒泡排序类似。

代码实现（伪代码）：

procedure InsertionSort(arr):
    for i 从第二个元素到倒数第二个:
        取 arr[i]
        j = i - 1
        while j >= 1 且 arr[j] > arr[i]:
            j -= 1
        将 arr[i] 插入到 arr[j+1] 的位置
    返回 arr

---

4.希尔排序（Shell Sort）

定义：

希尔排序是一种优化后的插入排序，通过使用特定的增量来缩小排序范围，显著提高了排序效率。

工作原理：

计划一个增量序列，例如 n/2, n/4, ... 1。

每一趟排序使用当前增量对序列进行划分和排序，依次递减增量，直到完成排序。

优点：时间复杂度为O(n log n)，比冒泡排序和选择排序高效。

缺点：增量序列的选择对性能影响较大，未优化时可能达不到最优效果。

代码实现（伪代码）：

procedure ShellSort(arr, gapSequence):
    for each gap in gapSequence:
        for i 从 gap 到 n-1:
            if arr[i] < arr[i - gap]:
                交换 arr[i] 和 arr[i - gap]
    返回 arr

---

5.归并排序（Merge Sort）

定义：

归并排序是通过分治法将数组分成较小的子数组进行排序，然后再合并这些有序子数组，完成整体排序。

工作原理：

将整个数组分成两半，分别进行归并排序。

合并两个有序子数组，生成最终的有序数组。

优点：时间复杂度稳定为O(n log n)，更高效的选择排序和插入排序。

缺点：需要额外的内存空间用于存储合并过程的数据。

代码实现（伪代码）：

procedure MergeSort(arr):
    if 长度(arr) <= 1:
        返回 arr
    中间 = 长度(arr) // 2
    左子数组 = 排序(arr[1...中间])
    右子数组 = 排序(arr[中间+1...n])
    返回 合并(左子数组, 右子数组)

---

6.快速排序（Quick Sort）

定义：

快速排序通过选定一个基准元素，将数组分成两部分，较小的元素放在基准前面，较大的元素放在基准后面，递归排序两部分。

工作原理：

选定数组中的一个元素作为基准。

将小于基准的元素移到基准前面，其他元素移到基准后面。

递归对前后两部分进行排序，直到所有子数组只含有一个元素。

优点：平均时间复杂度为O(n log n)，是比较效率高的排序算法之一。

缺点：最坏情况下时间复杂度为O(n²)，因为此时数组已排序。

代码实现（伪代码）：

procedure QuickSort(arr):
    如果 长度(arr) <= 1:
        返回 arr
    选择基准 pivot = arr[中间位置]
    把小于 pivot 的元素移到前面，其他元素移到后面
    Catalan排序前面的数组和后面的数组
    返回 合并后的数组

---

7.堆排序（Heap Sort）

定义：

堆排序利用堆数据结构对数组进行排序，即将数组转换为大顶堆或小根堆，逐步分解数据并进行交换。

工作原理：

将数组转换为大顶堆。

把堆顶元素与数组末尾交换，重复直到所有元素排序完成。

优点：时间复杂度为O(n log n)，空间复杂度较低。

缺点：由于堆操作的限制，其实现相对较为复杂。

代码实现（伪代码）：

procedure HeapSort(arr):
    n = 长度(arr)
    构建大顶堆
    while 长度(arr) > 1:
        最小元素 = 堆顶
        交换堆顶与数组末尾
        重排堆结构
    返回 arr

---

8.计数排序（Counting Sort）

定义：

计数排序基于数据的取值范围，对每个值统计其出现次数，然后依次放置到结果数组中。

工作原理：

找到数据的最小值和最大值。

为每个值创建计数器，记录其出现次数。

根据计数器，将数据按顺序放置到结果数组中。

优点：时间复杂度为O(n + k)，k为数据的取值范围。

缺点：需要额外的内存空间存储计数器。

代码实现（伪代码）：

procedure CountingSort(arr):
    最小值 = min(arr)
    最大值 = max(arr)
    C  = �esen tabulation 迹器，大小为最大值 - 最小值 + 1
    初始化所有元素的计数
    for i 从 0 到 最大值-1:
        如果 C[arr[i]] > 0:
            将 arr[i] 放到结果数组中
            C[arr[i]] -= 1
    返回 结果数组

---

9.桶排序（Bucket Sort）

定义：

桶排序通过将元素划分到若干桶中，依次进行排序，最后将桶内的数据合并。

工作原理：

根据数据的分布决定桶的数量和桶的大小。

将元素放入对应的桶中。

逐个桶对内部进行排序，最后合并所有桶的结果。

优点：时间复杂度可能达到O(n + k)，具体效率依赖于桶的划分策略。

缺点：桶的数量增加可能导致内存需求增加。

代码实现（伪代码）：

procedure BucketSort(arr,桶大小):
    创建桶列表
    for 每个元素 x in arr:
        将 x 放入对应桶中
    for 每个桶:
        对桶中的元素进行排序
    将桶中的元素合并到结果数组中
    返回 结果数组

---

10.基数排序（Radix Sort）

定义：

基数排序根据数据的每一位对数据进行排序，先从低位开始，然后是高位。

工作原理：

从低位到高位依次进行排序。

对于每一位，使用计数器记录每个数字的数量。

根据计数器，将数据按顺序放置到结果数组中。

优点：时间复杂度为O(kn)，适用于有固定位数的整数数据。

缺点：对高位较少的数据，效率较低。

代码实现（伪代码）：

procedure RadixSort(arr):
    n = 长度(arr)
    最大位 = 最高位数
    for 每一位 i 从最低位到最高位:
        计数器数组 C 初始化为0
        for j 从 0 到 n-1:
            d = arr[j] 的第i位数字
            C[d] += 1
        for j 从 0 到 n-1:
            d = arr[j] 的第i位数字
            将 arr[j] 放到相应的位置 C[d]-1 的位置
    返回 arr

---

这些排序算法各有特点，用户可以根据具体需求选择最适合的排序方法。从中可以看出，非比较排序（如计数排序、桶排序、基数排序）在数据范围较窄的情况下表现更好，而比较排序（如归并排序、快速排序、堆排序）则适用于大范围的数据。