目錄：
一、排序算法的性質
二、十大排序算法介紹及代碼實作(C++版)
一、排序算法的性質
1.穩定性
如果在待排序的序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的;否則稱為不穩定的。
2.時間複雜度
1）時間頻度
一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運作測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，隻需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。算法的時間複雜度是指執行算法所需要的計算工作量。
（2）時間複雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間複雜度概念。
一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),存在一個正常數c使得fn*c>=T(n)恒成立。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。
在各種不同算法中，若算法中語句執行次數為一個常數，則時間複雜度為O(1),另外，在時間頻度不相同時，時間複雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間複雜度相同，都為O(n^2)。
按數量級遞增排列，常見的時間複雜度有：
常數階O(1),對數階O(log2n)(以2為底n的對數，下同),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k),指數階O(2^n)。随着問題規模n的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低。
3.空間複雜度
與時間複雜度類似，空間複雜度是指算法在計算機内執行時所需存儲空間的度量。記作:
S(n)=O(f(n))
算法執行期間所需要的存儲空間包括3個部分：
（1）算法程式所占的空間；
（2）輸入的初始資料所占的存儲空間；
（3）算法執行過程中所需要的額外空間。
4.排序算法性質比較
二、十大排序算法介紹
1.冒泡排序法
冒泡排序（Bubble Sort）是一種較簡單的排序算法，重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）不同就把他們交換過來。走訪元素的工作是重複地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同水中的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
冒泡排序的原理如下：
a. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
b. 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
c. 針對所有的元素重複以上的步驟，除了最後一個。
d. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
流程圖：
冒泡排序C++代碼：
#include<iostream>
#include<Windows.h>
using namespace std;
//冒泡過程
template< class T>
void bubble(T A[], int n)
{//将最大元素冒到最尾部或者頂部
for (int i = 0; i < n - 1; i++)
{
if (A[i] > A[i + 1])
swap(A[i], A[i + 1]);
}
}
//冒泡排序
template <class T>
void bubbleSort(T A[], int n)
{
for (int i = n; i>1; i--)
{
bubble(A, i);
}
}
//測試代碼
int main(int argc, char ** argv)
{
int a[] = { 6, 4, 7, 2, 3, 1, 5 };
cout << "原數組是:" << endl;
for (int i = 0; i < 7; i++)
{
cout << a[i] << " ";
}
bubbleSort(a, 7);
cout << endl;
for (int i = 0; i < 7; i++)
{
cout << a[i] << " ";
}
Sleep(10000);
}
2.選擇排序法
選擇排序法是一種不穩定的排序算法。它的工作原理是每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的資料元素排完。
流程圖：
選擇排序C++代碼：
#include<iostream>
#include<Windows.h>
using namespace std;
template <class T>
int indexOfMax(T A[], int n)
{
int temp = A[0];
//找出最大值
for (int i = 0; i < n; i++)
{
if (temp < A[i])
temp = A[i];
}
//找出最大值的索引
int i = -1;
for (i = 0; i < n; i++)
{
if (temp == A[i])
break;
}
return i;
}
//選擇排序
template <class T>
void selectSort(T A[], int n)
{
//使用選擇排序算法給數組排序
for (int i = n; i > 1; i--)
{
int max = indexOfMax(A, i);
swap(A[max], A[i - 1]);
}
}
int main(int argc, char ** argv)
{
int a[] = {6,5,8,4,3,1};
selectSort(a, 6);
for (int i = 0; i<6; i++)
{
cout << " ," << a[i] << endl;
}
Sleep(10000);
}
3.插入排序法
插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法 。插入排序是一種簡單的排序方法，它的基本思想是将一個記錄插入到已經排好序的有序表中，進而形成一個新的、記錄數增1的有序表。在其實作過程使用雙層循環，外層循環對除了第一個元素之外的所有元素，内層循環對目前元素前面有序表進行待插入位置查找，并進行移動。
流程：
插入排序C++代碼：
#include<iostream>
using namespace std;
//插入元素
template<class T>
void insert(T a[], int n, const T &x)
{
int i;
for (i = n - 1; i >= 0 && x < a[i]; i--)
{
a[i + 1] = a[i];
}
a[i + 1] = x;
}
template <class T>
void insertSort(T a[], int n)
{
for (int i = 1; i < n; i++)
{
T t = a[i];
insert(a, i, t);
}
}
4.快速排序法
快速排序由C. A. R. Hoare在1960年提出。基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。
流程：
快速排序C++代碼：
int Paritition1(int A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot) {
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot) {
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[], int low, int high) //快排母函數
{
if (low < high) {
int pivot = Paritition1(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
5.希爾排序法
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵字越來越多，當增量減至 1 時，整個檔案恰被分成一組，算法終止。
流程：
希爾排序C++代碼：
template<typename T>
void shell_sort(T array[], int length) {
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
std::swap(array[j], array[j - h]);
}
}
h = h / 3;
}
}
6.計數排序法
計數排序是一個非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優勢在于在對一定範圍内的整數排序時，它的複雜度為Ο(n+k)（其中k是整數的範圍），快于任何比較排序算法。 當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間複雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）。它是計算一個序列中的值在正常排好序中的序列所處的位置，怎麼求解一個數的位置呢？就是利用下腳标進行求解，建立一個數組resu[]，數組的長度要比序列中的最大值大1，數組中的值全部初始化為0，然後周遊原序列，将原序列的值i作為建立數組resu[]的下腳表，對resu[i]++操作，這樣就得出值 i 出現的次數；然後再利用resu[i]=resu[i]+resu[i-1]求解出i在原序列中的位置。
流程：
計數排序的C++代碼：
#include<iostream>
#include<Windows.h>
using namespace std;
/**
求數組元素的名次，結果存入r中
**/
template <class T>
void rankarr(T arr[], int n, int r[])
{
for (int i = 0; i < n; i++)
{
r[i] = 0; //初始化r
}
//從第一個元素開始兩兩比較所有元素
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[j] <= arr[i])
r[i]++;
else
r[j]++;
}
}
}
//名次排序，計數排序
template <class T>
void rankSort(T a[], int n, int r[])
{
//建立一個數組
T *b = new T[n];
//把a中的元素移到b中的位置，按照r的名次
for (int i = 0; i < n; i++)
{
b[r[i]] = a[i];
}
//把b中元素移回到a
for (int i = 0; i < n; i++)
{
a[i] = b[i];
}
}
//測試代碼
int main(int argc, char ** argv)
{
//int a[] = { 3, 4, 2, 1, 6, 7, 2, 3, 5 ,4};
//cout << "原數組:" << endl;
//for (int i = 0; i < 10; i++)
//{
// cout << a[i] << " ";
//}
//int b[10];
排名次
//rankarr(a, 10, b);
按名次排序
//rankSort(a,10,b);
//cout<< endl;
//cout << "排序後:" << endl;
//for (int i = 0; i < 10; i++)
//{
// cout << a[i] << " ";
//}
int a = 1;
a <<= 33;
cout << a << endl;
Sleep(10000);
}
7.堆排序法
堆排序（英語：Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
在堆的資料結構中，堆中的最大值總是位于根節點（在優先隊列中使用堆的話堆中的最小值位于根節點）。堆中定義以下幾種操作：
(1)最大堆調整（Max Heapify）：将堆的末端子節點作調整，使得子節點永遠小于父節點。
(2)建立最大堆（Build Max Heap）：将堆中的所有資料重新排序。
(3)堆排序（HeapSort）：移除位在第一個資料的根節點，并做最大堆調整的遞歸運算。
[1] 首先，從要排序的數組開始建立一個大頂堆（這裡以大頂堆說明，如何建大頂堆，下面詳解），這樣由大頂堆的性質可知，堆頂的數最大；
[2] 然後，交換堆頂key[0]和堆的最後一個元素Key[n-1]，Key[0]<->Key[n-1] ,這樣最大的數就放到堆的最後Key[n-1]了；由于交換了元素，0 ~ (n-2)的節點可能不滿足大頂堆要求，是以然後對堆的Key[0]--Key[n-2]調整為大頂堆;
[3] 将調整好的大頂堆[0~(N-2)],交換堆頂Key[0]和堆的最後一個元素Key[n-2],Key[0]<->Key[n-2],這樣，Key[n-2]、Key[n-1]最大的兩個數都已經排好了；重新調整[0~（n-3）]為大頂堆；不斷重複此過程直到整個排序過程完成
如何建大頂堆呢？
[1] 首先，從最大的非葉節點（設為Key[i]）開始，往下進行調整，如果子孩子節點Key[2*i+1]和Key[2*i+2]較大的值比Key[i]的值大，則，交換該節點Key[i]與子節點中較大的節點。然後 以交換後的子節點作為目前節點，往下進行調整，直到遇到葉節點；
[2] 最大非葉節點Key[i]調整完畢後，對節點Key[i-1]進行往下調整，直到出現葉節點；不斷重複此過程，直到對根節點往下調整完畢；
下面是建大頂堆的執行個體：待排序數組為[5 16 3 20 17 4]
堆排序流程執行個體：
示範
堆排序C++代碼：
#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
// 建立父節點和子節點指針
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { // 如果子節點指針在範圍内才作比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個位元組點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else { // 否則交換父子內容再繼續子節點和孫節點比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
// 初始化，i從最後一個父節點開始調整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}
8.歸并排序
歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。歸并操作，也叫歸并算法，指的是将兩個順序序列合并成一個順序序列的方法。
歸并排序執行個體：
歸并排序C++代碼：
#include <iostream>
void Merge(int r[], int r1[], int s, int m, int t)
{
int i = s;
int j = m + 1;
int k = s;
while (i <= m && j <= t)
{
if (r[i] <= r[j])
r1[k++] = r[i++];
else
r1[k++] = r[j++];
}
if (i <= m)
while (i <= m)
r1[k++] = r[i++];
else
while (j <= t)
r1[k++] = r[j++];
for (int n = s; n <= t; n++)
r[n] = r1[n];
}
void MergeSort(int r[], int r1[], int s, int t)
{
if (s < t)
{
int m = (s + t) / 2;
MergeSort(r, r1, s, m);
MergeSort(r, r1, m + 1, t);
Merge(r, r1, s, m, t);
}
}
int main()
{
int r[8] = {10, 3, 5, 1, 9, 34, 54, 565}, r1[8];
MergeSort(r, r1, 0, 7);
for (int q = 0; q < 8; q++)
std::cout << r[q] << std::ends;
return 0;
}
9.桶排序
桶排序 (Bucket sort)或所謂的箱排序，工作的原理是将數組分到有限數量的桶子裡。每個桶子再個别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組内的數值是均勻配置設定的時候，桶排序使用線性時間（O（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
桶排序算法要求，資料的長度必須完全一樣，程式過程要産生長度相同的資料，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的掃描順序是按照上次掃描的結果來的，是以設計上提供相同的兩個桶資料結構。前一個儲存每一次掃描的結果供下次調用，另外一個臨時拷貝前一次掃描的結果提供給前一個調用。
資料結構設計：連結清單可以采用很多種方式實作，通常的方法是動态申請記憶體建立結點，但是針對這個算法，桶裡面的連結清單結果每次掃描後都不同，就有很多連結清單的分離和重建。如果使用動态配置設定記憶體，則由于指針的使用，安全性低。是以，筆者設計時使用了數組來模拟連結清單（當然犧牲了部分的空間，但是操作卻是簡單了很多，穩定性也大大提高了）。共十個桶，是以建立一個二維數組，行向量的下标0—9代表了10個桶，每個行形成的一維數組則是桶的空間。
平均情況下桶排序以線性時間運作。像基數排序一樣，桶排序也對輸入作了某種假設， 因而運作得很快。具 體來說，基數排序假設輸入是由一個小範圍内的整數構成，而桶排序則 假設輸入由一個随機過程産生，該過程将元素一緻地分布在區間[0，1)上。 桶排序的思想就是把區間[0，1)劃分成n個相同大小的子區間，或稱桶，然後将n個輸入數分布到各個桶中去。因為輸入數均勻分布在[0，1)上，是以一般不會有很多數落在一個桶中的情況。為得到結果，先對各個桶中的數進行排序，然後按次序把各桶中的元素列出來即可。
桶排序流程執行個體：
桶排序C++代碼：
#include<iostream>
usingnamespace std;
int a[]={1,255,8,6,25,47,14,35,58,75,96,158,657};
const int len=sizeof(a)/sizeof(int);
int b[10][len+1]={0};//将b全部置0
void bucketSort(int a[]);//桶排序函數
void distribute Elments(int a[],int b[10][len+1],int digits);
void collectElments(int a[],int b[10][len+1]);
int numOfDigits(int a[]);
void zeroBucket(int b[10][len+1]);//将b數組中的全部元素置0
int main()
{
cout<<"原始數組：";
for(int i=0;i<len;i++)
cout<<a[i]<<",";
cout<<endl;
bucketSort(a);
cout<<"排序後數組：";
for(int i=0;i<len;i++)
cout<<a[i]<<",";
cout<<endl;
return 0;
}
void bucketSort(int a[])
{
int digits=numOfDigits(a);
for(int i=1;i<=digits;i++)
{
distributeElments(a,b,i);
collectElments(a,b);
if(i!=digits)
zeroBucket(b);
}
}
int numOfDigits(int a[])
{
int largest=0;
for(int i=0;i<len;i++)//擷取最大值
if(a[i]>largest)
largest=a[i];
int digits=0;//digits為最大值的位數
while(largest)
{
digits++;
largest/=10;
}
return digits;
}
void distributeElments(int a[],int b[10][len+1],int digits)
{
int divisor=10;//除數
for(int i=1;i<digits;i++)
divisor*=10;
for(int j=0;j<len;j++)
{
int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10);
//numOfDigits為相應的(divisor/10)位的值,如當divisor=10時,求的是個位數
int num=++b[numOfDigist][0];//用b中第一列的元素來儲存每行中元素的個數
b[numOfDigist][num]=a[j];
}
}
void collectElments(int a[],int b[10][len+1])
{
int k=0;
for(int i=0;i<10;i++)
for(int j=1;j<=b[i][0];j++)
a[k++]=b[i][j];
}
void zeroBucket(int b[][len+1])
{
for(int i=0;i<10;i++)
for(int j=0;j<len+1;j++)
b[i][j]=0;
}
10.基數排序
基數排序（radix sort）屬于“配置設定式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，将要排序的元素配置設定至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。
實作方法：
最高位優先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後。再将各組連接配接起來，便得到一個有序序列。
最低位優先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重複，直到對k1排序後便得到一個有序序列
實作原理：
基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(Tabulation Machine)上的貢獻。它是這樣實作的：将所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。
基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
基數排序流程：
基數排序C++代碼：
int maxbit(int data[], int n) //輔助函數，求資料的最大位數
{
int maxData = data[0]; ///< 最大數
/// 先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優化點。
for (int i = 1; i < n; ++i)
{
if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p)
{
//p *= 10; // Maybe overflow
maxData /= 10;
++d;
}
return d;
/* 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 = new int[n];
int *count = new int[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;
}