算法导论打卡4，主要内容：快速排序

第七章 快速排序

快速排序的描述

  • KqfUOA.png
  • KqhK1g.png
  • KqhwjJ.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def quicksort(arr,low,high):
    if low<high :
        index=getindex(arr,low,high)
        quicksort(arr,low,index-1)
        quicksort(arr,index+1,high)

def getindex(arr,low,high):
	#PARTITION过程
    temp=arr[low]
    while(low<high):
        while((low<high)and(arr[high]>=temp)):
            high=high-1
        arr[low]=arr[high]
        while((low<high)and(arr[low]<=temp)):
            low=low+1
        arr[high]=arr[low]
    arr[low]=temp
    return low

def main():
    arr=input("please input a group of number:").split()
    n=len(arr)
    for i in range(n):
        arr[i]=int(arr[i])
    quicksort(arr,0,n-1)
    for i in arr:
        print(i,end=" ")

if __name__ =="__main__":
    main()