總第123篇

好久不見哈，我終于又更新了，驚不驚喜，意不意外，哈哈哈哈。等之后會專門寫一篇文章給大家匯報匯報我最近在忙什么呢，今天這篇還是接著之前的數(shù)據(jù)結(jié)構(gòu)系列繼續(xù)，主要講講數(shù)據(jù)結(jié)構(gòu)里面常用的幾種排序算法。

1.排序的基本概念

假設(shè)現(xiàn)在有n個記錄的序列{r1,r2,……,rn}，其相應(yīng)關(guān)鍵字分別為{k1,k2,……,kn},需要確定1，2，……,n的一種排列p1,p2,……,pn，使其相應(yīng)的關(guān)鍵字蠻子kp1<=kp2<=kp3<=……<=kpn的關(guān)系，即使得序列成為一個按關(guān)鍵字有序排列的序列，這樣的操作稱為排序。

1.1排序的穩(wěn)定性

關(guān)鍵字又分為主關(guān)鍵字和次關(guān)鍵字，主關(guān)鍵字只有一個，但是次關(guān)鍵字個數(shù)不限。因為排序不僅針對主關(guān)鍵字，也會參考次關(guān)鍵字進(jìn)行排序。因待排序的記錄序列中可能存在兩個或兩個以上的關(guān)鍵字相等的記錄，排序結(jié)果會出現(xiàn)不唯一的情況。如果兩個序列值在按關(guān)鍵字排序前是A在B前面，如果經(jīng)過排序后，A仍在B前面，則稱排序是穩(wěn)定的；若排序后A到了B的后面，則排序是不穩(wěn)定的。

1.2內(nèi)排序與外排序

內(nèi)排序是在排序的整個過程中，待排序的所有記錄全部被放置在內(nèi)存中。外排序是由于排序的記錄個數(shù)太多，不能同時放置在內(nèi)存中，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行。

1.3排序算法類別

排序總共有四種類別，七種算法，具體類別如下：

1.3.1插入類排序

插入類排序重點在插入這兩個字，具體是在一個已經(jīng)有序的序列中，插入一個新的關(guān)鍵字，通過將待插入關(guān)鍵字與已經(jīng)有序的序列中每個值進(jìn)行比較，找到合適的插入位置，使插入后整個序列依然是有序的。直接插入排序、折半排序、希爾排序均屬于這類排序。

1.3.2交換類排序

交換類排序重點在交換這兩個字，通過不停比較兩個數(shù)值之間的大小然后交換兩個數(shù)值的位置，重復(fù)這個過程，直到最后整個序列有序。冒泡排序和快速排序?qū)儆谶@類別排序。

1.3.3選擇類排序

選擇類排序的重點在選擇這兩個字，從待排序序列中選出一個最小（或最大）的關(guān)鍵字，把它和序列中的第一個（或最后一個）關(guān)鍵字進(jìn)行交換，這樣最小（或最大）的關(guān)鍵字就排到了有序的位置，繼續(xù)循環(huán)這個過程，直到整個序列有序。簡單選擇排序和堆排序?qū)儆谶@種排序類別。

1.3.4歸并類排序

歸并類排序就是將兩個或兩個以上的有序序列合并成一個新的有序序列

1.4排序算法用的結(jié)構(gòu)與函數(shù)

用于排序的順序表結(jié)構(gòu)，此結(jié)構(gòu)將會用于接下來要講的所有順序結(jié)構(gòu)。

#define?MAXSIZE?10????//要排序數(shù)組個數(shù)最大值 typedef?struct {int?r[MAXSIZE?+?1];????//用來存儲要排序數(shù)組int?length;????//用來記錄順序表長度 }

排序最常用的操作就是數(shù)組兩元素的交換，我們將這個交換過程寫成函數(shù)，方便之后的調(diào)用。

void?swap(SqList?*L,int?i,int?j) {int?temp?=?L->r[i];L->r[i]?=?L->r[j]L->r[j]?=?temp; }

2.插入類排序

2.1直接插入排序

直接插入排序類似于我們在打撲克的時候的理牌過程，我們一般都是一邊接牌一邊理牌，理牌的時候都是直接通過將新接的牌（待排序的數(shù)據(jù)）插入到前面已經(jīng)排好序的序列中。插入排序的具體過程如下：

• step1：從第一個元素開始，默認(rèn)第一個元素是已經(jīng)排好序的；

• step2：取出下一個元素作為待插入元素，然后將這個待插入元素與它前面的已經(jīng)排好序的每一個元素（即已經(jīng)插入到序列中的所有值）進(jìn)行比較，如果待插入元素的值比它前面已經(jīng)排序好的數(shù)值小，則將已經(jīng)在序列中的數(shù)后移一位，直到不需要后移了，新元素插入到空位；

• 重復(fù)step2，直到待插入序列中的所有數(shù)值全部插入完畢。

具體實現(xiàn)代碼如下：

void?Insertsort(int?R[],int?n)//R[]用來存放待插入排序的所有值 {int?i,j;int?temp;?//用來存放待插入值for(i?=?1;i?<?n;++i){temp?=?R[i];//待插入值為序列R[]中的第i個值j?=?i?-?1;//待插入數(shù)值前一位while(j>=0&&temp<R[j])//當(dāng)待插入值temp小于它前面的數(shù)時，前面的數(shù)就需要后移{R[j+1]?=?R[j];--j;//通過前移遍歷已排序好的序列中的每一個值}R[j+1]?=?temp;//將temp插入到R[j+1]的位置}}

2.2折半插入排序

折半排序是在直接插入排序的基礎(chǔ)上進(jìn)行改進(jìn)的，直接插入是遍歷待排序中的每一個值，而折半插入排序是采用每次尋找當(dāng)前位置的一半進(jìn)行插入排序，其實就是我們高中學(xué)的二分查找求根的方法。

2.3希爾排序

直接插入排序在有些時候效率是很高的，比如待排序的數(shù)據(jù)本身是基本有序的，我們只需要執(zhí)行少量的插入操作即可；或者是待排序的記錄很少時，直接插入排序效率也是挺高。但是現(xiàn)實中的數(shù)據(jù)很難滿足這兩個條件，所以就需要人為去把數(shù)據(jù)整理成符合這兩個條件的數(shù)據(jù)。

如何讓待排序的記錄個數(shù)較少呢？比較直接的方法就是將原來的大量記錄數(shù)進(jìn)行分組，分割成若干個子序列，這樣待排序記錄數(shù)就變少了，然后可以在各個組內(nèi)直接利用插入排序，當(dāng)整個序列基本有序時，再對全體記錄進(jìn)行一次直接插入排序。我們把這種方式稱作希爾排序。

現(xiàn)在比較重要的問題就是如何對原數(shù)據(jù)進(jìn)行分組，如果直接等距離切割的話，比如原序列是{9，1，5，8，3，7，4，6，2}，現(xiàn)在把他們等距離切割成三份，{9，1，5}，{8，3，7}，{4，6，2}，對這三組分別采用直接插入排序以后變成{1，5，9}，{3，7，8}，{2，4，6}，然后將三組進(jìn)行合并變成{1，5，9，3，7，8，2，4，6}，這個序列目前還是雜亂的，還需要對這個序列整體再來一遍直接插入排序，但是這個經(jīng)過切割以后序列和原序列并沒有太大的不同，這主要是因為我們切割的時候是等距切割的。為了避免這種切割以后用處不大的情況，所以我們采用以某種相隔距離開始分組，比如選擇1、3、5位置的數(shù)作為一組，2、4、6位置的數(shù)作為一組這樣跳躍切割的方式進(jìn)行。實現(xiàn)代碼如下：

void?ShellSort(SqList?*L) {int?i,j;int?incremrnt?=?L->length;do{incremrnt?=?increment/3+1;????//間隔序列for(i=increment+1;i<L-length;i++){if(L->r[i]<L->[i-increment]){L->r[0]=L->r[i];for(j=i-increment;j>0&&L->r[0]<L->r[j];j-=increment)L->r[j+increment]=L->r[j];????//記錄后移，查找插入位置L->r[j+increment]=L->r[0];????????//插入}}} }

3.交換類排序

3.1冒泡排序

冒泡排序是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序記錄為止。

實現(xiàn)步驟如下：

• step1:從第一位開始，兩兩比較相鄰數(shù)值，如果兩個數(shù)值是降序，則交換彼此的位置,直到最后一位，這樣最后一位肯定是最大的數(shù)值；

• step2:因最后一位已經(jīng)是最大值了，所以除最后一位外，其他數(shù)值再次執(zhí)行step1；

• step3:重復(fù)上述的step1、step2直到所有數(shù)值排序完成。

3.1.1最基礎(chǔ)冒泡排序?qū)崿F(xiàn)

遍歷序列中的每一個值，然后將該值與其后面序列中的每個值作比較，如果大于則交換彼此位置。

void?BubbleSort0(SqList?*L) {int?i,j;for(i=1;i<L-length;i++){for(j=i+1;j<L-length;j++){if(L->r[i]?>?L->r[j]){swap(L,i,j)}}} }

這種算法嚴(yán)格意義上并不是冒泡排序，因為他不滿足兩兩比較相鄰記錄的冒泡排序思想。

3.1.2正規(guī)冒泡排序

正規(guī)冒泡排序執(zhí)行的過程是按照我們前面的講過的冒泡排序的基本步驟來的，具體實現(xiàn)代碼如下：

void?BubbleSort(SqList?*L) {int?i,j;for(i=1;i<L-length;i++){for(j=L-length-1;j>=i;j--){if(L->r[j]?>?L->r[j+1])????//注意這里是比較j與j+1{swap(L,j,j+1);????????//交換L->r[j]與L->r[j+1]的位置}}} }

上面代碼表示從序列的末尾依次往前遍歷比較，先從倒數(shù)第二位與倒數(shù)第一位開始比較，i值用來控制最后不參加比較的數(shù)值的位數(shù)（即已經(jīng)是最大值的位數(shù)），剛開始i值是1，表示所有數(shù)值數(shù)值均參與排序，當(dāng)比較完一次（即j的for循環(huán)執(zhí)行完一次）以后，i的值加1，而參與比較的數(shù)值個數(shù)減1，循環(huán)此過程，直到所有的數(shù)值均已排序完成（即i的值大于等于待排序序列的長度）。

3.1.3改進(jìn)版冒泡排序

我們上面講的普通的冒泡排序中，只有最后一位不參與排序，除最后一位以外的其他序列還是都得參與排序，不管是否有序，如果除第一位以外的其他序列已經(jīng)是全部或部分有序的，那么是不是就可以不去遍歷比較了呢？答案肯定是的，只需要添加一個標(biāo)志用來判斷哪一部分序列是排好序的。

void?BubbleSort2(SqList?*L) {int?i,j;Status?flag?=?True;????//flag用來標(biāo)記哪部分是已排序好的for(i=1,i<L-length&&flag;i++){flag?=?False;for(j=L->length-1;j>=i;j--){if(L->r[j]?>?L->r[j+1]){swap(L[j],L[j+1])flag?=?True}}} }

3.2快速排序

終于到了傳說中的快排了，快排是快速排序的簡稱，是交換類排序的其中一種。快速排序在開始排序之前會先選中一個中間值M(注意這里的中間值并非實際意義上的中值)，一般會用待排序列中的第一個數(shù)，每執(zhí)行一次排序會將待排序序列分成兩部分，其中一部分中的所有數(shù)都要比中間值M大，而另一部分中的所有值要比中間值M小，在這兩部分內(nèi)再分別進(jìn)行快排，也是同樣先找一個中間值M，然后進(jìn)行數(shù)區(qū)間切分，循環(huán)這個過程，直到所有的序列切分完畢，最后會得到一個有序的序列，具體實現(xiàn)代碼如下：

void?QuickSort(int?R[],int?low,int?high) {int?temp;int?i?=?low;j?=?high;if(low?<?high){temp?=?R[low];//序列的第一個值作為中間值while(i<j){while(j>i&&R[j]>=temp)//從右往左尋找小于temp的值--j;if(i<j){R[i]=R[j];//放在temp左邊++i;//i后移一位}while(i<j&&R[i]<temp)//從左往右尋找大于temp的值++i;if(i<j){R[j]=R[i];//放在temp右邊--j;//左移一位}}}R[i]?=?temp;//將temp擋在最終位置QuickSort(R,low,i-1);//對temp左邊的值再執(zhí)行快排QuickSort(R,i+1,high);//對temp右邊的值再執(zhí)行快排 }

4.選擇類排序

4.1簡單選擇排序

冒泡排序是在一邊比較一邊交換，只要出現(xiàn)后面的值小于前面的值，就把兩者進(jìn)行調(diào)換，然后繼續(xù)比較；而簡單選擇排序是比較某一位置的數(shù)與該位置之后的所有數(shù)，如果該位置之后序列中的數(shù)有比該位置的數(shù)小，則調(diào)換兩者的位置，否則進(jìn)入下一個循環(huán),這個方法有點類似于基礎(chǔ)的冒泡排序。簡單選擇排序與冒泡排序相比就是省略了很多交換的過程。具體實現(xiàn)代碼如下：

void?SelectSort(SqList?*L) {int?i,j,min;for(i=1;i<L->length;i++){min?=?i;for(j?=?i+1;j<=L->length;j++){if(L->r[min]?>?L->r[j])?//如果存在i后面的值比i值小//則把該值傳給參數(shù)minmin?=?j;}if(i?!=?min)???//如果最小值不是i，則交換i和min的位置swap(L,i,min);}}

4.2堆排序

前面的簡單選擇排序中，在待排序的n個記錄中選擇一個最小的記錄需要比較n-1次，繼續(xù)在剩下的n-1條記錄里面比較n-2次才能得出第二個最小值。每次都需要比較剩下的所有值，然后從中挑選出最小值。但實際上有一些值之間是已經(jīng)對比過了，就沒必要再對比一次，如果要是可以針對已經(jīng)比較過的值做一個調(diào)整，那樣就可以避免很多不必要的比較啦。堆排序就是專門為了解決這個問題的，堆排序是改進(jìn)版的簡單選擇排序。

4.2.1堆概念

堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆；或者每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆。

4.2.2堆排序?qū)崿F(xiàn)

堆排序就是利用堆進(jìn)行排序的方法。它的基本思想是，將待排序的序列構(gòu)成一個大頂堆。這樣，整個序列的最大值就是堆頂?shù)母?jié)點。將根節(jié)點移走，根節(jié)點是最大值，然后再將剩余的n-1個序列重新構(gòu)造成一個堆，新堆的根節(jié)點是新堆的最大值，也是這n個元素中的次大值。如此重復(fù)，便可得到一個有序序列。

所以堆排序其實就是兩個步驟，第一步是將待排序數(shù)據(jù)轉(zhuǎn)換成一個大堆頂，第二步就是逐步將每個最大值的根結(jié)點移走，并且再次調(diào)整為大頂堆。具體實現(xiàn)代碼如下：

void?HeapSort(SqList?*L) {int?i;for(i=L->length/2;i>0,i--)????//將L中的r構(gòu)建成一個大堆頂HeapAdjust(L,i,L->length)????//HeaPAdjust是將待排序數(shù)據(jù)調(diào)整為大頂堆的過程for(i=L->length;i>1;i--)????{swap(L,1,i);????//將堆頂記錄和當(dāng)前未經(jīng)排序子序列的最后一個記錄進(jìn)行交換???HeapAdjust(L,1,i-1);????} }

HeapAdjust函數(shù)實現(xiàn)代碼

/已知L->r[s...m]中記錄的關(guān)鍵字除L->r[s]之外均滿足堆的定義/ /本函數(shù)調(diào)整L->r[s]的關(guān)鍵字，使L->r[s...m]成為一個大頂堆/ void?HeapAdjust(SqList?*L,int?s,int?m) {int?temp,j;temp?=?L->r[s];for(j=2*s;j<=m;j*=2)????//沿關(guān)鍵字較大的孩子結(jié)點向下篩選{if(j<m&&L->r[j]<L->r[j+1])++j;???????????????????????//j為關(guān)鍵字中較大的記錄的下標(biāo)if(temp>=L->r[j])break;????????????????????//rc應(yīng)插入的位置sL->r[s]=L->r[j];s=j;}L->r[s]=temp;????????//插入 }

5.歸并排序

歸并有序是一種分而治之的算法，歸并排序有多路歸并，我們以最簡單的二路歸并進(jìn)行講解：先將整個序列分成兩半，對每一半內(nèi)分別再進(jìn)行歸并排序，這樣將得到兩個有序序列，然后將這兩個有序序列歸并成一個序列即可。具體實現(xiàn)代碼如下：

void?mergeSort(int?A[],int?low,int?high) {if(low?<?high){int?mid?=?(low?+?high)/2;mergeSort(A,low,mid);?//歸并排序前半段mergeSort(A,mid+1,high);//歸并排序后半段merge(A,low,mid,high);//合并兩個歸并排序后的有序序列} }

你還可以看：

數(shù)據(jù)結(jié)構(gòu)—線性表

數(shù)據(jù)結(jié)構(gòu)-棧和隊列

數(shù)據(jù)結(jié)構(gòu)—字符串

數(shù)據(jù)結(jié)構(gòu)—樹與二叉樹

數(shù)據(jù)結(jié)構(gòu)-圖

總結(jié)

以上是生活随笔為你收集整理的数据结构-常用的排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。