算法导论第七章

快速排序

• 原址排序
• 期望时间复杂度 $\Theta(n\log n)$，且常数因子很小
• 最好时间复杂度 $\Theta(n\log n)$
• 只要划分是常数比例，快排复杂度始终为 $\Theta(n\log n)$

def QuickSort(lis, p, r):
    if p >= r:
        return lis
    else:
        q = Partion(lis, p, r)
        QuickSort(lis, p, q-1)
        QuickSort(lis, q+1, r)
    return lis

def Partion(lis, p, r):
    x = lis[r]
    i = p-1
    for j in range(p, r):
        if lis[j] <= x:
            i = i+1
            temp = lis[i]
            lis[i] = lis[j]
            lis[j] = temp
    lis[r] = lis[i+1]
    lis[i+1] = x
    return i+1

随机化快排

• 随机选择划分主元

  from random import randint
  
  def RandomQuickSort(lis, p, r):
      if p >= r:
          return lis
      else:
          q = RandomPartion(lis, p, r)
          QuickSort(lis, p, q-1)
          QuickSort(lis, q+1, r)
      return lis
  
  def RandomPartion(lis, p, r):
      index = randint(p,r)
      x = lis[r]
      lis[r] = lis[index]
      lis[index] = x
      return Partion(lis, p, r)

期望时间复杂度证明

• 快排运行时间有Partion上的操作时间决定
• Partion操作至多被执行 $n$ 次
• 分析划分主元与元素比较的总次数

最坏时间复杂度证明

$$ T(n) = \max_{0 \leq q\leq n-1} \lbrace T(q), T(n-1-q)\rbrace + \Theta(n) $$

• 最坏时间复杂度 $\Theta(n^2)$
• 对完全有序数组，快排复杂度为 $\Theta(n^2)$，插入排序复杂度为 $\Theta(n)$

习题

7.1-2, 7.4-1, 7.4-5, 7.4-6