#O(n)时间复杂度时间复杂度内找到一组数据的第 n大元素
import random
import time
def Array(n):
a = []
for i in range(n):
a.append(random.randint(0 , n))
return a
def QuickSort(n):
array = Array(100)
if n > len(array) or n < 1:
print("超出范围,找不到")
return
n = n-1
a = qsort(0 , len(array)-1 , array , n)
print(sorted(array))
print("-----------------------------")
print(a)
def qsort(start , end , array , n):
if start == end:
res = array[start]
if start < end:
key = partation(array , start , end)
print(start , key , end)
if key > n :
res = qsort(start , key-1 , array , n)
elif key < n:
res = qsort(key+1 , end , array , n)
else:
res = array[key]
return res
def swap(array , start , end):
temp = array[start]
array[start] = array[end]
array[end] = temp
def partation(array , start , end):
temp = array[start]
while start < end :
while start<end and array[end]<=temp:
end-=1
swap(array , start , end)
while start<end and array[start]>=temp:
start+=1
swap(array , start , end)
return start
展开