排序算法總結

1、冒泡排序

冒泡排序是一種簡單的排序方法，算法如下：

1. 首先将所有待排序的數字放入工作清單中。

2. 從清單的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大于他的下一位，則将它與它的下一位交換。

3. 重複2号步驟(倒數的數字加1。例如：第一次到倒數第二個數字，第二次到倒數第三個數字，依此類推...)，直至再也不能交換。

用c語言實作如下：

<code>int</code> <code>bubblesort(</code><code>int</code> <code>*a, </code><code>int</code> <code>n) </code><code>//a是待排序的整型數組，n是待排序數組的元素個數</code>

<code> </code><code>if</code><code>(a[i]>a[i+1]) </code><code>//數組元素大小按升序排列</code>

2、插入排序

插入排序也是一種簡單排序方法，算法如下：

1. 從第一個元素開始，認為該元素已經是排好序的。

2. 取下一個元素，在已經排好序的元素序列中從後向前掃描。

3. 如果已經排好序的序列中元素大于新元素，則将該元素往右移動一個位置。

4. 重複步驟3，直到已排好序的元素小于或等于新元素。

5. 在目前位置插入新元素。

6. 重複步驟2。

用c實作如下：

<code>int</code> <code>insert(</code><code>int</code> <code>*a, </code><code>int</code> <code>n)</code>

3、選擇排序

選擇排序的思想如下：

1. 設數組記憶體放了n個待排數字，數組下标從1開始，到n結束。

2. i=1

3. 從數組的第i個元素開始到第n個元素，尋找最小的元素。（具體過程為:先設arr[i]為最小，逐一比較，若遇到比之小的則交換）

4. 将上一步找到的最小元素和第i位元素交換。

5. 如果i=n－1算法結束，否則回到第3步

4、快速排序

（a）一趟排序的過程：

（b）排序的全過程

實踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證清單的前半部分都小于後半部分，然後分别對前半部分和後半部分排序，這樣整個清單就有序了。

快速排序的基本算法是：

1. 從數列中挑出一個元素，稱為 "基準"（pivot），

2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割之後，該基準是它的最後位置。這個稱為分割（partition）操作。

3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞回下去，但是這個算法總會結束，因為在每次的疊代（iteration）中，它至少會把一個元素擺到它最後的位置去。

<code>void</code><code>　quicksort(</code><code>int</code><code>　a[],</code><code>int</code><code>　numsize) </code><code>/*a是整形數組，numsize是元素個數*/</code>

<code>　</code><code>int</code><code>　i=0, j=numsize-1;</code>

<code>　</code><code>int</code><code>　val=a[0]; </code><code>/*指定參考值val大小*/</code>

<code>　</code><code>if</code><code>(numsize>1) </code><code>/*確定數組長度至少為2，否則無需排序*/</code>

<code>　 </code><code>while</code><code>(i<j) </code><code>/*循環結束條件*/</code>

<code>　</code><code>/*從後向前搜尋比val小的元素，找到後填到a[i]中并跳出循環*/</code>

<code>　 </code><code>break</code><code>;</code>

<code>　</code><code>/*從前往後搜尋比val大的元素，找到後填到a[j]中并跳出循環*/</code>

<code>　 a[i]=val; </code><code>/*将儲存在val中的數放到a[i]中*/</code>

<code>　 quicksort(a,i); </code><code>/*遞歸，對前i個數排序*/</code>

<code>　 quicksort(a+i+1,numsize-i-1); </code><code>/*對i+2到numsize這numsize-1-i個數排序*/</code>

5、希爾排序是不穩定的。

算法思想簡單描述：

在直接插入排序算法中，每次插入一個數，使有序序列隻增加1個節點，

并且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為

增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除

多個元素交換。d.l.shell于1959年在以他名字命名的排序算法中實作

了這一思想。算法先将要排序的一組數按某個增量d分成若幹組，每組中

記錄的下标相差d.對每組中全部元素進行排序，然後再用一個較小的增量

對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成

一組，排序完成。

下面的函數是一個希爾排序算法的一個實作，初次取序列的一半為增量，

以後每次減半，直到增量為1。

希爾排序是不穩定的。

輸入：數組名稱（也就是數組首位址）、數組中元素個數

<code>void</code> <code>shell_sort(</code><code>int</code> <code>*x, </code><code>int</code> <code>n)</code>

<code> </code><code>for</code> <code>(j=h; j<n; j++) </code><code>/*這個實際上就是上面的直接插入排序*/</code>

6、堆排序

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。

堆的定義如下：具有n個元素的序列（h1,h2,...,hn),當且僅當

滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)

時稱之為堆。在這裡隻讨論滿足前者條件的堆。

由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項。完全二叉樹可以

很直覺地表示堆的結構。堆頂為根，其它為左子樹、右子樹。

初始時把要排序的數的序列看作是一棵順序存儲的二叉樹，調整它們的存儲順序，使之成為一個堆，這時堆的根節點的數最大。然後将根節點與堆的最後一個節點交換。然後對前面(n-1)個數重新調整使之成為堆。依此類推，直到隻有兩個節點的堆，并對它們作交換，最後得到有n個節點的有序序列。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最後一個元素交換位置。是以堆排序有兩個函數組成。一是建堆的滲透函數，二是反複調用滲透函數

實作排序的函數。

堆排序是不穩定的。算法時間複雜度o(nlog2n)。

功能：滲透建堆

輸入：數組名稱（也就是數組首位址）、參與建堆元素的個數、從第幾個元素開始

<code> </code><code>t = *(x+s); </code><code>/*暫存開始元素*/</code>

<code> </code><code>k = s; </code><code>/*開始元素下标*/</code>

<code> </code><code>j = 2*k + 1; </code><code>/*右子樹元素下标*/</code>

<code> </code><code>while</code> <code>(j<n)</code>

<code> </code><code>if</code> <code>(j<n-1 && *(x+j) < *(x+j+1))</code><code>/*判斷是否滿足堆的條件：滿足就繼續下一輪比較，否則調整。*/</code>

<code> </code><code>k = j; </code><code>/*調整後，開始元素也随之調整*/</code>

<code> </code><code>else</code> <code>/*沒有需要調整了，已經是個堆了，退出循環。*/</code>

<code> </code><code>break</code><code>;</code>

<code> </code><code>*(x+k) = t; </code><code>/*開始元素放到它正确位置*/</code>

功能：堆排序

<code> </code><code>t = *(x+0); </code><code>/*堆頂放到最後*/</code>

<code> </code><code>sift(x,k,0); </code><code>/*剩下的數再建堆*/</code>

幾種常見排序算法的介紹及複雜度分析

相關概念

1、穩定排序（stable sort）和非穩定排序

穩定排序是指所有相等的數經過某種排序算法操作後仍然能保持它們在排序之前的相對次序。反之就是非穩定排序。

2、内排序（internal sorting）和外排序（external sorting）

在排序過程中，所有需要排序的數都在記憶體，并在記憶體中調整它們的存儲順序，稱為内排序；在排序過程中，隻有部分數被調入記憶體，并借助記憶體調整數在外存中的存放順序排序方法稱為外排序。

排序算法

【冒泡排序】（bubble sort）

冒泡排序方法是最簡單的排序方法。這種方法的基本思想是，将待排序的元素看作是豎着排列的“氣泡”，較小的元素比較輕，進而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若幹遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正确。如果發現兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之後，“最輕”的元素就浮到了最高位置；處理二遍之後，“次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“最輕”元素，是以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正确地排好序。

冒泡排序是穩定的。算法時間複雜度是o(n2)。

【選擇排序】（selection sort）

選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第 i 遍處理是将[i..n]中最小者與位置 i 交換位置。這樣，經過 i 遍處理之後，前 i 個記錄的位置已經是正确的了。

選擇排序是不穩定的。算法複雜度是o(n2 )。

【插入排序】（insertion sort）

插入排序的基本思想是，經過i-1遍處理後,l[1..i-1]己排好序。第i遍處理僅将l插入l[1..i-1]的适當位置，使得l[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較l和l[i-1]，如果l[i-1]≤ l，則l[1..i]已排好序，第i遍處理就結束了；否則交換l與l[i-1]的位置，繼續比較l[i-1]和l[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。

直接插入排序是穩定的。算法時間複雜度是o(n2)

【堆排序】（heap sort）

堆排序是一種樹形選擇排序，在排序過程中，将a[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的内在關系來選擇最小的元素。

堆排序是不穩定的。算法時間複雜度o(nlog2n)。

【歸并排序】（merge sort）

歸并（merge）排序法是将兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若幹個子序列，每個子序列是有序的。然後再把有序子序列合并為整體有序序列。

歸并排序是穩定的。其時間複雜度無論是在最好情況下還是在最壞情況下均是o(nlog2n)。

【快速排序】（quick sort）

快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描隻能確定最大數值的數移到正确位置，而待排序序列的長度可能隻減少1。快速排序通過一趟掃描，就能確定某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右隻有一個元素為止。

快速排序是不穩定的。最理想情況算法時間複雜度o(nlog2n)，最壞o(n ^2)。

各排序方法對比

冒泡排序算法時間複雜度是o(n^2)

選擇排序算法時間複雜度是o(n^2)

插入排序算法時間複雜度是o(n^2)

快速排序是不穩定的。最理想情況算法時間複雜度o(nlog2n)，最壞o(n^2)。

堆排序算法時間複雜度是o(nlogn)

歸并排序算法時間複雜度是o(nlogn)

1.基本概念

1.1穩定排序(stable sort)和非穩定排序

穩定排序是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，。反之，就是非穩定的排序。

比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序後為a1,a2,a4,a3,a5，

則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序後它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。

1.2内排序( internal sorting )和外排序( external sorting)

1.3算法的時間複雜度和空間複雜度

所謂算法的時間複雜度，是指執行算法所需要的計算工作量。一個算法的空間複雜度，一般是指執行這個算法所需要的記憶體空間。

2.幾種常見算法

2.1冒泡排序（bubble sort）

2.2選擇排序（selection sort）

選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是将l[i..n]中最小者與l交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正确的了。

2.3插入排序（insertion sort）

2.4堆排序

堆排序是不穩定的。算法時間複雜度o(nlog n)。

2.5歸并排序

設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為a[l..m]，a[m+1..h]，将它們歸并為一個有序數列，并存儲在a[l..h]。

2.6快速排序

排序算法總結

繼續閱讀

極大似然法(ML)與最大期望法(EM)

[HTML5]自定義屬性 data-* 和 jQuery.data 詳解

2021-2025年中國運動療法（KT）帶行業市場供需與戰略研究報告

shell排序基本思想及其複雜度分析

C++ 第十五周報告1--《冒泡法排序》

2021年危險化學品經營機關安全管理人員考試題庫及危險化學品經營機關安全管理人員考試技巧

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

無人機--飛控科普

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希