上文中提到一個題目，必須使用比較類排序。那麼比較類和非比較類的區别在哪裡呢

比較類排序： 通過比較元素來決定元素間的相對次序，其時間複雜度不能突破O(nlogn)。

非比價類排序： 不通過比較，可以用線性時間運行，如桶排序，計數排序，基數排序

各排序算法的類型

• 冒泡排序

依次比較相鄰元素，讓元素像冒泡一樣向數組頭部移動

算法描述：

1比較相鄰的元素，如果第一個比第二個大，則交換。

2對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數

3重複步驟2，直到某一趟中沒有任何交換，則排序結束

• 選擇排序

依次選出第一大的，第二大的，直到排序完成

算法描述：

1. 遍曆數組，找到最小的元素放到第一位
2. 遍曆數組，找到第二小的放到第二位
3. 重複以上步驟，直到排序完成

• 插入排序

将未确定數組中拿出一個數往已确定數組中插入

算法描述

1. 第一個元素認為是已經配排序
2. 去除下一個元素，往前面掃描，插入合适的位置，目前已确認兩個元素
3. 重複以上步驟直到排序完成

• 希爾排序，又稱縮小增量排序

先将整個待排序列按增量分隔成若幹子序列進行插入排序，然後将增量縮小，再進行一輪排序直到增量為1

• 歸并排序

該算法是采用分治法的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列

算法描述

1. 把長度為n的輸入序列分為兩個長度為n/2的序列
2. 把兩個子序列分别采用歸并排序

• 快速排序

同樣使用了分治法，從數列中挑出一個元素作為基準，将比基準小的擺在基準前面，将比基準大的擺在基準後面，形成兩個子序列。遞歸的把子數列進行快速排序

歸并和快排的區别是，歸并是合并起來，快速排序是逐漸分開

算法描述

1數列中挑出一個元素，稱為基準

2重新排序數列，将元素中比基準小的放在基準前面，将所有元素比基擺在基準後面

3遞歸子數列

• 堆排序

将數組構建成大頂堆，将大頂堆的頂部輸出，重新恢複大頂堆，重複以上知道排序完成

構建大頂堆的時間複雜度為O(n)

• 計數排序

計數排序要求輸入的數據必須是有确定範圍的整數，統計每個數出現的次數後依次輸出數組中，要求數據較為均勻

• 桶排序

利用了函數的映射關系，将數據分到有限的桶内，每個桶内在排序。要求數據較為均勻

• 基數排序

基數排序是按照低位先排序後，再按高位排序，要求數據位數差異不大

十大排序順口溜：快速冒泡，希爾插入，歸并，選擇堆，桶和計數，對比基數

故事解釋：掃地比賽，為了報名快速冒泡，希爾（人名）插入隊伍，歸并地上的垃圾，選擇别人的垃圾堆，放進桶裡進行計數，對比重量基數後獲勝。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!