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

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

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

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

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