快速排序的python实现

介绍

快速排序（QuickSort）是一种高效的排序算法，最早由Tony Hoare于1959年提出。它采用分治策略来排序，具有时间复杂度为O(nlogn)的优异性能，因此在实际应用中广泛使用。

算法思路

快速排序运用了分治（Divide and Conquer）的思想，分为分解、解决子问题和合并三个步骤。

1.分解

选择一个基准元素（pivot），将要排序的数组（subarray）按照基准元素进行划分，使得所有小于基准元素的元素在其左边，所有大于基准元素的元素在右边。

2.解决子问题

递归地对左右两部分子数组进行快速排序，直到子数组的长度为1或0。

3.合并

因为左右两部分子数组都已排好序，将左右两部分子数组及基准元素排列合并，得到最终有序数组。

综上，快速排序的分治方法是，选定一个基准元素，将序列分为小于和大于基准元素的两个子序列，再分别对子序列进行排序，最后再拼接两个序列即可。

def quick_sort(arr,low,high):
    """
    arr:待排序数组
    low:序列最小下标
    high:序簇最大下标
    """
    if low >= high:
        return
    p = partition(arr, low, high) # 找到主元素
    quick_sort(arr, low, p - 1) # 对左右子序列快速排序
    quick_sort(arr, p + 1, high)
    
def partition(arr,low,high):
    pivot = arr[low] # 初始主元素，可以随意选择
    while low < high:
        while low < high and arr[high] >= pivot: # 向前寻找第一个小于主元素的值
            high -= 1
        arr[low] = arr[high]
        while low < high and arr[low] <= pivot: # 向后寻找第一个大于主元素的值
            low += 1
        arr[high] = arr[low]
    arr[low] = pivot # 将主元素放入其最终位置，通过它将数组分为两部分
    return low

下面，我们来对上面所述的算法进行简单说明：

首先，将数组中的第一个元素作为基准元素（pivot）。

需要注意的是，快速排序不是稳定排序，所以有可能使得本来相等的多个元素之间的先后顺序发生改变。

优化思路

1. 三数取中法

在对数组划分时，若总是选择数组中的第一个或最后一个元素作为基准元素，有可能导致最坏情况的出现（即每次划分只能将数组缩短1）。三数取中法是一种优化方法，即在选择pivot之前，随机选择3个数，取其中位数作为pivot，以保证每一次划分都使得数组缩短至少1/4。

def partition(arr,low,high):
    mid = (low + high) // 2 # 选取中间值
    if arr[mid] < arr[low]:
        arr[mid],arr[low] = arr[low],arr[mid] # 保证第一个元素最小
    if arr[mid] > arr[high]:
        arr[mid],arr[high] = arr[high],arr[mid] # 保证最后一个元素最大
    pivot = arr[low]
    while low < high:
        while low < high and arr[high] >= pivot: # 向前寻找第一个小于主元素的值
            high -= 1
        arr[low] = arr[high]
        while low < high and arr[low] <= pivot: # 向后寻找第一个大于主元素的值
            low += 1
        arr[high] = arr[low]
    arr[low] = pivot # 将主元素放入其最终位置，通过它将数组分为两部分
    return low

2. 插入排序

在划分出的子序列长度小于一定值（如10）的时候，可以视为已经有序，不需要再做快速排序，可以切换为插入排序算法，即把子序列插入到有序序列中。

def quick_sort(arr,low,high):
    """
    arr:待排序数组
    low:序列最小下标
    high:序簇最大下标
    """
    if high - low <= 10: # 当序列长度小于等于 10 时直接插入排序
        insert_sort(arr, low, high)
        return
    if low >= high:
        return
    p = partition(arr, low, high) # 找到主元素
    quick_sort(arr, low, p - 1) # 对左右子序列快速排序
    quick_sort(arr, p + 1, high)
def insert_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

总结

快速排序是一种非常高效的排序算法，快速排序通过对问题的划分和逐步缩小，快速得到问题的解。这就是快速排序算法中的分治思想。在这篇文章中，我们介绍了快速排序算法的核心思想、python代码实现和优化，包括三数取中法和插入排序优化。在对于小规模的数组排序时，我们可以采用插入排序以获得更好的性能。快速排序虽然不同于人们常见的排序方法，但其流程简明，代码优雅，没有繁琐的数据结构，依赖性也很小，是一种优秀的排序方法。