python 快排以及多种优化

def quick_sort(alist, start, end):
    """快速排序"""

    # 递归的退出条件
    if start >= end:
        return

    # 设定起始元素为要寻找位置的基准元素
    mid = alist[start]

    # low为序列左边的由左向右移动的游标
    low = start

    # high为序列右边的由右向左移动的游标
    high = end

    while low < high:
        # 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
        while low < high and alist[high] >= mid:
            high -= 1
        # 将high指向的元素放到low的位置上
        alist[low] = alist[high]

        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid:
            low += 1
        # 将low指向的元素放到high的位置上
        alist[high] = alist[low]

    # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
    # 将基准元素放到该位置
    alist[low] = mid

    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, low-1)

    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)    

优化1：基准元素不再选择第一个元素，而是随机选择一个，这样避免了有序数组，时间复杂度最坏为log(n2) 的情况

优化2：三路快拍，把和基准元素相等的元素放在中间，比他小的在左边，大的在右边。这样避免了重复元素过多的情况

Snip20171120_17.png

import random


def quicksort(arr, left, right):
    # 只有left < right 排序
    if left >=right:
        return 
    #在列表里随机选一个数来作为基准元素
    random_index = random.randint(left, right)
    #把基准元素和第一个元素交换
    arr[left], arr[random_index] = arr[random_index], arr[left]
    pivot = arr[left]
    #定义lt：小于v部分元素 的下标，初始是空的，因为arr[left]是基准元素
    lt = left # arr[left+1...lt] < v
    #gt 大于v 部分开始的下标，初始为空
    gt = right + 1 # arr[gt...right] > v
    i = left + 1 # arr[lt+1...i] == v
    #终止条件：下标i 和gt 遇到一起，说明都排完了
    while i < gt:
        if arr[i] < pivot:
            arr[i], arr[lt+1] = arr[lt+1], arr[i]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt-1] = arr[gt-1], arr[i]
            gt -= 1
        else:
            i += 1
     #最后把第一个元素（基准元素）放到等于v的部分
    arr[left], arr[lt] = arr[lt], arr[left]
    #递归排序
    quicksort(arr, left, lt-1)
    quicksort(arr, gt, right)