排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存

內部排序算法有：直接插入排序，折半插入排序，希爾排序，選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。詳細如何劃分在文章中的敘述會有體現，字母為大類排序方法。

本文將依次介紹上述排序算法。

A、插入排序

一、直接插入排序。

直接插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

算法步驟：

1）將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。

2）從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

代碼實現：

void insert_sort(int array[],unsignedint n)
{int i,j;int temp;for(i = 1;i < n;i++){temp = array[i];for(j = i;j > 0&& array[j - 1] > temp;j--){array[j]= array[j - 1];}array[j] = temp;}
}

適用情況：

直接插入排序適用于順序存儲和鏈式存儲的線性表。當為鏈式存儲時，可以從前往后查照指定元素的位置。注意：大部分排序算法都僅適用于順序存儲的線性表。是一個穩定的排序方法！

二、折半插入排序?

在直接插入排序的基礎上，得出折半插入排序。將直接插入排序的比較和移動分離。

算法步驟：

與直接插入排序類似，在此就不再敘述。

代碼實現：

void binary_insertion_sort(int arr[], int len) 
{int i, j, temp, m, low, high;for (i = 1; i < len; i++){temp = arr[i];low = 0; high = i-1;while (low <= high){m = (low +high) / 2;if(arr[m] > temp)high = m-1;elselow = m+1;}}for (j = i-1; j>=high+1; j--)arr[j+1] = arr[j];arr[j+1] = temp;
}

排序過程：

適用情況：

適用于順序存儲的線性表，是穩定的排序。

三、希爾排序

也稱遞減增量排序方法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定的排序。其基本思想：先將整個待排序的記錄序列分割成若干子序列并分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

算法步驟：

先取一個小于n的步長d1，把表中全部記錄分成d1個組，所有距離為d1的倍數的記錄放在同一個分組中，在各分組中進行直接插入排序；然后取第二個步長d2<d1,重復上述過程，直到所取的dt=1，即所有記錄都放在同一分組里，再進行直接插入排序，由于此時已經具有較好的局部有序性，故很快得到最終結果。到目前為止，尚未求得一個最好的增量序列，希爾提出的方法是d1=n/2；d1+1=di/2（向下取）；并且最后一個增量等于1。

代碼實現：

#include<stdio.h>
#include<math.h>#define MAXNUM 10void main()
{void shellSort(int array[],int n,int t);//t為排序趟數int array[MAXNUM],i;for(i = 0;i < MAXNUM;i++)scanf("%d",&array[i]);shellSort(array,MAXNUM,int(log(MAXNUM + 1) / log(2)));//排序趟數應為log2(n+1)的整數部分for(i = 0;i < MAXNUM;i++)printf("%d ",array[i]);printf("\n");
}//根據當前增量進行插入排序
void shellInsert(int array[],int n,int dk)
{int i,j,temp;for(i = dk;i < n;i++)//分別向每組的有序區域插入{temp = array[i];for(j = i-dk;(j >= i % dk) && array[j] > temp;j -= dk)//比較與記錄后移同時進行array[j + dk] = array[j];if(j != i - dk)array[j + dk] = temp;//插入}
}//計算Hibbard增量
int dkHibbard(int t,int k)
{return int(pow(2,t - k + 1) - 1);
}//希爾排序
void shellSort(int array[],int n,int t)
{void shellInsert(int array[],int n,int dk);int i;for(i = 1;i <= t;i++)shellInsert(array,n,dkHibbard(t,i));
}//此寫法便于理解，實際應用時應將上述三個函數寫成一個函數。

適用情況：

僅適用于當線性表為順序存儲的情況，非穩定排序。

希爾排序舉例：

待排序數組：
{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}

第一次步長h=4,
那么數組按照步長可以拆分成4個小數組（[0]6的意思是下標[0]的值為6）

{[0]6, [4]8, [8]9}
{[1]5, [5]7, [9]0}
{[2]3, [6]2}
{[3]1, [7]4}

對這4個小數組分別進行插入排序后，4個小數組變成：
{[0]6, [4]8, [8]9}
{[1]0, [5]5, [9]7}
{[2]2, [6]3}
{[3]1, [7]4}
合并起來就是：{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}

第二次步長h=1,
那么數組按照步長只有1個數組了
{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}

對這個數組進行一次插入排序后，最終順序就成為：
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

B、交換排序

基于交換排序的排序方法有很多，主要并且常見的是冒泡排序和快速排序。

一、冒泡排序

也是一種簡單直觀的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

算法步驟：

1）比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。

3）針對所有的元素重復以上的步驟，除了最后一個。

4）持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

代碼實現：

void bubble_sort(int a[], int n)
{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^2）,平均時間復雜度O（N^2)。

二、快速排序

是對冒泡排序的一種改進。其基本思想是基于分治法的：在待排序表L[1...n]中任取一個元素pivot作為基準，通過一趟排序將待排序表劃分為獨立的兩部分L[1...K-1]和L[K+1....n]，使得L[1......K-1]中所有元素小于pivot，L[k+1....n]中所有元素大于或等于pivot，則pivot放在了其最終位置L[K]上，這個過程稱作一趟快速排序。而后分別遞歸地對兩個子表重復上述過程，直至每部分內只有一個元素或空為止，即所有元素放在了其最終位置。

算法步驟：

1?從數列中挑出一個元素，稱為?“基準”（pivot），

2?重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

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

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

代碼實現：

void Qsort(int a[], int low, int high)
{if(low >= high){return;}int first = low;int last = high;int key = a[first];/*用字表的第一個記錄作為樞軸*/while(first < last){while(first < last && a[last] >= key){--last;}a[first] = a[last];/*將比第一個小的移到低端*/while(first < last && a[first] <= key){++first;}a[last] = a[first];    
/*將比第一個大的移到高端*/}a[first] = key;/*樞軸記錄到位*/Qsort(a, low, first-1);Qsort(a, first+1, high);
}

考研的數據結構的快排代碼是以嚴版教材為準，看自己總結的黑色筆記本。

適用情況：

快速排序是不穩定的排序，最好的情況下，時間復雜度為：Ο(n?log?n) ，最差時為n^2。快速排序是所有內部排序算法中平均性能最優的排序算法。

C、選擇排序

選擇排序的基本思想是：每一趟（例如第i趟）在后面n-i+1(i=1,2,3...，n-1)個待排序元素中選取關鍵字最小的元素，作為有序子序列的第i個元素，直到第n-1趟做完，待排序元素只剩下一個，就不用再選了。

一、簡單選擇排序

是一種簡單直觀的排序方法

算法步驟：

1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2.再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。

3.重復第2步，直到所有元素均排序完畢。

代碼實現：

void select_sort(int *a,int n)
{register int i,j,min,t;for(i = 0;i < n-1;i++){min = i;//查找最小值for(j = i + 1;j < n;j++)if(a[min] > a[j])min = j;//交換if(min != i){t = a[min];a[min] = a[i];a[i] = t;}}
}

*register是做聲明的，為了提高效率。C語言允許將局部變量的值放在CPU中的寄存器中，這種變量叫寄存器變量。定義這個變量適用于頻繁使用某個變量，以加快運行速度，因為保存在寄存器中，省去了從內存中調用，要注意定義了這個變量后，不能取地址！！就是不能使用&符號

適用情況：

是一種不穩定的排序算法，時間復雜度是O(n^2)。

二、堆排序

是指利用“堆”這種數據結構所設計的一種排序方法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。其平均時間復雜度為Ο(nlogn) 。

算法步驟：

1.創建一個堆H[0...n-1]

2.把堆首（最大值）和堆尾交換。（建立小根堆）

? ?若把堆首（最小值）和堆尾交換則是建立大根堆。

詳細：n個結點的完全二叉樹，最后一個結點是第[n/2](向下取整）個結點的孩子。對第[n/2](向下取整）個結點為根的子樹篩選（對于大根堆：若根結點的關鍵字小于左右子女中關鍵字較大者，則交換），使該子樹成為堆。之后向前依次對各結點（[n/2]-1~1)(n/2向下取整)為根的子樹進行篩選，看該結點值是否大于其左右子結點的值，若不是，將左右子結點中較大值與之交換，交換后可能會破壞下一級的堆，于是繼續采用上述方法構造下一級的堆，直到以該結點為根的子樹構成堆為止。反復利用上述調整堆的方法建堆。

代碼實現：

//array是待調整的堆數組，i是待調整的數組元素的位置，nlength是數組的長度
//本函數功能是：根據數組array構建大根堆
void HeapAdjust(int array[],int i,int nLength)
{int nChild;int nTemp;for(; 2 * i + 1 < nLength;i = nChild){//子結點的位置=2*（父結點位置）+1nChild = 2 * i + 1;//得到子結點中較大的結點if(nChild < nLength - 1 && array[nChild + 1] > array[nChild]) ++nChild;//如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點if(array[i] < array[nChild]){nTemp = array[i];array[i] = array[nChild];array[nChild] = nTemp; }else break; //否則退出循環}
}
//堆排序算法
void HeapSort(int array[],int length)
{int i;//調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素//length/2-1是最后一個非葉節點，此處"/"為整除for(i = length / 2 - 1;i >= 0;--i)HeapAdjust(array,i,length);//從最后一個元素開始對序列進行調整，不斷的縮小調整的范圍直到第一個元素for(i = length - 1;i > 0;--i){//把第一個元素和當前的最后一個元素交換，//保證當前的最后一個位置的元素都是在現在的這個序列之中最大的array[i] = array[0] ^ array[i];array[0] = array[0] ^ array[i];array[i] = array[0] ^ array[i];//不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值HeapAdjust(array,0,i);}
}

適用情況：

是一種不穩定的排序方法，平均時間復雜度O(nlogn)。

*1.插入排序耗時主要在有序表中，選擇排序在無序表中。

?2.看其算法步驟即可得出二者區別。

D、其他排序

一、歸并排序

是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide?and?Conquer）的一個非常典型的應用。

算法步驟：

1.?申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

2.?設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

3.?比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4.?重復步驟3直到某一指針達到序列尾

5.?將另一序列剩下的所有元素直接復制到合并序列尾

代碼實現：

#include <stdlib.h>
#include <stdio.h>void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{int i = startIndex, j=midIndex+1, k = startIndex;while(i != midIndex + 1 && j != endIndex + 1){if(sourceArr[i] >= sourceArr[j])tempArr[k++] = sourceArr[j++];elsetempArr[k++] = sourceArr[i++];}while(i != midIndex+1)tempArr[k++] = sourceArr[i++];while(j != endIndex+1)tempArr[k++] = sourceArr[j++];for(i = startIndex; i <= endIndex; i++)sourceArr[i] = tempArr[i];
}//內部使用遞歸
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{int midIndex;if(startIndex < endIndex){midIndex = (startIndex + endIndex) / 2;MergeSort(sourceArr, tempArr, startIndex, midIndex);MergeSort(sourceArr, tempArr, midIndex+1, endIndex);Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);}
}

適用情況：

是一種穩定的排序方法，時間復雜度未O(nlogn)。

二、基數排序

是一種很特別的排序方法，它不是基于比較進行排序的，而是采用多關鍵字排序思想（即基于關鍵字各位的大小進行排序的），借助“分配”和“收集”兩種操作對單邏輯關鍵字進行排序。基數排序又分為最高位優先（MSD）排序和最低位優先（LSD）排序。

算法步驟：

1.算出要排序的數中的最大位數，設置一個定量的數組當作空桶子（桶的容量即為前面算得的最大位數），桶的序號為0~9，十個位置。

2.對要排列的數據，從個位開始，根據其大小，放入對應的序號的桶中，按照從左往右，從下往上的順序，例如:756個位是6，所以在第一趟中放入序號為6的桶中。收集時也是同樣的順序。（這樣排序的結果為從小到大）

3.一直進行第二步，直到把所有的位數遍歷完，最后一次收集到的數據，即是從小到大排好的順序。

代碼實現：

int maxbit(int data[], int n) //輔助函數，求數據的最大位數
{int d = 1; //保存最大的位數int p = 10;for(int i = 0; i < n; ++i){while(data[i] >= p){p *= 10;++d;}}return d;
}
void radixsort(int data[], int n) //基數排序
{int d = maxbit(data, n);int *tmp = newint[n];int *count = newint[10]; //計數器int i, j, k;int radix = 1;for(i = 1; i <= d; i++) //進行d次排序{for(j = 0; j < 10; j++)count[j] = 0; //每次分配前清空計數器for(j = 0; j < n; j++){k = (data[j] / radix) % 10; //統計每個桶中的記錄數count[k]++;}for(j = 1; j < 10; j++)count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中{k = (data[j] / radix) % 10;tmp[count[k] - 1] = data[j];count[k]--;}for(j = 0; j < n; j++) //將臨時數組的內容復制到data中data[j] = tmp[j];radix = radix * 10;}delete[]tmp;delete[]count;
}

詳細的例題可以查看有關數據結構的參考書。

適用情況：

穩定的排序方法，時間復雜度為O(n)。

*缺點：

1）首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數組的空間開銷，一個存放待排序數組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數組就要至少m個空間。

2）其次待排序的元素都要在一定的范圍內等等。

?總結

各種排序的穩定性，時間復雜度、空間復雜度、穩定性總結如下圖：

不穩定的排序算法有：快、希、選、堆------>“快些選一堆”

注：排序的穩定性是這樣定義的：

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。