快速排序 - 算法优化 - 优化快速排序的性能

快速排序 - 算法优化 - 优化快速排序的性能

一、快速排序基础回顾

快速排序（Quick Sort）是由东尼·霍尔所发展的一种排序算法。它采用了分治法（Divide and Conquer）的策略，基本思想是选择一个基准值（pivot），将数组分为两部分，使得左边部分的所有元素都小于等于基准值，右边部分的所有元素都大于等于基准值，然后分别对左右两部分递归地进行快速排序。

以下是一个简单的 Python 实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    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)
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)

虽然快速排序在平均情况下具有 $O(n log n)$ 的时间复杂度，但在某些极端情况下，比如数组已经有序时，其时间复杂度会退化为 $O(n^2)$。接下来我们将探讨如何优化快速排序的性能。

二、优化策略及实现

1. 随机选择基准值

在原始的快速排序中，我们通常选择数组的第一个元素作为基准值。这种做法在数组已经有序的情况下会导致性能下降。为了避免这种情况，我们可以随机选择一个元素作为基准值。

import random
def quick_sort_random_pivot(arr):
    if len(arr) <= 1:
        return arr
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]
    left = [x for x in arr[:pivot_index] + arr[pivot_index + 1:] if x <= pivot]
    right = [x for x in arr[:pivot_index] + arr[pivot_index + 1:] if x > pivot]
    return quick_sort_random_pivot(left) + [pivot] + quick_sort_random_pivot(right)
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort_random_pivot(arr)
print(sorted_arr)

通过随机选择基准值，我们可以使得快速排序在大多数情况下都能保持 $O(n log n)$ 的时间复杂度。

2. 三数取中法

另一种选择基准值的方法是三数取中法。即选择数组的第一个元素、中间元素和最后一个元素，然后取这三个元素的中位数作为基准值。

def median_of_three(arr, left, right):
    mid = (left + right) // 2
    if arr[left] <= arr[mid] <= arr[right] or arr[right] <= arr[mid] <= arr[left]:
        return mid
    elif arr[mid] <= arr[left] <= arr[right] or arr[right] <= arr[left] <= arr[mid]:
        return left
    else:
        return right
def quick_sort_median_of_three(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left < right:
        pivot_index = median_of_three(arr, left, right)
        arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
        pivot = arr[right]
        i = left - 1
        for j in range(left, right):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[right] = arr[right], arr[i + 1]
        pivot_index = i + 1
        quick_sort_median_of_three(arr, left, pivot_index - 1)
        quick_sort_median_of_three(arr, pivot_index + 1, right)
    return arr
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort_median_of_three(arr)
print(sorted_arr)

三数取中法可以更好地避免选择到最大或最小的元素作为基准值，从而提高算法的性能。

3. 小数组使用插入排序

当数组的长度较小时，快速排序的递归调用开销可能会比较大。此时，我们可以使用插入排序来处理小数组。插入排序在处理小规模数据时具有较好的性能。

def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
def quick_sort_with_insertion(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if right - left < 10:  # 当数组长度小于 10 时使用插入排序
        return insertion_sort(arr, left, right)
    if left < right:
        pivot_index = median_of_three(arr, left, right)
        arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
        pivot = arr[right]
        i = left - 1
        for j in range(left, right):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[right] = arr[right], arr[i + 1]
        pivot_index = i + 1
        quick_sort_with_insertion(arr, left, pivot_index - 1)
        quick_sort_with_insertion(arr, pivot_index + 1, right)
    return arr
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort_with_insertion(arr)
print(sorted_arr)

三、优化效果总结

通过以上优化策略，我们可以显著提高快速排序的性能，使其在各种情况下都能保持较好的表现。在实际应用中，我们可以根据具体的场景选择合适的优化策略。