各種算法比較
image.png
快速排序的最壞情況發(fā)生的場景：
1）每次選取的基準(zhǔn)元素都是最小元素
2）每次選取的基準(zhǔn)元素都是最大元素
在最壞的情況下，待排序的序列為正序或者逆序，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列，注意另一個(gè)為空。如果遞歸樹畫出來，它就是一棵斜樹。此時(shí)需要執(zhí)行n‐1次遞歸調(diào)用，且第i次劃分需要經(jīng)過n‐i次關(guān)鍵字的比較才能找到第i個(gè)記錄，也就是樞軸的位置，因此比較次數(shù)為
，最終其時(shí)間復(fù)雜度為O(n2)
