排序算法總結
1、冒泡排序
冒泡排序是一種簡單的排序方法，算法如下：
1. 首先將所有待排序的數字放入工作列表中。
2. 從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大于他的下一位，則將它與它的下一位交換。
3. 重復2號步驟(倒數的數字加1。例如：第一次到倒數第二個數字，第二次到倒數第三個數字，依此類推...)，直至再也不能交換。
用C語言實現如下：
int BubbleSort(int *a, int b) //a是待排序的整型數組，b是待排序數組的元素個數
{
int i,j,temp;
for(j=0;j<n-1;j++)
for(i=0;i<n-1-j;i++)
{
if(a[i]>a[i+1])//數組元素大小按升序排列
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
｝
最差時間復雜度 O(n²)
最優時間復雜度 O(n)
平均時間復雜度 O(n²)
最差空間復雜度 O(n) total, O(1) auxiliary
.
2、插入排序
插入排序也是一種簡單排序方法，算法如下：
1. 從第一個元素開始，認為該元素已經是排好序的。
2. 取下一個元素，在已經排好序的元素序列中從后向前掃描。
3. 如果已經排好序的序列中元素大于新元素，則將該元素往右移動一個位置。
4. 重復步驟3，直到已排好序的元素小于或等于新元素。
5. 在當前位置插入新元素。
6. 重復步驟2。
用C實現如下：
int InsertSort(int *a, int b){
int i,j;
int temp;
for(i = 0; i<</SPAN> b; i++){
temp = a[i];
for(j = i-1; j>=0; j--){
if(a[j] > temp)
a[j+1] = a[j]; //將元素往右移動
else{
a[j+1]=temp;
break;
}
}
}
｝
最差時間復雜度 O(n²)
最優時間復雜度 O(n)
平均時間復雜度 O(n²)
最差空間復雜度 O(n) total, O(1) auxiliary
.
3、選擇排序
選擇排序的思想如下：
1. 設數組內存放了n個待排數字，數組下標從1開始，到n結束。
2. i=1
3. 從數組的第i個元素開始到第n個元素，尋找最小的元素。（具體過程為:先設arr[i]為最小，逐一比較，若遇到比之小的則交換）
4. 將上一步找到的最小元素和第i位元素交換。
5. 如果i=n－1算法結束，否則回到第3步
用C語言實現如下：
int SelectSort(int *a, int b){
int i,j;
int flag; //用于記錄哪個元素最小
int temp;
for(i = 0; i<</SPAN> b; i++){
flag = i;
for(j = i+1; j a[j]){
flag = j;
} //選出從i開始最小的元素
}
temp = a[flag];
a[flag] = a[i];
a[i] = temp; //交換元素
}
｝
最差時間復雜度 О(n²)
最優時間復雜度 О(n²)
平均時間復雜度 О(n²)
最差空間復雜度 О(n) total, O(1) auxiliary
以上三種排序的時間復雜度都是O(n²)。
4、快速排序
（a）一趟排序的過程：
（b）排序的全過程
實踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證列表的前半部分都小于后半部分，然后分別對前半部分和后半部分排序，這樣整個列表就有序了。
快速排序的基本算法是：
1. 從數列中挑出一個元素，稱為 "基準"（pivot），
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分割之后，該基準是它的最后位置。這個稱為分割（partition）操作。
3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞回下去，但是這個算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
用C語言實現如下：
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}
int QuickSort(int *a, int b){
int i, j;
int base;
if(b>1){
base = a[0]; //設第一個元素為基準
i = 1; j = b-1;
while(i<</SPAN>j){
if(a[i]<</SPAN>base)
i++;
else
swap(&a[i],&a[j--]);//如果i位置的數大于基準，則往后移
}
if(a[i]<</SPAN>base){ //將基準插入到中間
swap(&a[0], &a[i]);
QuickSort(a, i+1);
QuickSort(&a[i+1], b-i-1);
}
else{
swap(&a[0], &a[i+1]);
QuickSort(a, i);
QuictSort(&a[i],b-i);
}
}
}
快速排序的時間復雜度是O(nlogn)，但是最壞情況下復雜度是O(n²)。
最差時間復雜度 Θ(n²)
最優時間復雜度 Θ(nlogn)
平均時間復雜度 Θ(nlogn) comparisons
最差空間復雜度 根據實現的方式不同而不同
5、希爾排序是不穩定的。
算法思想簡單描述：
在直接插入排序算法中，每次插入一個數，使有序序列只增加1個節點，
并且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為
增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除
多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現
了這一思想。算法先將要排序的一組數按某個增量d分成若干組，每組中
記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量
對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成
一組，排序完成。
下面的函數是一個希爾排序算法的一個實現，初次取序列的一半為增量，
以后每次減半，直到增量為1。
希爾排序是不穩定的。
輸入：數組名稱（也就是數組首地址）、數組中元素個數
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h>0; h=h/2) /*控制增量*/
{
for (j=h; j<n; j++) /*這個實際上就是上面的直接插入排序*/
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}
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)。
功能：滲透建堆
輸入：數組名稱（也就是數組首地址）、參與建堆元素的個數、從第幾個元素開始
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x+s); /*暫存開始元素*/
k = s; /*開始元素下標*/
j = 2*k + 1; /*右子樹元素下標*/
while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/*判斷是否滿足堆的條件：滿足就繼續下一輪比較，否則調整。*/
{
j++;
}
if (t<*(x+j)) /*調整*/
{
*(x+k) = *(x+j);
k = j; /*調整后，開始元素也隨之調整*/
j = 2*k + 1;
}
else /*沒有需要調整了，已經是個堆了，退出循環。*/
{
break;
}
}
*(x+k) = t; /*開始元素放到它正確位置*/
}
功能：堆排序
輸入：數組名稱（也就是數組首地址）、數組中元素個數
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;
for (i=n/2-1; i>=0; i--)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k>=1; k--)
{
t = *(x+0); /*堆頂放到最后*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0); /*剩下的數再建堆*/
}
}
幾種常見排序算法的介紹及復雜度分析
相關概念
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）
冒泡排序方法是最簡單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，并時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。
冒泡排序是穩定的。算法時間復雜度是O(n2)。
2.2選擇排序 （Selection Sort）
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L交換位置。這樣，經過i遍處理之后，前i個記錄的位置已經是正確的了。
選擇排序是不穩定的。算法復雜度是O(n2 )。
2.3插入排序 （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]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
直接插入排序是穩定的。算法時間復雜度是O(n2)
2.4堆排序
堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
堆排序是不穩定的。算法時間復雜度O(nlog n)。
2.5歸并排序
設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸并為一個有序數列，并存儲在A[l..h]。
歸并排序是穩定的。其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。
2.6快速排序
快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然后又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有一個元素為止。
快速排序是不穩定的。最理想情況算法時間復雜度O(nlog2n)，最壞O(n ^2)。
各種排序的穩定性，時間復雜度和空間復雜度總結：
