一、前言

如果說各種編程語言是程序員的招式巫玻，那么數(shù)據(jù)結(jié)構(gòu)和算法就相當(dāng)于程序員的內(nèi)功丛忆。

想寫出精煉、優(yōu)秀的代碼仍秤，不通過不斷的錘煉熄诡，是很難做到的。

二诗力、八大排序算法

排序算法作為數(shù)據(jù)結(jié)構(gòu)的重要部分凰浮，系統(tǒng)地學(xué)習(xí)一下是很有必要的。

1、排序的概念

排序是計算機內(nèi)經(jīng)常進(jìn)行的一種操作袜茧，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列屿良。

排序分為內(nèi)部排序和外部排序。

若整個排序過程不需要訪問外存便能完成惫周，則稱此類排序問題為內(nèi)部排序尘惧。

反之，若參加排序的記錄數(shù)量很大递递，整個序列的排序過程不可能在內(nèi)存中完成喷橙，則稱此類排序問題為外部排序。

2登舞、排序分類

八大排序算法均屬于內(nèi)部排序贰逾。如果按照策略來分類，大致可分為：交換排序菠秒、插入排序疙剑、選擇排序、歸并排序和基數(shù)排序践叠。如下圖所示：

3言缤、算法分析

1.插入排序：

????● 直接插入排序

????● 希爾排序

2.選擇排序

????● 簡單選擇排序

????●?堆排序

3.交換排序

????●?冒泡排序

????●?快速排序

4.歸并排序

5.基數(shù)排序

不穩(wěn)定排序：簡單選擇排序，快速排序禁灼，希爾排序管挟，堆排序

穩(wěn)定排序：冒泡排序，直接插入排序弄捕，歸并排序穿铆，奇數(shù)排序

三荞雏、具體排序講解

下面針對不同排序進(jìn)行一一講解讯檐。

一、直接插入排序（Insertion Sort)

算法思想：

直接插入排序的核心思想就是：將數(shù)組中的所有元素依次跟前面已經(jīng)排好的元素相比較柳刮，如果選擇的元素比已排序的元素小痢毒，則交換哪替，直到全部元素都比較過 因此凭舶，從上面的描述中我們可以發(fā)現(xiàn)帅霜，直接插入排序可以用兩個循環(huán)完成：

? ? ? ? ??第一層循環(huán)：遍歷待比較的所有數(shù)組元素

??????????第二層循環(huán)：將本輪選擇的元素(selected)與已經(jīng)排好序的元素(ordered)相比較身冀。如果：selected > ordered，那么將二者交換兄墅。

算法代碼：

void print(int a[], int n ,int i){

? cout<<i <<":";

? for(int j= 0; j<8; j++){

? ? cout<<a[j] <<" ";

? }

? cout<<endl;

}

void InsertSort(int a[], int n)

{

? for(int i= 1; i<n; i++){

? ? if(a[i] < a[i-1]){? //若第i個元素大于i-1元素隙咸，直接插入。小于的話充包，移動有序表后插入

? ? ? int j= i-1;?

? ? ? int x = a[i];? ? //復(fù)制為哨兵基矮，即存儲待排序元素

? ? ? a[i] = a[i-1];? ? ? ? ? //先后移一個元素

? ? ? while(x < a[j]){? //查找在有序表的插入位置

? ? ? ? a[j+1] = a[j];

? ? ? ? j--;? ? //元素后移

? ? ? }

? ? ? a[j+1] = x;? ? //插入到正確位置

? ? }

? ? print(a,n,i);? ? ? //打印每趟排序的結(jié)果

? }

}

int main(){

? int a[8] = {3,1,5,7,2,4,9,6};

? InsertSort(a,8);

? print(a,8,8);

}

————————

二、希爾排序（Shell' s Sort）

算法思想:

希爾排序也稱遞減增量排序算法钢悲，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法还棱。

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時辞做，再對全體記錄進(jìn)行依次直接插入排序焙蹭。

算法步驟：

??? 1.選擇一個增量序列t1孔厉，t2撰豺，…污桦，tk凡橱，其中ti>tj识虚，tk=1累舷；

??? 2.按增量序列個數(shù)k澄者，對序列進(jìn)行k 趟排序侨拦；

??? 3.每趟排序蛀柴，根據(jù)對應(yīng)的增量ti矫夯，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序递沪。僅增量因子為1 時款慨，整個序列作為一個表來處理，表長度即為整個序列的長度埠戳。

算法代碼:

void print(int a[], int n ,int i){

? cout<<i <<":";

? for(int j= 0; j<8; j++){

? ? cout<<a[j] <<" ";

? }

? cout<<endl;

}

/**

* 直接插入排序的一般形式

*

* @param int dk 縮小增量，如果是直接插入排序喳钟，dk=1

*

*/

void ShellInsertSort(int a[], int n, int dk)

{

? for(int i= dk; i<n; ++i){

? ? if(a[i] < a[i-dk]){? ? ? //若第i個元素大于i-1元素奔则，直接插入共郭。小于的話，移動有序表后插入

? ? ? int j = i-dk;?

? ? ? int x = a[i];? ? ? //復(fù)制為哨兵尉咕，即存儲待排序元素

? ? ? a[i] = a[i-dk];? ? ? //首先后移一個元素

? ? ? while(x < a[j]){? ? //查找在有序表的插入位置

? ? ? ? a[j+dk] = a[j];

? ? ? ? j -= dk;? ? ? //元素后移

? ? ? }

? ? ? a[j+dk] = x;? ? ? //插入到正確位置

? ? }

? ? print(a, n,i );

? }

}

// 先按增量d（n/2,n為要排序數(shù)的個數(shù)進(jìn)行希爾排序

void shellSort(int a[], int n){

? int dk = n/2;

? while( dk >= 1? ){

? ? ShellInsertSort(a, n, dk);

? ? dk = dk/2;

? }

}

int main(){

? int a[8] = {3,1,5,7,2,4,9,6};

? //ShellInsertSort(a,8,1); //直接插入排序

? shellSort(a,8);? ? ? ? //希爾插入排序

? print(a,8,8);

}

————————

三、簡單選擇排序（Selection Sort）

算法思想：

簡單選擇排序的實現(xiàn)思想：比較+交換

????? 從待排序序列中蜕该，找到關(guān)鍵字最小的元素堂淡；

????? 如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換皆的；

????? 從余下的 N - 1 個元素中，找出關(guān)鍵字最小的元素义锥，重復(fù)(1)、(2)步岩灭，直到排序結(jié)束拌倍。因此我們可以發(fā)現(xiàn)，簡單選擇排序也是通過兩層循環(huán)實現(xiàn)噪径。

第一層循環(huán)：依次遍歷序列當(dāng)中的每一個元素?

第二層循環(huán)：將遍歷得到的當(dāng)前元素依次與余下的元素進(jìn)行比較柱恤，符合最小元素的條件，則交換找爱。

算法代碼：

void print(int a[], int n ,int i){

? cout<<"第"<<i+1 <<"趟 : ";

? for(int j= 0; j<8; j++){

? ? cout<<a[j] <<"? ";

? }

? cout<<endl;

}

/**

* 數(shù)組的最小值

*

* @return int 數(shù)組的鍵值

*/

int SelectMinKey(int a[], int n, int i)

{

? int k = i;

? for(int j=i+1 ;j< n; ++j) {

? ? if(a[k] > a[j]) k = j;

? }

? return k;

}

/**

* 選擇排序

*

*/

void selectSort(int a[], int n){

? int key, tmp;

? for(int i = 0; i< n; ++i) {

? ? key = SelectMinKey(a, n,i);? ? ? ? ? //選擇最小的元素

? ? if(key != i){

? ? ? tmp = a[i];? a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換

? ? }

? ? print(a,? n , i);

? }

}

int main(){

? int a[8] = {3,1,5,7,2,4,9,6};

? cout<<"初始值：";

? for(int j= 0; j<8; j++){

? ? cout<<a[j] <<"? ";

? }

? cout<<endl<<endl;

? selectSort(a, 8);

? print(a,8,8);

}

————————

四寺谤、堆排序（Heap Sort）

算法思想：

堆：本質(zhì)是一種數(shù)組對象。特別重要的一點性質(zhì)：任意的葉子節(jié)點小于（或大于）它所有的父節(jié)點澎灸。對此巩梢，又分為大頂堆和小頂堆：

???????????大頂堆要求節(jié)點的元素都要大于其孩子搁拙。

????????? 小頂堆要求節(jié)點元素都小于其左右孩子兴垦。

????????? 兩者對左右孩子的大小關(guān)系不做任何要求。

利用堆排序西潘，就是基于大頂堆或者小頂堆的一種排序方法蚂子。下面别渔，我們通過大頂堆來實現(xiàn)。

基本思想：堆排序可以按照以下步驟來完成：

??? 1.首先將序列構(gòu)建稱為大頂堆淤毛；（這樣滿足了大頂堆那條性質(zhì)：位于根節(jié)點的元素一定是當(dāng)前序列的最大值）

??? 2. 取出當(dāng)前大頂堆的根節(jié)點纸颜，將其與序列末尾元素進(jìn)行交換；（此時：序列末尾的元素為已排序的最大值慌盯；由于交換了元素，當(dāng)前位于根節(jié)點的堆并不一定滿足大頂堆的性質(zhì)）

??? 3. 對交換后的n-1個序列元素進(jìn)行調(diào)整跟衅，使其滿足大頂堆的性質(zhì)；

? ????4. 重復(fù)2.3步驟辩蛋，直至堆中只有1個元素為止

下面是基于大頂堆的堆排序算法代碼：

void print(int a[], int n){

? for(int j= 0; j<n; j++){

? ? cout<<a[j] <<"? ";

? }

? cout<<endl;

}

/**

* 已知H[s…m]除了H[s] 外均滿足堆的定義

* 調(diào)整H[s],使其成為大頂堆.即將對第s個結(jié)點為根的子樹篩選,

*

* @param H是待調(diào)整的堆數(shù)組

* @param s是待調(diào)整的數(shù)組元素的位置

* @param length是數(shù)組的長度

*/

void HeapAdjust(int H[],int s, int length)

{

? int tmp? = H[s];

? int child = 2*s+1; //左孩子結(jié)點的位置悼院。(i+1 為當(dāng)前調(diào)整結(jié)點的右孩子結(jié)點的位置)

? ? while (child < length) {

? ? if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比當(dāng)前待調(diào)整結(jié)點大的孩子結(jié)點)

? ? ? ++child ;

? ? }

? ? if(H[s]<H[child]) {? // 如果較大的子結(jié)點大于父結(jié)點

? ? ? H[s] = H[child]; // 那么把較大的子結(jié)點往上移動裆蒸，替換它的父結(jié)點

? ? ? s = child;? ? // 重新設(shè)置s ,即待調(diào)整的下一個結(jié)點的位置

? ? ? child = 2*s+1;

? ? }? else {? ? ? // 如果當(dāng)前待調(diào)整結(jié)點大于它的左右孩子跷睦，則不需要調(diào)整润绵，直接退出

? ? ? break;

? ? }

? ? H[s] = tmp;? ? ? // 當(dāng)前待調(diào)整的結(jié)點放到比其大的孩子結(jié)點位置上

? }

? print(H,length);

}

/**

* 初始堆進(jìn)行調(diào)整

* 將H[0..length-1]建成堆

* 調(diào)整完之后第一個元素是序列的最小的元素

*/

void BuildingHeap(int H[], int length)

{

? //最后一個有孩子的節(jié)點的位置 i=? (length -1) / 2

? for (int i = (length -1) / 2 ; i >= 0; --i)

? ? HeapAdjust(H,i,length);

}

/**

* 堆排序算法

*/

void HeapSort(int H[],int length)

{

? ? //初始堆

? BuildingHeap(H, length);

? //從最后一個元素開始對序列進(jìn)行調(diào)整

? for (int i = length - 1; i > 0; --i)

? {

? ? //交換堆頂元素H[0]和堆中最后一個元素

? ? int temp = H[i]; H[i] = H[0]; H[0] = temp;

? ? //每次交換堆頂元素和堆中最后一個元素之后尘盼，都要對堆進(jìn)行調(diào)整

? ? HeapAdjust(H,0,i);

? }

}

int main(){

? int H[10] = {3,1,5,7,2,4,9,6,10,8};

? cout<<"初始值：";

? print(H,10);

? HeapSort(H,10);

? //selectSort(a, 8);

? cout<<"結(jié)果：";

? print(H,10);

}

————————

五、冒泡排序（Bubble Sort）

算法思想：

冒泡遍歷所有的數(shù)據(jù)烦绳，每次對相鄰元素進(jìn)行兩兩比較卿捎，如果順序和預(yù)先規(guī)定的順序不一致，則進(jìn)行位置交換径密；

這樣一次遍歷會將最大或最小的數(shù)據(jù)上浮到頂端午阵，之后再重復(fù)同樣的操作，直到所有的數(shù)據(jù)有序睹晒。

這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端趟庄。

算法代碼：

void bubbleSort(int a[], int n){

? for(int i =0 ; i< n-1; ++i) {

? ? for(int j = 0; j < n-i-1; ++j) {

? ? ? if(a[j] > a[j+1])

? ? ? {

? ? ? ? int tmp = a[j] ; a[j] = a[j+1] ;? a[j+1] = tmp;

? ? ? }

? ? }

? }

}

————————

六、快速排序（Quick Sort）

算法思想：

快速排序是由東尼·霍爾所發(fā)展的一種排序算法伪很。在平均狀況下戚啥，排序n個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n2)次比較锉试，但這種狀況并不常見猫十。事實上，快速排序通常明顯比其他Ο(nlogn) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）拖云。

算法步驟：

????????? 從數(shù)列中挑出一個元素贷笛，稱為 “基準(zhǔn)”（pivot）。

????????? 重新排序數(shù)列宙项，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面乏苦，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后尤筐，該基準(zhǔn)就處于數(shù)列的中間位置汇荐。這個稱為分區(qū)（partition）操作。

????????? 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序盆繁。

遞歸的最底部情形掀淘，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了油昂。雖然一直遞歸下去革娄，但是這個算法總會退出，因為在每次的迭代（iteration）中冕碟，它至少會把一個元素擺到它最后的位置去拦惋。

算法代碼：

void print(int a[], int n){

? for(int j= 0; j<n; j++){

? ? cout<<a[j] <<"? ";

? }

? cout<<endl;

}

void swap(int *a, int *b)

{

? int tmp = *a;

? *a = *b;

? *b = tmp;

}

int partition(int a[], int low, int high)

{

? int privotKey = a[low];? ? ? ? ? ? ? ? //基準(zhǔn)元素

? while(low < high){? ? ? ? ? ? ? ? ? ? //從表的兩端交替地向中間掃描

? ? while(low < high? && a[high] >= privotKey) --high;? //從high 所指位置向前搜索，至多到low+1 位置鸣哀。將比基準(zhǔn)元素小的交換到低端

? ? swap(&a[low], &a[high]);

? ? while(low < high? && a[low] <= privotKey ) ++low;

? ? swap(&a[low], &a[high]);

? }

? print(a,10);

? return low;

}

void quickSort(int a[], int low, int high){

? if(low < high){

? ? int privotLoc = partition(a,? low,? high);? //將表一分為二

? ? quickSort(a,? low,? privotLoc -1);? ? ? //遞歸對低子表遞歸排序

? ? quickSort(a,? privotLoc + 1, high);? ? //遞歸對高子表遞歸排序

? }

}

int main(){

? int a[10] = {3,1,5,7,2,4,9,6,10,8};

? cout<<"初始值：";

? print(a,10);

? quickSort(a,0,9);

? cout<<"結(jié)果：";

? print(a,10);

}

————————

七架忌、歸并排序（Merge Sort）

算法思想：

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用我衬。

算法步驟：

????????? 申請空間，使其大小為兩個已經(jīng)排序序列之和饰恕，該空間用來存放合并后的序列挠羔；

????????? 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置埋嵌；

????????? 比較兩個指針?biāo)赶虻脑仄萍樱x擇相對小的元素放入到合并空間，并移動指針到下一位置雹嗦；

????????? 重復(fù)步驟3直到某一指針達(dá)到序列尾范舀；

????????? 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

算法代碼：

void print(int a[], int n){

? for(int j= 0; j<n; j++){

? ? cout<<a[j] <<"? ";

? }

? cout<<endl;

}

//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]

void Merge(ElemType *r,ElemType *rf, int i, int m, int n)

{

? int j,k;

? for(j=m+1,k=i; i<=m && j <=n ; ++k){

? ? if(r[j] < r[i]) rf[k] = r[j++];

? ? else rf[k] = r[i++];

? }

? while(i <= m)? rf[k++] = r[i++];

? while(j <= n)? rf[k++] = r[j++];

? print(rf,n+1);

}

void MergeSort(ElemType *r, ElemType *rf, int lenght)

{

? int len = 1;

? ElemType *q = r ;

? ElemType *tmp ;

? while(len < lenght) {

? ? int s = len;

? ? len = 2 * s ;

? ? int i = 0;

? ? while(i+ len <lenght){

? ? ? Merge(q, rf,? i, i+ s-1, i+ len-1 ); //對等長的兩個子表合并

? ? ? i = i+ len;

? ? }

? ? if(i + s < lenght){

? ? ? Merge(q, rf,? i, i+ s -1, lenght -1); //對不等長的兩個子表合并

? ? }

? ? tmp = q; q = rf; rf = tmp; //交換q,rf了罪，以保證下一趟歸并時锭环，仍從q 歸并到rf

? }

}

int main(){

? int a[10] = {3,1,5,7,2,4,9,6,10,8};

? int b[10];

? MergeSort(a, b, 10);

? print(b,10);

? cout<<"結(jié)果：";

? print(a,10);

}

————————

八、基數(shù)排序(Radix Sort)

算法思想：

基數(shù)排序：通過序列中各個元素的值泊藕，對排序的N個元素進(jìn)行若干趟的“分配”與“收集”來實現(xiàn)排序辅辩。

分配：我們將L[i]中的元素取出，首先確定其個位上的數(shù)字，根據(jù)該數(shù)字分配到與之序號相同的桶中 玫锋。

收集：當(dāng)序列中所有的元素都分配到對應(yīng)的桶中蛾茉，再按照順序依次將桶中的元素收集形成新的一個待排序列L[ ] 。

對新形成的序列L[]重復(fù)執(zhí)行分配和收集元素中的十位撩鹿、百位...直到分配完該序列中的最高位谦炬，則排序結(jié)束。

算法代碼：

Void RadixSort(Node L[],length,maxradix)

{

? int m,n,k,lsp;

? k=1;m=1;

? int temp[10][length-1];

? Empty(temp); //清空臨時空間

? while(k<maxradix) //遍歷所有關(guān)鍵字

? {

? ? for(int i=0;i<length;i++) //分配過程

? ? {

? ? ? if(L[i]<m)

? ? ? ? ? Temp[0][n]=L[i];

? ? ? else

? ? ? ? ? Lsp=(L[i]/m)%10; //確定關(guān)鍵字

? ? ? Temp[lsp][n]=L[i];

? ? ? n++;

? }

? CollectElement(L,Temp); //收集

? n=0;

? m=m*10;

? k++;

}

}

————————

看到這里节沦，你對“C語言八大排序算法”了解了多少键思？

如果你想更深入的學(xué)習(xí)C語言，小編推薦一個C語言編程學(xué)習(xí)俱樂部【下圖進(jìn)入】散劫！

涉及到：C語言稚机、C++、windows編程获搏、網(wǎng)絡(luò)編程赖条、QT界面開發(fā)、Linux編程常熙、游戲編程纬乍、黑客等等......

編程入門資料：

?推薦學(xué)習(xí)書籍：

一個活躍、高逼格裸卫、高層次的編程學(xué)習(xí)殿堂仿贬；編程入門只是順帶，思維的提高才有價值墓贿！

四茧泪、總結(jié)

各種排序的穩(wěn)定性，時間復(fù)雜度和空間復(fù)雜度總結(jié)：

我們比較時間復(fù)雜度函數(shù)的情況：

時間復(fù)雜度函數(shù)O(n)的增長情況

所以對n較大的排序記錄聋袋。一般的選擇都是時間復(fù)雜度為O(nlog2n)的排序方法队伟。

時間復(fù)雜度來說：

(1)平方階(O(n2))排序

????各類簡單排序：直接插入、直接選擇和冒泡排序幽勒；

(2)線性對數(shù)階(O(nlog2n))排序

????快速排序嗜侮、堆排序和歸并排序；

(3)O(n1+§))排序,§是介于0和1之間的常數(shù)啥容。

????希爾排序

(4)線性階(O(n))排序

????基數(shù)排序锈颗，此外還有桶、箱排序咪惠。

總結(jié)

以上所述是小編給大家介紹的必須知道的C語言 八大排序算法(值得收藏)击吱，希望對大家有所幫助！