快速排序（输出中间过程）技术博客

快速排序是一种高效的排序算法，它在众多排序场景中表现出色。本文将详细介绍快速排序的原理，并通过输出中间过程来帮助读者更深入地理解其执行步骤。

目录#

  1. 快速排序原理
  2. 实现步骤
  3. 输出中间过程的方法
  4. 示例代码与运行结果
  5. 常见实践与最佳实践
  6. 总结
  7. 参考文献

快速排序原理#

快速排序采用分治法（Divide and Conquer）策略。其基本思想是：

  • 从数组中选择一个基准元素（通常选择第一个元素、最后一个元素或中间元素等）。
  • 通过一趟排序将数组分成两部分，一部分的元素都比基准元素小，另一部分的元素都比基准元素大。
  • 然后对这两部分分别进行快速排序，递归地重复上述过程，直到整个数组有序。

实现步骤#

  1. 选择基准元素：例如，选择数组的第一个元素作为基准。
  2. 划分操作：
    • 定义两个指针，一个从数组的起始位置（除基准元素外）开始，一个从数组的末尾开始。
    • 从右往左移动末尾指针，找到第一个比基准元素小的元素。
    • 从左往右移动起始指针，找到第一个比基准元素大的元素。
    • 如果起始指针小于末尾指针，交换这两个元素。
    • 重复上述步骤，直到起始指针大于等于末尾指针。
    • 最后交换基准元素和起始指针（此时起始指针位置的元素比基准小，基准左边都小，右边都大）。
  3. 递归排序：对基准元素左边和右边的子数组分别进行快速排序。

输出中间过程的方法#

为了输出中间过程，我们可以在每次划分操作后，打印当前数组的状态。例如，在每次递归调用前，先打印当前要排序的子数组。

示例代码与运行结果#

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        print(f"划分后基准位置为 {pi}，当前数组：{arr}")
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
 
 
def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high
    while True:
        while i <= j and arr[i] <= pivot:
            i += 1
        while i <= j and arr[j] >= pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            break
    arr[low], arr[j] = arr[j], arr[low]
    return j
 
 
arr = [12, 4, 5, 6, 7, 3, 1, 15]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("排序后的数组:", arr)

运行结果：

划分后基准位置为 7，当前数组：[1, 4, 5, 6, 7, 3, 12, 15]
划分后基准位置为 0，当前数组：[1, 4, 5, 6, 7, 3, 12, 15]
划分后基准位置为 2，当前数组：[1, 3, 5, 6, 7, 4, 12, 15]
划分后基准位置为 3，当前数组：[1, 3, 4, 6, 7, 5, 12, 15]
划分后基准位置为 5，当前数组：[1, 3, 4, 5, 7, 6, 12, 15]
划分后基准位置为 6，当前数组：[1, 3, 4, 5, 6, 7, 12, 15]
排序后的数组: [1, 3, 4, 5, 6, 7, 12, 15]

常见实践与最佳实践#

  • 基准选择：
    • 随机选择基准：可以避免最坏情况（如数组已经有序时，普通基准选择会导致时间复杂度为 O(n²)，随机选择可降低这种概率）。
    • 三数取中法：取数组的起始、中间、末尾三个元素，选择中间大小的元素作为基准。
  • 优化递归：当子数组长度较小时（例如小于某个阈值，如 10），可以切换到插入排序等简单排序算法，因为此时递归的开销可能大于简单排序的优势。

总结#

快速排序通过分治思想实现高效排序，通过输出中间过程，我们能更直观地看到其排序逻辑。在实际应用中，合理选择基准和优化递归等操作可以进一步提升其性能。

参考文献#

2026-09