单选题
适中
#24871
有n位同学的成绩已经从小到大排好序,现在对它执行下面这段以第一个元素为pivot 的快速排序,请问此次排序的时间复杂度是()。 def quicksort(a…
有n位同学的成绩已经从小到大排好序,现在对它执行下面这段以第一个元素为pivot 的快速排序,请问此次排序的时间复杂度是()。
def quicksort(a , l , r):
if l >= r:
return
pivot = a [l]
i , j = l , r
while i < j :
while i < j and a [j] >= pivot :
j -= 1
while i < j and a [i] <= pivot :
i += 1
if i < j :
a [i], a [j] = a [j], a [i]
a [l], a [i] = a [i], a [l]
quicksort(a , l , i - 1)
quicksort(a , i + 1 , r)
if __name__ == "__main__":
scores = [60 , 70 , 80 , 90 , 100]
print("排序前:", scores)
quicksort(scores , 0 , len(scores)-1)
print("排序后:", scores) # 输出:[60 , 70 , 80 , 90 , 100]
def quicksort_with_log(a , l , r , depth=0):
if l >= r:
return
print(f "递归深度{depth},处理区间[{l },{r }],数组:{a [l:r+1]}")
pivot = a [l]
i , j = l , r
while i < j :
while i < j and a [j] >= pivot : j -= 1
while i < j and a [i] <= pivot : i += 1
if i < j : a [i], a [j] = a [j], a [i]
a [l], a [i] = a [i], a [l]
quicksort_with_log(a , l , i-1 , depth+1)
quicksort_with_log(a , i+1 , r , depth+1)
scores2 = [60 ,70 ,80 ,90 ,100]
print("\n递归过程:")
quicksort_with_log(scores2 , 0 , 4)
答案与解析
正确答案:C
这道题暂未补解析。