快速排序详解与实现

太过爱你忘了你带给我的痛 2022-06-04 08:49 199阅读 0赞

选一个序列中的值，所有元素跟这个值做比较，序列被分为两部分，然后对剩下每部分继续做相同操作。快排随机性很大，跟选取的值有关系，每次选值有可能将序列平均分为两份，也有可能做了无用功选取了最大或者最小的那个值,所以时间消耗上随机性很大.

![Center][]

Pythoe 实现 :

def sortList(list) :
        if len(list)>2 :
            #多于两条记录，进行一次快排
            x = list[0]
            i = 0;
            j = len(list)-1
            flag = 'right-left'
            while i<j :
                if flag=='right-left' :
                    if list[j]<x :
                        #互换位置
                        list[i]=list[j]
                        list[j]=x
                        #转变方向
                        flag='left-right'
                        i+=1
                    else : j-=1
                elif flag=='left-right' :
                    if list[i]>x :
                        #互换位置
                        list[j]=list[i]
                        list[i] = x
                        #转变方向
                        flag='right-left'
                        j-=1
                    else : i+=1
            #到此处为止一层快排就结束了
            #要分别对i之前和j之后的部分再进行一次快排
            return sortList(list[0:i])+[x]+sortList(list[j+1:])
        elif len(list)==2 :
            #等于两条记录，比较大小
            if list[0]>list[1] : list.reverse()
            return list
        else :
            return list
    
    originalList=[130,-177,141,-195,-4,98,117,-168,-62,181,167,-190,-100,46,53,39,74,-77,-129,168,92,-139,-106,-188,-50,82,-111,194,83,18]
    resultList = sortList(originalList)
    print(resultList)

写快排的时候一定要注意对选取的比对值的处理，很容易造成死循环。例如我习惯性将队首值做为比对值，现在要做从小到大排序，如果我的序列队首已经是最小值了\[1,3,9,2,6,5,4\],快排后的结果仍然是\[ 1,3,9,2,6,5,4\]，快排后一定要将比对值剔除后再递归，否则将是个死循环。

时间复杂度上来分析,快排最理想的情况下比较次数=2(n-2),最差的情况相当于做了一次冒泡排序(n^2)/2-n/2,复杂度O(nlog2(n))，线性部分n越大每次比对越复杂，对数部分n扩大一倍相当于多递归一次而已。

空间复杂度方面来分析,快排的内存开销很大,为了不破坏原有的元素它必须开辟额外的内存空间保存比对后的结果,复杂度也是O(nlog2(n))，算法又来跟时间复杂度的由来一样.

最有分歧的一个问题来了:快排是不是稳定的?先说结论吧,个人觉得最标准的答案是”快排在牺牲效率的前提下可以稳定”.网上给的答案都是不稳定的,原因有2个.第一:每次排序选取比对值如果是随机选取的话肯定就不稳定了.第二:为了提高大小分组效率往往是首尾向中间对撞比对的,重复数据虽然因为值是相等的都会被分到一边,但是先后顺序得不到保障.如何才能稳定?每次用第一个元素做单向比对就能实现.

![Center 1][]

Pythoe 实现稳定的快速排序 :

def sortList(list) :
        if len(list)>2 :
            #多于两条记录，进行一次快排
            x = list[0]
            leftList=[]
            rightList=[]
            for n in list[1:] :
                if n<x : leftList.append(n)
                else : rightList.append(n)
            return sortList(leftList)+[x]+sortList(rightList)
        elif len(list)==2 :
            #等于两条记录，比较大小
            if list[0]>list[1] : list.reverse()
            return list
        else :
            return list
    
    originalList=[-130,-10,1,28,-39,-88,79,60,10,1,38]
    resultList = sortList(originalList)
    print(resultList)

[Center]: /images/20220604/4835978490dd4c96aafae907fee102aa.png
[Center 1]: /images/20220604/8719714f850a412290495b0eca3ea221.png