算法导论打卡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()