十大算法排序總結

• 排序算法的總結：

  #基礎排序

  a.冒泡

  誰大誰上，每一輪都把最大的頂到天花闆

  效率太低O(n²)——掌握swap

b.選擇排序，效率較低，但經常用它内部的循環方式來找最大值和最小值——怎麼一次性求出數組的最大值和最小值

O(n²)

c.插排，雖然平均效率低，但是在序列基本有序時，它很快，是以也有其适用範圍

Arrays這個工具類在1.7裡面做了較大改動

d.希爾（縮小增量排序），是插排的改良，對空間思維訓練有幫助

#分治法

1.子問題拆分

2.遞歸求解子問題

3.合并子問題的解

e.快排是軟體工業中最常見的正常排序法，其雙向指針掃描和分區算法是核心，

往往用于解決類似問題，特别地partition算法用來劃分不同性質的元素，

partition->selectK,也用于著名的top問題

O(NlgN)，但是如果主元不是中位數的話，特别地如果每次主元都在數組區間的一側，複雜度将退化為N²

工業優化：三點取中法，絕對中值法，小資料量用插入排序

快排重視子問題拆分

f.歸并排序，空間換時間——逆序對數

歸并重視子問題的解的合并

g.堆排序，用到了二叉堆資料結構，是繼續掌握樹結構的起手式

=插排+二分查找

上面三個都是NlgN的複雜度，其中快排表現最好，是原址的不用開辟輔助空間；堆排也是原址的，但是常數因子較大，不具備優勢。

上面7種都是基于比較的排序，可證明它們在元素随機順序情況下最好是NlgN的，用決策樹證明

下面三個是非比較排序，在特定情況下會比基于比較的排序要快：

1.計數排序，可以說是最快的：O(N+k),k=maxOf(sourceArr)，

用它來解決問題時必須注意如果序列中的值分布非常廣（最大值很大，元素分布很稀疏），

空間将會浪費很多

是以計數排序的适用範圍是：序列的關鍵字比較集中，已知邊界，且邊界較小

2.桶排序：先分桶，再用其他排序方法對桶内元素排序，按桶的編号依次檢出。（配置設定-收集）

用它解決問題必須注意序列的值是否均勻地分布在桶中。

如果不均勻，那麼個别桶中的元素會遠多于其他桶，桶内排序用比較排序，極端情況下，全部元素在一個桶内

還是會退化成NlgN

其時間複雜度是：時間複雜度： O(N+C)，其中C=N*(logN-logM)，約等于N*lgN

N是元素個數，M是桶的個數。

3.基數排序，kN級别（k是最大數的位數）是整數數值型排序裡面又快又穩的，無論元素分布如何，

隻開辟固定的輔助空間（10個桶）

對比桶排序，基數排序每次需要的桶的數量并不多。而且基數排序幾乎不需要任何“比較”操作，而桶排序在桶相對較少的情況下，

桶内多個資料必須進行基于比較操作的排序。

是以，在實際應用中，對十進制整數來說，基數排序更好用。