目前給大家介紹過了6種排序冒泡排序選擇排序 插入排序希爾排序歸并排序快速排序，并且在上期講 快速排續(xù) 時給出了快排的優(yōu)化方案對于大數據集排序先使用 快排 ，當分區(qū)達到一定小的時候使用 插入排序 ，有同學就有疑惑為什么當分區(qū)達到一定小時要用 插入排序 ，這樣真的會變快嗎。

隨機選擇快速排序是一種比較常見的優(yōu)化快速排序的方法，即隨機選取一個元素作為主元，而不是像普通快速排序那樣選取第一個元素作為主元，這種情況下雖然最壞情況仍然是On^2，但最壞情況不再依賴于輸入數據，而是由于隨機函數取值不佳實際上，隨機化快速排序得到理論最壞情況的可能性僅為12^n。

然而，快速排序在最壞情況下的時間復雜度為On^2，這種情況通常發(fā)生在輸入的數組已經有序或者接近有序的情況下為了避免這種情況，可以通過一些優(yōu)化手段來提高算法的效率，例如隨機化分區(qū)函數或者使用三數取中法來選擇分區(qū)點快速排序優(yōu)勢1高效快速快速排序的時間復雜度通常為Onlogn，在大。

快速排序的優(yōu)化主要在于基準數的選取 快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發(fā)生變化，所以快速排序不穩(wěn)定 前面也說了二分查找排序是改進的插入排序，不同之處在于，在有序區(qū)間查找新元素插入位置時，為了減少比較次數提高效率，采用二分查找算法進行插入位置的確定 具體步驟，設。

希爾排序是對插入排序的優(yōu)化希爾排序的思想先使用數組中任間隔為h的元素有序，然后對全局進行排序h該怎么取值呢如果數組長度比較小，則可設置 h=3，h=1若數組長度比較大，可以取 h=4，但最終還是得對全局進行排序h=1但如果數組很長呢則可以設置 h=10，h=4，h=1那如果再來一。