第11067题 单选
已从小到大排好序的数组,以第一个元素为pivot的快速排序的时间复杂度是多少?

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

O(n)

B

O(nlogn)

C

O(n²)

D

O(logn)

程序运行统计
暂无判题统计