基础练习——快速排序

快排采用分治递归策略，从待排序数组选一个基准值，比如首元素，然后剩下的元素里，比基准值小的放左边，大的放右边。这两部分继续递归进行排序。

首元素做基准

def quick_sort(lst):
    length = len(lst)
    if length <= 1:
        return lst

    key = lst[0]                                                # 选第一个作为基准值
    left = [lst[i] for i in range(1, length) if lst[i] < key]   # 比基准值小的放左边
    right = [lst[i] for i in range(1, length) if lst[i] >= key] # 比基准值大的放右边

    return quick_sort(left) + [key] + quick_sort(right)

末元素做基准

也可以选择末元素做基准值，这样可以pop删掉再循环，代码简洁了些。当然也可以选择中位值作为基准值。

def quick_sort(lst):
    length = len(lst)
    if length <= 1:
        return lst

    key = lst[-1]                        # 选最后一个作为基准值
    lst.pop()
    left = [i for i in lst if i < key]   # 比基准值小的放左边
    right = [i for i in lst if i >= key] # 比基准值大的放右边

    return quick_sort(left) + [key] + quick_sort(right)

优化比较次数

上面的代码一目了然，比较pythonic，但是在划分左右的时候比较次数重复了，比基准值小的没必要再去比较是否比基准值大，可以优化。

    key = lst[0]
    left, right = [], []
    for i in range(1, length):
        if lst[i] < key:
            left.append(lst[i])
        else:
            right.append(lst[i])

原地调整数组

之前的代码都开辟新数组，能否直接原地inplace排序？这是我们见得比较多的快排的一个版本，设置左右指针往中间靠拢。

def quick_sort(lst, left=0, right=None):
    if not left:
        left = 0
    if not right:
        right = len(lst) - 1
    if right - left < 1:
        return

    # 保存分治的边界
    low = left
    high = right

    key = lst[left]                                 # 左值作为基准保存
    while left < right:
        while lst[right] >= key and left < right:   # 从右边开始找第一个比基准值小的，注意，必须先看右边的，因为左值是基准！
            right -= 1
        lst[left] = lst[right]                      # 右值赋值给左值， 首位（左）、右分别为 小、小
        
        while lst[left] <= key and left < right:    # 从左边开始找第一个比基准值大的
            left += 1
        lst[right] = lst[left]                      # 左值赋值给右值，至此，左右互换一次，首位、左、右分别为 小、大、大
    else:
        lst[left] = key                             # 左右相撞，赋值为基准值，首位、左、右分别为 小、基、大 
        quick_sort(lst, low, left - 1)
        quick_sort(lst, left + 1, high)

其实这个代码我觉得有点拗口，可以理解为基准值往中间冒泡。

非递归版本

采用堆栈

def quick_sort(lst):
    if len(lst) <= 1:
        return lst

    stack = []
    stack.append(len(lst) - 1)
    stack.append(0)

    while stack:
        left = stack.pop()
        right = stack.pop()
        low = left
        high = right

        key = lst[left]
        while left < right:
            while lst[right] >= key and left < right:
                right -= 1
            lst[left] = lst[right]
            
            while lst[left] <= key and left < right:
                left += 1
            lst[right] = lst[left]

        else:
            lst[left] = key
            if low < left - 1:
                stack.append(left - 1)
                stack.append(low)
            if high > left + 1:
                stack.append(high)
                stack.append(left + 1)

时间复杂度

如果每次都能二等分，属于最优，那么就是O(nlgn)；最差情况是每次都没分开，那么就是O(n²)。另外，平均时间复杂度也是O(nlgn)，证明比较复杂。