快排优化Python表示「建议收藏」

全栈程序员站长

发布于 2022-07-28 19:22:06

6100

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

基本快速排序分析

以从小到大排序为例 * 选取一个主元（选取方式多样） * 利用主元，将序列分为两个子序列，左侧都比主元小，右侧都比主元大。 * 对两个子序列重复此操作

例如取第一个元素,代码表示如下：

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

优化方案

主元的选取上面的算法有很大的问题，对于升序或降序序列，效率很差，我优化后的方式是主元取序列首中尾三个值取平均数，网上有些取三个值的中值的，我认为没必要，为了效率还要将中值换到首或尾。
序列中可能有一些和主元相等的元素，上面直接将其并入子序列中了，最好是将其和主元聚集在一起，子序列缩减幅度也会更快

这样的话定义一个函数：

def getMidNum(list):
    return (list[0] + list[len(list) - 1] + list[len(list)/2])/3
def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = getMidNum(arr)
        return qsort([x for x in arr[0:] if x < pivot]) + \
               [x for x in arr[0:] if x == pivot] + \
               qsort([x for x in arr[0:] if x > pivot])