快速排序算法：用Python编写的10个函数

快速排序（Quick Sort）是一种常用的高效排序算法。它的核心思想是分治法，通过将数组分成两部分，一部分比基准值小，一部分比基准值大，再对两部分分别进行排序，最终达到整个数组有序的目的。下面将介绍用Python编写的10个快速排序算法的函数。

1. 递归版快排

递归版的快排是快排算法的经典实现方式，其函数签名如下：

def quick_sort_recursive(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 quick_sort_recursive(left) + middle + quick_sort_recursive(right)

2. 非递归版快排

非递归版的快排与递归版的实现方式略有不同，其函数签名如下：

def quick_sort_iterative(arr):
    if len(arr) <= 1:
        return arr
    stack = [(0, len(arr) - 1)]
    while stack:
        start, end = stack.pop()
        if start >= end:
            continue
        pivot = arr[(start + end) // 2]
        left, right = start, end
        while left <= right:
            while arr[left] < pivot:
                left += 1
            while arr[right] > pivot:
                right -= 1
            if left <= right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1
        stack.append((start, right))
        stack.append((left, end))
    return arr

3. 随机化快排

在数据量较大的情况下，递归版快排的性能可能会受到影响。为了解决这个问题，我们可以使用随机化的快排算法。其函数签名如下：

import random

def quick_sort_randomized(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    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 quick_sort_randomized(left) + middle + quick_sort_randomized(right)

4. 单向扫描快排

单向扫描快排（单边循环快排）是一种快速排序算法的变种，其函数签名如下：

def quick_sort_single(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition_single(arr, low, high)
        quick_sort_single(arr, low, pivot_index)
        quick_sort_single(arr, pivot_index + 1, high)
    return arr

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

5. 双向扫描快排

双向扫描快排（双边循环快排）是单向扫描快排的进一步变种，其函数签名如下：

def quick_sort_dual(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition_dual(arr, low, high)
        quick_sort_dual(arr, low, pivot_index - 1)
        quick_sort_dual(arr, pivot_index + 1, high)
    return arr

def partition_dual(arr, low, high):
    pivot = arr[low]
    left, right = low + 1, high
    while True:
        while left <= right and arr[left] < pivot:
            left += 1
        while left <= right and arr[right] > pivot:
            right -= 1
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
        else:
            break
    arr[low], arr[right] = arr[right], arr[low]
    return right

6. 原地快排

原地快排是一种不需要额外空间的快速排序算法，其函数签名如下：

def quick_sort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition_inplace(arr, low, high)
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)
    return arr

def partition_inplace(arr, low, high):
    pivot = arr[low]
    i, j = low, high
    while i < j:
        while i < j and arr[j] > pivot:
            j -= 1
        while i < j and arr[i] <= pivot:
            i += 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[low], arr[j] = arr[j], arr[low]
    return j

7. 三向切分快排

三向切分快排是一种针对重复元素较多的情况的优化快排算法，其函数签名如下：

def quick_sort_3way(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        lt, gt, i = partition_3way(arr, low, high)
        quick_sort_3way(arr, low, lt - 1)
        quick_sort_3way(arr, gt + 1, high)
    return arr

def partition_3way(arr, low, high):
    pivot = arr[low]
    lt, gt, i = low, high, low + 1
    while i <= gt:
        if arr[i] < pivot:
            arr[i], arr[lt] = arr[lt], arr[i]
            i += 1
            lt += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    return lt, gt

8. 基数排序快排

基数排序快排结合了基数排序和快速排序的优点，其函数签名如下：

def quick_sort_radix(arr, radix=10):
    if len(arr) <= 1:
        return arr
    # 计算最大值和位数
    max_val, digits = max(arr), 1
    while max_val >= radix ** digits:
        digits += 1
    # 基数排序
    for i in range(digits):
        buckets = [[] for _ in range(radix)]
        for val in arr:
            digit = (val // (radix ** i)) % radix
            buckets[digit].append(val)
        arr = [val for bucket in buckets for val in bucket]
    # 递归调用快排
    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 quick_sort_radix(left) + middle + quick_sort_radix(right)

9. Lomuto快排

Lomuto快排是一种普遍认为不如Hoare快排的变体，但其实现简单易懂，其函数签名如下：

`

def quick_sort_lomuto(arr, low=0, high=None):

if high is None:

high = len(arr) - 1

if low < high:

pivot_index = partition_lomuto(arr, low, high)

quick_sort_lomuto(arr, low, pivot_index - 1)

quick_sort_lomuto(arr, pivot_index + 1, high)

return arr

def