快速排序
() 在最好情況下假設每次劃分能得到兩個長度相等的子文件文件的長度n=k那麼第一遍劃分得到兩個長度均為ën/û的子文件第二遍劃分得到個長度均為ën/û的子文件以此類推總共進行k=log(n+)遍劃分各子文件的長度均為排序完畢當n=時k=在最好情況下第一遍需比較次第二遍分別對兩個子文件(長度均為k=)進行排序各需次共次即可
() 在最好情況下快速排序的原始序列實例
() 在最壞情況下若每次用來劃分的記錄的關鍵字具有最大值(或最小值)那麼只能得到左(或右)子文件其長度比原長度少因此若原文件中的記錄按關鍵字遞減次序排列而要求排序後按遞增次序排列時快速排序的效率與冒泡排序相同其時間復雜度為O(n)所以當n=時最壞情況下的比較次數為次
() 在最壞情況下快速排序的初始序列實例 要求按遞增排序
該排序方法為快速排序
不是因為當序列已有序時快速排序將退化成冒泡排序時間復雜度為O(n)當待排序序列無序使每次劃分完成後樞軸兩側子文件長度相當此時快速排序性能最好
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23198.html
