排序算法性能对比及选择指南

2025-2-27

排序算法性能对比及选择指南

1. 引言

在计算机科学领域，排序算法是处理数据的基础且核心的算法之一。不同的算法在不同的数据规模和特性下表现出迥异的性能。本文旨在深入探讨多种经典排序算法的原理、时间复杂度、空间复杂度以及稳定性，并以一种非正式的、类似实验报告的形式，对比它们在不同场景下的性能表现，最终提供一份实用性的排序算法选择指南。

2. 排序算法概述

本节将介绍本文讨论的几种经典排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。

2.1 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的比较排序算法。它重复地遍历要排序的列表，比较每对相邻的元素，如果它们的顺序错误就交换它们。遍历列表的工作重复进行直到没有再需要交换的元素，这意味着列表已经排序完成。

算法步骤：

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.2 选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

算法步骤：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 以此类推，直到所有元素均排序完毕。

2.3 插入排序 (Insertion Sort)

插入排序的工作方式像许多人排序一手扑克牌。开始时，左手为空，桌子上有一堆牌。每次从桌子上拿走一张牌并将它插入到左手中正确的位置。为了找到正确的位置，需要从右到左将它与已在手中的每张牌进行比较。

算法步骤：

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5。

2.4 希尔排序 (Shell Sort)

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了。

算法步骤：

  1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
  2. 按增量序列个数 k，对序列进行 k 趟排序；
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2.5 归并排序 (Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法步骤：

  1. 分解（Divide）： 将n个元素分成个含n/2个元素的子序列。
  2. 解决（Conquer）： 用合并排序法对两个子序列递归的排序。
  3. 合并（Combine）： 合并两个已排序的子序列已得到排序结果。

2.6 快速排序 (Quick Sort)

快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

算法步骤：

  1. 挑选基准值： 从数列中挑出一个元素，称为 "基准"（pivot）。
  2. 分割： 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
  3. 递归排序子序列： 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

2.7 堆排序 (Heap Sort)

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法步骤：

  1. 创建一个堆 H[0……n-1]。
  2. 把堆首（最大值）和堆尾互换。
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置。
  4. 重复步骤 2，直到堆的尺寸为 1。

2.8 计数排序 (Counting Sort)

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤：

  1. 找出待排序的数组中最大和最小的元素。
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。
  4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

2.9 桶排序 (Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，需要做到：在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。

算法步骤：

  1. 设置一个定量的数组当作空桶。
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去。
  3. 对每个不是空的桶进行排序。
  4. 从不是空的桶里把排好序的数据拼接起来。

2.10 基数排序 (Radix Sort)

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法步骤：

  1. 取得数组中的最大数，并取得位数。
  2. arr为原始数组，从最低位开始取每个位组成radix数组。
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）。

3. 算法性能比较

本节将比较上述排序算法的时间复杂度、空间复杂度以及稳定性。

复杂度与稳定性描述:

  • 时间复杂度: 描述了算法执行所需的时间与输入数据规模之间的增长关系。
  • 空间复杂度: 描述了算法执行所需的额外空间与输入数据规模之间的增长关系。
  • 稳定性: 如果两个具有相等键值的元素在排序后保持其原始的相对顺序，则称排序算法是稳定的。

下面是各个算法的特性：

  • 冒泡排序:

    • 平均时间复杂度：O(n^2)
    • 最佳时间复杂度：O(n)
    • 最差时间复杂度：O(n^2)
    • 空间复杂度：O(1)
    • 稳定性：稳定

  • 选择排序:

    • 平均时间复杂度：O(n^2)
    • 最佳时间复杂度：O(n^2)
    • 最差时间复杂度：O(n^2)
    • 空间复杂度：O(1)
    • 稳定性：不稳定

  • 插入排序:

    • 平均时间复杂度：O(n^2)
    • 最佳时间复杂度：O(n)
    • 最差时间复杂度：O(n^2)
    • 空间复杂度：O(1)
    • 稳定性：稳定

  • 希尔排序:

    • 平均时间复杂度：取决于增量序列，通常为 O(n log^2 n) 或 O(n^(3/2))
    • 最佳时间复杂度：取决于增量序列
    • 最差时间复杂度：取决于增量序列
    • 空间复杂度：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^2)
    • 空间复杂度：O(log n) (递归栈的平均深度)
    • 稳定性：不稳定

  • 堆排序:

    • 平均时间复杂度：O(n log n)
    • 最佳时间复杂度：O(n log n)
    • 最差时间复杂度：O(n log n)
    • 空间复杂度：O(1)
    • 稳定性：不稳定

  • 计数排序:

    • 平均时间复杂度：O(n+k)，其中 k 是整数的范围
    • 最佳时间复杂度：O(n+k)
    • 最差时间复杂度：O(n+k)
    • 空间复杂度：O(k)
    • 稳定性：稳定

  • 桶排序:

    • 平均时间复杂度：O(n+k)，其中 k 是桶的数量
    • 最佳时间复杂度：O(n)
    • 最差时间复杂度：O(n^2) (如果所有元素都在一个桶中)
    • 空间复杂度：O(n+k)
    • 稳定性：取决于每个桶内部使用的排序算法

  • 基数排序:

    • 平均时间复杂度：O(nk)，其中 k 是数字的最大位数
    • 最佳时间复杂度：O(nk)
    • 最差时间复杂度：O(nk)
    • 空间复杂度：O(n+k)
    • 稳定性：稳定

4. 算法性能实测

为了更直观地展现不同排序算法的性能差异，本节将通过实际编程测试来比较它们在不同数据规模下的运行时间。

**(注意：以下代码仅为示例，并非严谨的性能测试代码，实际测试需要考虑更多因素，如预热、多次运行取平均值等。) **

采用同一种编程语言python，针对同一组不同大小的随机数序列进行实验。

```python
import time
import random
import sys

由于快速排序递归深度可能超出限制, 因此需要设置限制

sys.setrecursionlimit(10000)

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]

def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

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

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

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = 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

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)

def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2

if l < n and arr[i] < arr[l]:
    largest = l

if r < n and arr[largest] < arr[r]:
    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)

def counting_sort(arr):

max_val = max(arr)
min_val = min(arr)
range_of_elements = max_val - min_val + 1

count_arr = [0 for _ in range(range_of_elements)]
output_arr = [0 for _ in range(len(arr))]

for i in range(0, len(arr)):
    count_arr[arr[i]-min_val] += 1

for i in range(1, len(count_arr)):
    count_arr[i] += count_arr[i-1]

for i in range(len(arr)-1, -1, -1):
    output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
    count_arr[arr[i] - min_val] -= 1

for i in range(0, len(arr)):
    arr[i] = output_arr[i]

def bucket_sort(arr):
# 假设输入数据服从均匀分布
num_buckets = len(arr)
max_val = max(arr)
min_val = min(arr)
# 避免除以零
if max_val == min_val:
return
bucket_range = (max_val - min_val) / num_buckets

buckets = [[] for _ in range(num_buckets)]

for i in range(len(arr)):
    index = int((arr[i] - min_val) / bucket_range)
     # 修正可能超出范围的索引
    index = min(index, num_buckets - 1)
    buckets[index].append(arr[i])

for i in range(num_buckets):
    insertion_sort(buckets[i])  # 对每个桶进行排序, 这里使用插入排序

k = 0
for i in range(num_buckets):
    for j in range(len(buckets[i])):
        arr[k] = buckets[i][j]
        k += 1

def radix_sort(arr):
# 找到最大值以确定位数
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_for_radix(arr, exp)
exp *= 10
def counting_sort_for_radix(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10

# 存储出现的次数
for i in range(0, n):
    index = (arr[i] // exp) % 10
    count[index] += 1

# 更改count[i]，使其现在包含实际
# 在输出数组中的位置
for i in range(1, 10):
    count[i] += count[i - 1]

# 建立输出数组
i = n - 1
while i >= 0:
    index = (arr[i] // exp) % 10
    output[count[index] - 1] = arr[i]
    count[index] -= 1
    i -= 1

# 将输出数组复制到arr[]，以便arr[]现在
# 包含根据当前位数排序的数字
for i in range(0, len(arr)):
    arr[i] = output[i]

测试函数

def test_sorting_algorithm(sort_func, arr):
arr_copy = arr[:] # 创建数组副本，避免修改原数组
start_time = time.time()
sort_func(arr_copy)
end_time = time.time()
return end_time - start_time

生成随机数列表

sizes = [10, 100, 1000, 5000] # 不同规模的数据

针对每种排序算法和每个数据规模进行测试, 将结果记录到 result中

result = {}
for size in sizes:
arr = [random.randint(0, 1000) for _ in range(size)]
print(f"Testing with array size: {size}")
for func in [bubble_sort, selection_sort, insertion_sort, shell_sort, merge_sort,
quick_sort, heap_sort, counting_sort, bucket_sort, radix_sort]:
if func.name not in result:
result[func.name] = {}
time_taken = test_sorting_algorithm(func, arr)
result[func.name][size] = time_taken
print(f"{func.name}: {time_taken:.4f} seconds")
print("-" * 30)

输出测试结果

for size in sizes:
print (f"数据规模:{size}")
for func_name, time_taken in result.items():
print(f"算法名称:{func_name}, 运行时间:{time_taken[size]}")
print('\n')
```

实验结果分析 (基于上述示例代码的可能输出，非实际数据):

通过观察不同算法在不同数据规模下的运行时间，可以得出以下结论：

  • 小规模数据 (n=10, n=100): 简单排序算法（如冒泡、选择、插入）与高级排序算法（如归并、快速）的性能差距不明显。甚至在某些情况下，简单排序算法可能更快，因为它们没有额外的函数调用开销。

  • 中等规模数据 (n=1000): 高级排序算法开始展现出优势，特别是归并排序和快速排序，它们的运行时间远小于简单排序算法。希尔排序的性能介于两者之间。

  • 大规模数据 (n=5000): 高级排序算法的优势非常明显。快速排序和归并排序通常是最快的。而冒泡排序、选择排序和插入排序的运行时间变得非常长，几乎不可用。

  • 计数排序、桶排序和基数排序：在数据满足特定条件（如整数、范围已知）时，这三种线性时间复杂度的排序算法表现出色，运行时间显著低于基于比较的排序算法。

  • 快速排序和堆排序: 快速排序在平均情况下是最快的, 但是最差情况性能可能退化为O(n^2), 堆排序无论在什么情况下都能保证O(nlogn)的复杂度

实验结果可视化（仅为示意，非实际数据）:

```
数据规模 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排序 基数排序

10 0.0001 0.0001 0.0001 0.0001 0.0002 0.0001 0.0002 0.0001 0.0001 0.0001

100 0.001 0.001 0.0005 0.0003 0.0005 0.0003 0.0004 0.0002 0.0002 0.0003

1000 0.1 0.08 0.03 0.005 0.004 0.002 0.003 0.001 0.002 0.003

5000 2.5 2.0 0.8 0.03 0.02 0.01 0.015 0.005 0.01 0.01
```

5. 排序算法选择指南

根据上述的理论分析和实验结果，可以为实际应用场景提供如下排序算法选择建议：

  1. 数据规模很小 (n ≤ 100): 任何排序算法都可以，甚至可能简单排序算法（如插入排序）更优，因为它们实现简单，没有额外的开销。

  2. 数据基本有序: 插入排序是最佳选择。在这种情况下，插入排序的时间复杂度接近 O(n)。

  3. 需要稳定性且空间不敏感: 归并排序是理想的选择，它具有稳定性和 O(n log n) 的时间复杂度，但需要 O(n) 的额外空间。

  4. 数据随机分布且空间有限: 堆排序是一个不错的选择，它具有 O(n log n) 的时间复杂度和 O(1) 的空间复杂度，但不稳定。快速排序在平均情况下有最优的表现, 但是需要注意避免最坏情况。

  5. 数据是整数且范围已知: 计数排序是最佳选择，它具有 O(n+k) 的时间复杂度。

  6. 数据可以均匀分布到桶中: 桶排序可以提供接近 O(n) 的性能。

  7. 需要按多个关键字排序: 基数排序很适用，它可以按照不同的优先级对数据进行排序。

  8. 内存非常有限: 尽量选择空间复杂度为 O(1) 的算法，如冒泡排序、选择排序、插入排序或堆排序。如果可能，可以考虑希尔排序，它在某些情况下可以达到较好的性能。

  9. 如果需要稳定且对空间使用不敏感，则归并排序是个好选择. 如果对稳定性没有要求，快速排序通常是平均性能最好的. 如果可以保证输入数据的某些特征（比如取值范围小，适合基数或桶排序）则优先考虑这几个非比较排序算法。

6. 更进一步的思考

本文探讨了几种经典排序算法的特性和性能。可以意识到，没有一种排序算法在所有情况下都是最优的。选择合适的排序算法需要综合考虑数据规模、数据分布、稳定性需求、空间限制以及编程语言的特性等多个因素。

此外，随着计算机硬件的发展和新算法的出现，排序算法的研究仍在继续。例如，并行排序算法可以利用多核处理器来加速排序过程；外部排序算法可以处理无法全部加载到内存中的超大数据集。

版权声明：
作者：admin
链接：https://hostlocvps.com/2025/02/27/%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95%e6%80%a7%e8%83%bd%e5%af%b9%e6%af%94%e5%8f%8a%e9%80%89%e6%8b%a9%e6%8c%87%e5%8d%97/
文章版权归作者所有，未经允许请勿转载。
THE END
什么是ClashX？全面了解这款工具的功能特点
<<上一篇
为什么选择Manjaro？揭示它成为热门Linux发行版的原因
下一篇>>
相关推荐
深入理解Kotlin Coroutines：基础知识与实际应用
Flask框架的应用场景与开发流程详解
TypeScript Map操作全攻略：语法、特性与最佳实践
安装谷歌浏览器apk的注意事项
专业级C#开发者必备IDE工具
华氏400度转摄氏度：详细换算教程
Caddy介绍：一款高效的HTTP/2服务器详解
Plex Media Server功能特性及使用场景详解
什么是3GPP FTP？全面了解其功能与应用场景
Netflix 免费版功能解析