深入理解排序算法

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