分治算法應用--快速排序

#快速排序

#學過c的就知道了，這里的lst相當于是數組

#分治的一個思想，把lst切割成小段，在小段上進行操作，然后各小段的組合結果即為整個lst的結果

def FastSort(lst,start,end,desc=False):

    right = start

    left = end

    store = lst[right]#這里lst[0]的作用只是中間值存儲

    while right < left:#滿足條件下，以lst[0]為分界線

        while right < left and store < lst[left]:#找到左邊比lst[0]小的第一個數

            left = left - 1#注意下標

        if right < left:

            lst[right] = lst[left]#并賦值給lst[right]

            right = right +1#注意下標

        while right < left and store >= lst[right]:#找到右邊比lst[0]大的第一個數

            right = right + 1#注意下標

        if right < left:

            lst[left] = lst[right]#并賦值給lst[left]

            left = left - 1#注意下標

    lst[right] = store

    print(lst)#測試

    if start < right:#滿足條件下，將lst一分為二，每一段執行上面代碼，遞歸實現

        FastSort(lst,start,left-1)

    if end > left:

        FastSort(lst,left+1,end)

    if desc:

        print(lst[::-1])

    else:

        print(lst)

if __name__ == ' __main__':

    lst = [0,0,0,0,0,23,2,0,1,2,67,2,45,9,4,78,4,5]#前幾次的000000已經是最小的了

    FastSort(lst,0,len(lst)-1,desc=True)

測試結果： 
  
[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 23, 1, 2, 67, 2, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 2, 2, 1, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 67, 23, 45, 9, 4, 78, 4, 5]

[0, 0, 0, 0, 1, 2, 2, 2, 5, 23, 45, 9, 4, 4, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 45, 23, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 45, 23, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 45, 23, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 45, 23, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 45, 23, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 45, 23, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[0, 0, 0, 0, 1, 2, 2, 2, 4, 4, 5, 9, 23, 45, 67, 78]

[78, 67, 45, 23, 9, 5, 4, 4, 2, 2, 2, 1, 0, 0, 0, 0]