有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)