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

#快速排序

#学过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]