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