编辑“︁快速排序中的分治”︁（章节）

== 快速排序中的分治 ==

快速排序（Quicksort）是分治算法（Divide and Conquer）的经典应用之一。它通过递归地将数组划分为较小的子数组，再对子数组进行排序，最终合并结果，达到整体有序的目的。本节将详细介绍快速排序的分治思想、实现步骤、复杂度分析及实际应用。

=== 分治思想简介 ===
分治算法的核心思想是“分而治之”，包含三个步骤：
1. '''分解'''（Divide）：将原问题划分为若干个规模较小的子问题。
2. '''解决'''（Conquer）：递归地解决子问题。若子问题规模足够小，则直接求解。
3. '''合并'''（Combine）：将子问题的解合并为原问题的解。

在快速排序中：
- '''分解'''：选择基准值（pivot），将数组分为两部分，左边小于等于基准值，右边大于基准值。
- '''解决'''：递归排序左右子数组。
- '''合并'''：由于子数组排序后原数组自然有序，无需额外合并操作。

=== 算法步骤 ===
快速排序的具体步骤如下：
1. 从数组中选择一个元素作为基准值（pivot）。
2. 分区（Partition）：重新排列数组，使得所有小于等于基准值的元素位于其左侧，大于基准值的元素位于右侧。
3. 递归地对左右子数组重复上述步骤，直到子数组长度为1或0（已有序）。

=== 代码实现 ===
以下是快速排序的Python实现：

<syntaxhighlight lang="python">
def quicksort(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 quicksort(left) + middle + quicksort(right)

# 示例输入与输出
arr = [3, 6, 8, 10, 1, 2, 1]
print("排序前:", arr)
sorted_arr = quicksort(arr)
print("排序后:", sorted_arr)
</syntaxhighlight>

'''输出结果：'''
<pre>
排序前: [3, 6, 8, 10, 1, 2, 1]
排序后: [1, 1, 2, 3, 6, 8, 10]
</pre>

=== 分区过程详解 ===
快速排序的关键在于分区（Partition）。以下是原地分区的实现（Lomuto分区方案）：

<syntaxhighlight lang="python">
def partition(arr, low, high):
    pivot = arr[high]  # 选择最后一个元素作为基准值
    i = low - 1        # i是小于基准值的区域的右边界
    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 quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pi = partition(arr, low, high)
        quicksort_inplace(arr, low, pi - 1)
        quicksort_inplace(arr, pi + 1, high)

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
quicksort_inplace(arr)
print("原地排序结果:", arr)
</syntaxhighlight>

=== 复杂度分析 ===
* '''时间复杂度'''：
  - 最优情况：每次分区均匀，递归树高度为<math>O(\log n)</math>，每层比较次数为<math>O(n)</math>，总复杂度为<math>O(n \log n)</math>。
  - 最坏情况：每次分区极不均匀（如数组已有序），递归树退化为链表，复杂度为<math>O(n^2)</math>。
  - 平均情况：<math>O(n \log n)</math>。
* '''空间复杂度'''：
  - 递归调用栈空间：最优<math>O(\log n)</math>，最坏<math>O(n)</math>。

=== 实际应用 ===
快速排序因其高效性广泛应用于：
1. 编程语言标准库（如C++的`std::sort`、Python的`list.sort`）。
2. 大数据处理中需要高效排序的场景。
3. 数据库索引构建。

=== 可视化示例 ===
以下是一个分区过程的Mermaid图示：

<mermaid>
graph TD
    A[初始数组: 3, 6, 8, 10, 1, 2, 1] --> B[选择pivot=1]
    B --> C[分区后: 1, 1 | 3, 6, 8, 10, 2]
    C --> D[递归排序左子数组: 1, 1]
    C --> E[递归排序右子数组: 3, 6, 8, 10, 2]
    E --> F[选择pivot=2]
    F --> G[分区后: 2 | 3, 6, 8, 10]
    G --> H[递归排序右子数组: 3, 6, 8, 10]
</mermaid>

=== 优化策略 ===
为避免最坏情况，可采用以下优化：
1. '''随机化基准值'''：随机选择`pivot`降低不均匀分区的概率。
2. '''三数取中法'''：选择首、中、尾元素的中位数作为`pivot`。
3. '''小数组切换插入排序'''：当子数组较小时（如长度≤10），使用插入排序减少递归开销。

=== 总结 ===
快速排序通过分治思想将问题分解为独立子问题，是高效排序算法的代表。理解其分区过程和递归逻辑对掌握分治算法至关重要。实际应用中需注意优化策略以避免性能退化。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:分治算法]]