python实现快速排序简例

code:

def QuickSort(myList,start,end):
    #判断low是否小于high,如果为false,直接返回
    if start < end:
        i,j = start,end
        #设置基准数
        base = myList[i]

        while i < j:
            #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
            while (i < j) and (myList[j] >= base):          
                j = j - 1
                
            #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
            myList[i] = myList[j]
            # print('后半区',myList)
            
            #同样的方式比较前半区
            while (i < j) and (myList[i] <= base):
                i = i + 1
            myList[j] = myList[i]
            
             # print('前半区',myList)
           
        #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
        myList[i] = base
        #递归前后半区
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList

#输入列表
List = list(map(int, input().split()))
print(List)
QuickSort(List,0,len(List)-1)
print(List)

• 注：基准数为第一个数，则必须从右边开始第一步的排序（仔细考虑，对理解快排非常有益）
• 快速排序（Quicksort）是对冒泡排序的一种改进。
• 下图为各排序方法的时间复杂度

各排序算法的时间复杂度