Python 实现快速排序

快速排序，排序中最基本的算法，也是用得最多的算法。

python 里的 sorted() 方法，就是使用快速排序来执行的。

原理

在数据中选定一个基准，将小于这个基准的的数据放在左边，大于这个基准的放在右边，然后以这个基准为分界线，递归地实现左边以及右边的数据。

这个基准可以选中位数，也可以选第一个以及最后一个数，不同的数会导致不同的执行效率。

实现

1. 常见的实现代码
   这个代码最好理解，也十分通用

   def quick_sort(alist:list, low: int, high: int):
       # 当 low 高于 high 的时候，出栈
       if low >= high:
           return
   
       partition = get_partition_1(alist, low, high)
       quick_sort(alist, low, partition-1)
       quick_sort(alist, partition+1, high)
   
   
   
   # 以第一个为基准
   def get_partition_1(alist:list, low:int, high: int):
       pivot = alist[low]
       while low < high:
           # 右边找到比基准小于等于的数
           while low < high and alist[high] > pivot:
               high -= 1
           alist[low] = alist[high]
           # 左边找到比基准大的数
           while low < high and alist[low] <= pivot:
               low += 1
           alist[high] = alist[low]
   
       alist[low] = pivot
   
       return low
   
   
   # 以最后一个为基准
   def get_partition_2(alist:list, low:int, high: int):
       pivot = alist[high]
       while low < high:
           # 左边找到比基准大于等于的数
           while low < high and alist[low] < pivot:
               low += 1
           alist[high] = alist[low]
           # 右边找到比基准小的数
           while low < high and alist[high] >= pivot:
               high -= 1
           alist[low] = alist[high]
   
       alist[high] = pivot
   
       return high

还有一个是以中间为基准的代码：

# 以中间为基准
def mid_quick_sort(alist:list, low:int, high:int):
    if low >= high: return
    mid = low + (high - low) // 2
    pivot = alist[mid]

    # 交换中间和尾部
    l = low
    h = high

    while l <= h:
        while alist[h] > pivot:
            h -= 1

        while alist[l] < pivot:
            l += 1
        
        if l <= h:
            alist[h], alist[l] = alist[l], alist[h]
            l += 1
            h -= 1

    mid_quick_sort(alist, low, h)
    mid_quick_sort(alist, l, high)

2. 单循环版

只使用单循环，代码更加简洁。

def quick_sort(alist:list, low: int, high: int):
    # 当 low 高于 high 的时候，出栈
    if low >= high:
        return

    partition = get_partition(alist, low, high)
    quick_sort(alist, low, partition-1)
    quick_sort(alist, partition+1, high)

def get_partition(alist:list, low: int, high: int):
    i = low - 1
    pivot = alist[low]
    for j in range(low, high):
        if alist[j] < pivot:
            i += 1
            alist[j], alist[i] = alist[i], alist[j]
    alist[i] = pivot
    return i

3. python简洁版

使用python的特性，以及分治算法。

def quick_sort(alist: list):
    if len(alist) < 2:
        return alist
    pivot = alist[len(alist) // 2]
    left, right = [], []
    alist.remove(pivot)
    for i in alist:
        if i > pivot: right.append(i)
        else: left.append(i)
    return quick_sort(left) + [pivot] + quick_sort(right)

4. 一行代码实现版
   上面代码的简化版

   quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])

优化一下函数命名：

sort = lambda A: A if len(A) <= 1 else sort([i for i in A[1:] if i <= A[0]]) + [A[0]] + sort([i for i in A[1:] if i > A[0]])