最坏情况是每次划分选取的基准都是当前无序区中最小(或最大)的记录。
划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
Cmax = n(n-1)/2=Cmax = n(n-1)/2=O(n2)
版权声明：本文为howlaa原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。