作者 | 鐵猴
責編 | 屠敏
出品 | CSDN 博客
1.簡介
本文對常見排序算法進行總結。
2.排序算法
冒泡排序
該算法比較簡單，幾乎所有語言涉及到算法時，都會涉及到冒泡算法。
算法思路：
-
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
-
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
-
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
選擇排序
每次選擇一個最大(小)的，直到所有元素都被輸出。
可參考：https://blog.csdn.net/sun7545526/article/details/85165618
直接插入排序
插入排序的基本方法是：每一步將一個待排序的元素，按其排序碼的大小，插入到前面已經排好序的一組元素的適當位置上去，直到元素全部插入為止
算法思路：
當插入第i(i >= 1)時，前面的V[0]，V[1]，……，V[i-1]已經排好序。這時，用V[I]的排序碼與V[i-1]，V[i-2]，…的排序碼順序進行比較，找到插入位置即將V[i]插入，原來位置上的元素向后順移。
以[21,25,49,25,16,08]為例，排序過程如下所示：
在小規模數據集或是基本有序時，該算法效率較高。
希爾排序
先對數據進行預處理，使其基本有序，然后再用直接插入排序算法排序。
詳細過程可參考：https://blog.csdn.net/eric_sunah/article/details/103080731
快速排序
利用“分而治之”的思想對集合進行排序
可參考：https://blog.csdn.net/sun7545526/article/details/85165742
堆排序
說堆排序前，先說下啥是堆。
堆：堆是滿足下列性質的完全二叉樹：
-
每個節點都大于或是等于其左右孩子節點的值，稱為大頂堆
-
每個節點都小于或是等于其左右孩子節點的值，稱為小頂堆
接下來說下堆是如何做排序的，思路如下（以大頂堆為例）：
-
根節點是整個堆的最大值，將它移走。
-
將剩余n-1個節點重新構造成一個堆，再將根節點移走
-
重復執行1,2。直到沒有節點可移動，就生成了有序序列。
該算法有兩個需要解決問題：
-
如何將一個無序序列構建一個堆。
-
移除根節點后，如何用剩余的節點重建堆。
詳細介紹參見：https://blog.csdn.net/eric_sunah/article/details/103081878
歸并排序
歸并排序（MERGE-SORT）是利用歸并的思想實現的排序方法，該算法采用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
詳細介紹參見：https://blog.csdn.net/eric_sunah/article/details/103082607
3.總結
分類總結：
時間復雜度總結：
版權聲明：本文為CSDN博主「鐵猴」加入原力計劃的原創文章。
