分治法之快排&随机化

0. 快速排序

由Tony Hoare在1962年发明,这是一个分治算法,它就在原地完成排序,类似与插入排序。
优点:节约内存资源,非常实用,线性复杂度

1. 分治策略

1.1 分

快速排序通过选取一个关键数据,再根据它的大小,把原数组分为两个子数组,第一个数组里面的元数据都比第二个数组里的元素大或者相等。
数组

1.2 治

对两个子数组进行递归排序。

1.3 合

最后得到的数组便是排好序的数组。

快速排序关键的一步就是 ,即递归地划分数组,而归并排序就可以说是递归地合并数组。

2. 分析

伪代码如下所示:

1
/* 划分 */
Partition(A, p, q)  // A[p...q]
x <- A[p]           // 需要作比较的数,哨兵
i <- p
for j <- p+1 to q
    do if A[j] <= x
        then i <- i+1
           exch A[i] <-> A[j]
exch A[p] <-> A[i]
return i

/* 快速排序 */
QuitSort(A, p, q)
if(p<q)
    then r <- Partition(A, p, q)
        QuickSort(A, p, r)
        QuickSort(A, r, q)
        
        
/* 初始调用 */
Init call:
QuickSort(A, 1, n)

2.1 思路

思路
以j为循环变量,从p+1开始遍历,对于每一个元素,都与x进行比较:

  • 若大于等于x,则不管,直接继续
  • 若小于x,i的位置向前移动一位,这时候再将i位置的值与j位置的值进行交换
    循环结束后,将哨兵的值放回到i循环结束后的位置上

2.2 效率分析

  • 最坏情况: 已经排好序或者排成逆序,此时不如插入排序算法
    T(n) = Θ(n^2)
  • 最优情况: 划分正好处在正中央
    T(n) = Θ(n lgn)

    当划分为1:9时,经验证同为最优情况

3. 示例

对 6、10、13、5、8、3、2、11 进行快速排序划分:

  • 第一步,i指向6,j指向10,哨兵赋值为6
    赋值

  • 第二步,j向前移动,寻找比哨兵值6小的元素
    移动

  • 第三步,交换i+1与j值
    交换

  • 重复第二步、第三步
    重复步骤
    重复步骤

  • 最后一步,交换哨兵与i所在位置
    交换哨兵


4. 随机化快排

简单说就是在排序前将数据进行随机化,它具有一下优点:

  • 运行时间不依赖于输入的序列顺序
  • 无需对输入序列的分布做出任何假设
  • 没有一种特定的输入引起最差的情况
  • 最差的情况由随机数生成器产生