十大經典排序算法

前言

先從簡單的入手好了。分别是：

• 冒泡排序；
• 選擇排序；
• 插入排序；
• 希爾排序；
• 歸并排序；
• 快速排序；
• 堆排序；
• 計數排序；
• 桶排序；
• 基數排序。

廢話不多說，讓我們愉快地開始吧~

冒泡排序

基本原理

比較類排序算法。算法描述如下(假設是升序排序)：

• 比較相鄰的元素，如果第一個元素比第二個大，就交換它們；
• 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
• 針對所有的元素重複以上的步驟，除了最後已經選出的有序元素；
• 持續對剩下的無序元素重複上面的步驟，直到排序完成。

算法時間複雜度

選擇排序

• 首先在未排序序列中找到最小元素，存放到排序序列的起始位置；
• 再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序序列的末尾；
• 重複第二步，直到所有元素均排序完畢。

插入排序

• 從第一個元素開始，該元素可以認為已經被排序；
• 取出下一個元素，在已經排序的元素序列中從後向前掃描；
• 如果該元素(已排序)大于新元素，将該元素移到下一位置；
• 重複第三步，直到找到已排序的元素小于或等于新元素的位置；
• 将新元素插入到該位置；
• 重複第二到第五步，直到排序完成。

希爾排序

比較類排序算法。其基本思想是把資料按下标的一定增量分組，對每組使用直接插入排序算法排序，随着增量逐漸減少，每組包含的數越來越多，當增量減至1時，整個檔案恰被分成一組，算法終止。算法描述如下(假設是升序排序)：

• 選擇一個增量序列  ，  ；
• 按增量序列個數k，對序列進行k次排序；
• 每次排序，根據對應的增量  ，将待排序列分割成若幹長度為m的子序列，分别對各子序列進行直接插入排序。

歸并排序

比較類排序算法。該算法采用了分治法的思想，将已有序的子序列合并，得到完全有序的序列。算法描述如下(假設是升序排序)：

• 把長度為n的輸入序列分為兩個長度為  的子序列；
• 對這兩個子序列分别采用歸并排序；
• 将兩個排序好的子序列合并成一個最終的排序序列。

快速排序

比較類排序算法。基本思想是通過一次排序将待排序資料分隔成獨立的兩部分，其中一部分資料均比另一部分的資料小。然後分别對這兩部分資料繼續進行排序，直到整個序列有序。算法描述如下(假設是升序排序)：

• 從數列中挑出一個元素，稱為“基準”；
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺放在基準的後面(相同的數可以到任一邊)；
• 分别對步驟二中的兩個子序列再使用快速排序；
• 重複上述步驟，直到排序完成。

堆排序

• 将初始待排序序列  建構成大頂堆，此堆為初始的無序區；
• 将堆頂元素  和最後一個元素  交換，此時得到新的無序區  和新的有序區  ，且滿足：  ；
• 由于交換後新的堆頂  可能違反堆的性質，是以需要将目前無序區  調整為新堆，然後再次将  與無序區最後一個元素交換，得到新的無序區  和新的有序區  。不斷重複此過程直到有序區的元素個數為  ，則整個排序過程完成。

計數排序

非比較類排序算法。算法描述如下(假設是升序排序)：

• 找出待排序的數組中最大和最小的元素；
• 統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
• 對所有的計數累加(從C中的第一個元素開始，每一項和前一項相加)；
• 反向填充目标數組，将每個元素i放在新數組的第C[i]項，每放一個元素就将C[i]減去1。

桶排序

• 設定一個定量的數組當作空桶集合；
• 周遊輸入資料，并且把資料一個個放到對應的桶裡去(即在每個空桶放一定數值範圍的資料)；
• 對每個非空的桶進行排序；
• 從不是空的桶裡把排好序的資料拼接起來。

基數排序

非比較類排序算法。其實就是先按最低位排序，然後按照高位排序，直到最高位。算法描述如下(假設是升序排序)：

• 取得數組中的最大數，并取得其位數；
• arr為原始數組，從最低位開始取每個位組成的基數數組；
• 對基數進行計數排序(利用計數排序适用于小範圍數的特點)。