排序算法-快速排序

快速排序

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它采用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

快速排序的步骤：

选择基准值（Pivot）：从数组中选择一个元素作为基准值，通常选择第一个元素、最后一个元素、中间元素或随机元素。

分区操作（Partitioning）：重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面，相同的数可以到任意一边。在这个分区退出之后，该基准就处于数组的中间位置。这个称为分区（partition）操作。

递归排序：递归地（Recursive）把小于基准值的子数组和大于基准值的子数组排序。

快速排序的性能在最坏的情况下是O(n^2)，但平均性能是O(n log n)，这使得它在实际应用中非常高效。它的空间复杂度是O(log n)，这是因为递归调用的栈空间。

python实现快速排序

def quick_sort(arr):
    # 快速排序的辅助函数，用于递归排序
    def _quick_sort(items, low, high):
        if low < high:
            # pi是分区索引，基准值最终的位置
            pi = partition(items, low, high)
            # 分别对基准值左边和右边的子数组进行快速排序
            _quick_sort(items, low, pi - 1)
            _quick_sort(items, pi + 1, high)

    # 执行分区操作的函数
    def partition(items, low, high):
        # 选择基准值，这里选择数组的最后一个元素
        pivot = items[high]
        i = low - 1  # `i`指向比基准小的区域的最后一个元素
        for j in range(low, high):
            # 如果当前元素小于或等于基准值
            if items[j] <= pivot:
                i += 1
                # 交换元素，将`i`和`j`指向的元素交换
                items[i], items[j] = items[j], items[i]
        # 交换基准值到它最终的位置
        items[i + 1], items[high] = items[high], items[i + 1]
        return i + 1

    # 调用辅助函数进行排序
    _quick_sort(arr, 0, len(arr) - 1)

还可以使用列表生成式创建子列表来实现，这种方法代码简单，但创建了额外的列表，占用内存空间，性能较低。

# 列表生成式实现快速排序
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)