044. 编写一个函数，实现快速排序算法

快速排序是一种高效的排序算法，使用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

示例代码

def quick_sort(arr):
    """
    快速排序函数。

    参数:
        arr (list): 输入数组。
    """
    if len(arr) <= 1:
        return arr  # 如果数组长度小于等于1，直接返回数组
    else:
        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(left) + middle + quick_sort(right)  # 递归排序左右子序列并合并

# 测试代码
arr = [3, 6, 8, 10, 1, 2, 1]
print("原始数组：", arr)
sorted_arr = quick_sort(arr)
print("排序后的数组：", sorted_arr)

运行结果

运行上述代码后，输出如下：

原始数组： [3, 6, 8, 10, 1, 2, 1]
排序后的数组： [1, 1, 2, 3, 6, 8, 10]

代码解释

基本情况：

• 如果数组长度小于等于 1，直接返回数组，因为长度为 1 的数组已经是有序的。

选择基准：

• 选择数组中间的元素作为基准（pivot）。也可以选择第一个元素、最后一个元素或随机元素作为基准。

划分数组：

• 使用列表推导式将数组分为三部分：

• left：小于基准的元素。

• middle：等于基准的元素。

• right：大于基准的元素。

递归排序：

• 递归地对 left 和 right 子序列进行快速排序。

• 最后将排序后的 left 子序列、middle 和排序后的 right 子序列合并。

扩展：原地快速排序

上述实现使用了额外的空间来存储 left、middle 和 right 子序列。为了节省空间，可以实现原地快速排序。以下是原地快速排序的实现代码：

def quick_sort_inplace(arr, low, high):
    """
    原地快速排序函数。

    参数:
        arr (list): 输入数组。
        low (int): 当前排序区间的起始索引。
        high (int): 当前排序区间的结束索引。
    """
    if low < high:
        # 找到分区点
        pivot_index = partition(arr, low, high)
        # 递归排序左右子序列
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

def partition(arr, low, high):
    """
    分区函数，将数组分为小于基准和大于基准的两部分。

    参数:
        arr (list): 输入数组。
        low (int): 当前排序区间的起始索引。
        high (int): 当前排序区间的结束索引。

    返回:
        int: 分区点的索引。
    """
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1  # 小于基准的元素的索引

    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

# 测试代码
arr = [3, 6, 8, 10, 1, 2, 1]
print("原始数组：", arr)
quick_sort_inplace(arr, 0, len(arr) - 1)
print("排序后的数组：", arr)

运行结果

运行上述代码后，输出如下：

原始数组： [3, 6, 8, 10, 1, 2, 1]
排序后的数组： [1, 1, 2, 3, 6, 8, 10]

代码解释

quick_sort_inplace 函数：

• 参数 low 和 high 分别表示当前排序区间的起始和结束索引。

• 使用 partition 函数找到分区点，并递归地对左右子序列进行排序。

partition 函数：

• 选择最后一个元素作为基准（pivot）。

• 使用两个指针 i 和 j，i 用于记录小于基准的元素的索引，j 用于遍历数组。

• 如果 arr[j] < pivot，交换 arr[i + 1] 和 arr[j]，并将 i 向前移动。

• 最后，将基准放到中间位置，返回分区点的索引。

注意事项

1. 基准选择：选择不同的基准会影响快速排序的性能。常见的选择方法包括选择第一个元素、最后一个元素、中间元素或随机元素。
2. 性能：快速排序的平均时间复杂度为 O(nlogn)，但在最坏情况下（如数组已经有序）时间复杂度为 O(n2)。通过随机选择基准可以避免最坏情况。
3. 原地排序：原地快速排序不需要额外的空间，空间复杂度为 O(logn)，适用于大规模数据排序。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)