50000+ 数据排序算法效率比较 - 冒泡、快速、插入、归并 - 常规

50000+ 数据排序算法效率比较 - 冒泡、快速、插入、归并

本文将通过生成 50000+ 个随机数，并使用四种排序算法（冒泡、快速、插入、归并）进行排序，分析比较它们的执行时间和效率。此外，文章还会讨论不同数据分布（基本有序、有序、反序）对算法性能的影响，并提出一些优化建议。

1. 生成随机数据

import random

data = [random.randint(0, 100000) for _ in range(50000)]

with open('test.txt', 'w') as file:
    for num in data:
        file.write(str(num) + '\n')

2. 排序算法实现

冒泡排序

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

快速排序

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

插入排序

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

归并排序

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

3. 排序算法性能测试

import time

def read_data(filename):
    with open(filename, 'r') as file:
        data = [int(line.rstrip()) for line in file]
    return data

def write_data(filename, data):
    with open(filename, 'w') as file:
        for num in data:
            file.write(str(num) + '\n')

filename = 'test.txt'

data = read_data(filename)

# 冒泡排序
start_time = time.time()
bubble_sort(data)
end_time = time.time()
write_data('sorted_bubble.txt', data)
print('冒泡排序耗时: ', end_time - start_time)

# 快速排序
data = read_data(filename)
start_time = time.time()
quick_sort(data, 0, len(data) - 1)
end_time = time.time()
write_data('sorted_quick.txt', data)
print('快速排序耗时: ', end_time - start_time)

# 插入排序
data = read_data(filename)
start_time = time.time()
insertion_sort(data)
end_time = time.time()
write_data('sorted_insertion.txt', data)
print('插入排序耗时: ', end_time - start_time)

# 归并排序
data = read_data(filename)
start_time = time.time()
merge_sort(data)
end_time = time.time()
write_data('sorted_merge.txt', data)
print('归并排序耗时: ', end_time - start_time)

4. 算法优劣分析

冒泡排序 时间复杂度为 O(n^2)，在最坏情况下的性能很差，但对于基本有序的数据，冒泡排序的性能较好。
快速排序 时间复杂度为 O(nlogn)，在大多数情况下具有较好的性能，但在最坏情况下的性能为 O(n^2)。
插入排序 时间复杂度为 O(n^2)，在数据基本有序的情况下，插入排序的性能较好。
归并排序 时间复杂度为 O(nlogn)，无论数据的初始顺序如何，归并排序的性能稳定。

5. 不同数据分布下的性能

对于基本有序的数据，冒泡排序、插入排序的性能较好，归并排序、快速排序的性能较差。
对于有序的数据，冒泡排序、插入排序的性能较好，归并排序、快速排序的性能较差。
对于反序的数据，归并排序的性能最好，快速排序的性能较差。

6. 优化建议

在排序前检测数据是否已经有序，如果是，则可以直接跳过排序过程。
对于反序的数据，可以先进行反转，再进行排序。

通过对不同排序算法进行比较和分析，我们可以根据实际情况选择合适的排序算法，以获得最佳的性能。