深入理解排序算法

我們先來(lái)說(shuō)一說(shuō)什么是排序、為什么要排序。什么是排序，這個(gè)很簡(jiǎn)單，就是把無(wú)序的東西按照一定的規(guī)則順序排列成升序或者降序。為什么要排序，有兩個(gè)原因，一是為了方便后面的查找，如果沒(méi)有排序的話只能進(jìn)行線性查找，時(shí)間復(fù)雜度是O(n)，如果排序了就可以進(jìn)行二分查找，時(shí)間復(fù)雜度是O(logn)，復(fù)雜度一下子就大大降低了。我們來(lái)說(shuō)明一下這兩種復(fù)雜度的差別有多么懸殊(雖然用詞錯(cuò)誤，但是這么用確實(shí)很符合氣氛)，假設(shè)n是10億的話，O(n)還是10億，而O(logn)是30多(以2為底，假設(shè)系數(shù)是1)，30多和10億比都可以忽略不計(jì)了。二是為了顯示的時(shí)候按照順序顯示，人類的習(xí)慣就是喜歡看有序的東西。