先回憶一下我們的一些算法以及他們之間的特點(diǎn)。
| 算法 | 時(shí)間復(fù)雜度 | 原地排序 | 是否穩(wěn)定 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | 是 | 是 |
| 選擇排序 | O(n^2) | 是 | 否 |
| 插入排序 | O(n^2) | 是 | 是 |
| 快速排序 | O(n*logn) | 是 | 否 |
| 歸并排序 | O(n*logn) | 否 | 是 |
| 桶排序 | O(n) | 否 | 是 |
| 計(jì)數(shù)排序 | O(n) | 否 | 是 |
| 基數(shù)排序 | O(n) | 否 | 是 |
線(xiàn)性排序的幾種排序算法桶排序、計(jì)數(shù)排序以及基數(shù)排序都對(duì)數(shù)據(jù)的要求比較高。桶排序跟計(jì)數(shù)排序需要在數(shù)據(jù)的區(qū)間不大，可以講數(shù)據(jù)劃分為不同的桶來(lái)實(shí)現(xiàn)排序?；鶖?shù)排序則要求數(shù)據(jù)可以劃分為高低位，位之間有遞進(jìn)關(guān)系。
剩下的排序算法快速排序跟歸并排序的時(shí)間復(fù)雜度都為O(n*logn)，是我們的首選，而歸并排序的空間復(fù)雜度較高，所以一般我們選擇用快速排序。
當(dāng)然如果數(shù)據(jù)比較小的情況下，我們可以選擇插入排序來(lái)實(shí)現(xiàn)，因?yàn)镺(n^2)在規(guī)模小的數(shù)據(jù)下，排序的時(shí)間會(huì)比O(n*logn)的排序算法還要快。而插入排序不穩(wěn)定，冒泡排序比插入排序的數(shù)據(jù)移動(dòng)的次數(shù)要更多一些。
我們知道快速排序最好的時(shí)間復(fù)雜度是O(n*logn)，最差的時(shí)間復(fù)雜度是O(n^2),就是對(duì)已經(jīng)排好序的數(shù)據(jù)進(jìn)行排序，等于是每次分區(qū)造成數(shù)據(jù)全在一邊。針對(duì)這種情況，我們可以?xún)?yōu)化我們選的基準(zhǔn)數(shù)。
1、可以選幾個(gè)數(shù)，比如三個(gè)，第一個(gè)、中間、最后一個(gè)，取中間值作為基準(zhǔn)數(shù)。
2、也可以用隨機(jī)取，這樣從概率學(xué)的角度，取到最差的結(jié)果的概率會(huì)比較低。
我們參考系統(tǒng)的一些排序算法我們會(huì)發(fā)現(xiàn)，當(dāng)數(shù)據(jù)比較少的時(shí)候選用插入排序，當(dāng)數(shù)據(jù)大于一定的規(guī)模，就采用快速排序，在結(jié)合上面說(shuō)的優(yōu)化選基準(zhǔn)數(shù)的方法，我們就可以實(shí)現(xiàn)一個(gè)高性能的排序算法了。
