利用分区思想改进快速排序算法

# 1. 快速排序算法概述

快速排序是一种高效的排序算法，基于分治思想实现。其核心原理是选择一个基准元素，将数组分为两部分，小于基准的元素放左边，大于的放右边，然后对左右两部分递归地进行排序，最终完成整个数组的排序。时间复杂度主要取决于基准的选择方式和划分操作的实现。

在快速排序中，平均时间复杂度为 O(n log n)，最坏情况下为 O(n^2)，但通过优化基准选择以及分区操作，可以避免最坏情况的发生，提高算法的性能表现。因其简单高效的特点，快速排序广泛应用于各种编程语言和实际的软件开发场景中。

# 2. 常规快速排序算法实现

1. **递归实现**

快速排序算法经典的实现方式之一是通过递归来实现。递归的思想是将一个数组不断划分成两个子数组，直到子数组的大小为1或者0，即递归的结束条件。在每一次划分过程中，选择一个基准值（通常是第一个元素），然后将小于基准值的元素放在基准值的左边，大于基准值的元素放在右边，最后递归地对左右两个子数组进行排序。递归退出后，所有子数组都有序，整个数组也就有序了。

下面是Python中递归实现的快速排序代码：

def quick_sort_recursive(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_recursive(left) + [pivot] + quick_sort_recursive(right)

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort_recursive(arr)
print(sorted_arr)

2. **非递归实现**

除了递归实现外，我们也可以用栈模拟递归的过程，从而避免递归调用带来的额外空间消耗。非递归版本的快速排序使用栈来存储待处理的子数组范围，通过循环实现栈内元素的处理，直到栈为空为止。具体步骤是：将初始待排序的数组范围入栈，循环取出栈顶的数组范围，进行分区操作，然后将分区出的左右子数组的范围入栈，重复这个过程直到栈为空。

以下是使用Python实现的非递归快速排序代码：

def quick_sort_iterative(arr):
    if len(arr) <= 1:
        return arr

    stack = [(0, len(arr) - 1)]
    while stack:
        low, high = stack.pop()
        if low < high:
            pivot_position = partition(arr, low, high)
            stack.append((low, pivot_position - 1))
            stack.append((pivot_position + 1, high))

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_iterative(arr)
print(arr)

def partition(arr, low, high):
    pivot = arr[low]
    left = low + 1
    right = high

    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1
        while arr[right] >= pivot and right >= left:
            right -= 1
        if right < left:
            done = True
        else:
            arr[left], arr[right] = arr[righ