C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(一)

第C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(一)解讀：如上個(gè)表格這樣的一個(gè)無序數(shù)組，想要將它按照從小到大排序。上圖下標(biāo)2和6對(duì)應(yīng)的數(shù)字都是10，排序后假如紅色的10任然在黑色的10前面，那這種排序方法就是穩(wěn)定的，否則排序方法不穩(wěn)定。

3.內(nèi)部和外部排序

內(nèi)部排序：整個(gè)排序過程在內(nèi)存中

外部排序：需要排序的數(shù)過大，需要借助外部設(shè)備

三、插入類排序

插入類：在一個(gè)有序序列插入一個(gè)新的記錄，使之仍然有序

1.直接插入排序

動(dòng)態(tài)演示：

算法講解：

上面的動(dòng)態(tài)圖可以很好的表達(dá)直接插入的過程，只是動(dòng)態(tài)圖有點(diǎn)長

首先將0作為監(jiān)視哨，用一個(gè)指針從前往后找后面的數(shù)字比前面數(shù)字小的，找到了放到0

指針開始向前移動(dòng)，如果指向的值比監(jiān)視哨里的值大，數(shù)字向后移

如果指向的值比監(jiān)視哨里的值小，那把監(jiān)視哨里的值存入這個(gè)元素之后

以此類推

代碼：

voidInsSort(RecordTyper[],intlength)

/*對(duì)記錄數(shù)組r做直接插入排序，length為數(shù)組中待排序記錄的數(shù)目*/

inti,j;

for(i=2;i=length;i++)

r[0]=r[i];/*將待插入記錄存放到監(jiān)視哨r[0]中*/

j=i-1;

while(r[0].keyr[j].key)/*尋找插入位置*/

r[j+1]=r[j];

j=j-1;

r[j+1]=r[0];/*將待插入記錄插入到已排序的序列中*/

}/*InsSort*/

特點(diǎn)：

穩(wěn)定排序

時(shí)間復(fù)雜度O(n*n),空間復(fù)雜度O(1)

2.折半插入排序

算法講解：

動(dòng)態(tài)圖沒找到，只能用上面這張圖片了

折半插入和折半查找思想差不多，對(duì)于一個(gè)有序的數(shù)組，將一個(gè)數(shù)字插入之后任然有序

k=要插入的值

low=1,high=length,mid=(low+high)+1

mid對(duì)應(yīng)的值比k大，high=low-1,否則low=mid+1,

當(dāng)lowhigh，low后面就是k插入的位置

代碼：

voidBinSort(RecordTyper[],intlength)

/*對(duì)記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長度*/

inti,j;

RecordTypex;

intlow,high,mid;

for(i=2;i=length;++i)

x=r[i];low=1;high=i-1;

while(low=high)/*確定插入位置*/

mid=(low+high)/2;

if(x.keyr[mid].key)high=mid-1;

elselow=mid+1;

for(j=i-1;j=low;--j)r[j+1]=r[j];/*記錄依次向后移動(dòng)*/

r[low]=x;/*插入記錄*/

}/*BinSort*/

特點(diǎn)：

穩(wěn)定排序

時(shí)間復(fù)雜度O(n*n),空間復(fù)雜度O(1)

3.希爾排序

動(dòng)態(tài)演示：

算法講解：

對(duì)于希爾排序來說取增量d(d一般為奇數(shù)，并且逐次遞減)

上圖第一次排序d等于5，將第一個(gè)作為起始點(diǎn)，下標(biāo)+5取下一個(gè)值，一直到最后，將去到的值從小到達(dá)排序，然后將第二個(gè)作為起始點(diǎn)，345依次作為起始點(diǎn)排序

第二次是d等于3

第三次是d等于1

代碼：

voidShellInsert(RecordTyper[],intlength,intdelta)

/*對(duì)記錄數(shù)組r做一趟希爾插入排序，length為數(shù)組的長度,delta為增量*/

{inti,j;

for(i=1+delta;i=length;i++)/*1+delta為第一個(gè)子序列的第二個(gè)元素的下標(biāo)*/

if(r[i].keyr[i-delta].key)

r[0]=r[i];/*備份r[i](不做監(jiān)視哨)*/

for(j=i-delta;j0r[0].keyr[j].key;j-=delta)

r[j+delta]=r[j];

r[j+delta]=r[0];

}/*ShellInsert*/

特點(diǎn)：

不穩(wěn)定排序方法

增量序列的d取值無除1之外的公因子，最后一個(gè)增量值必須為1

時(shí)間復(fù)雜度O(nlogn)

空間復(fù)雜度O(1)

四、交換類排序

1.冒泡排序

動(dòng)態(tài)演示：

算法講解：

設(shè)立兩個(gè)指針，i，j

每一次排序都會(huì)把最大的一個(gè)數(shù)放到后面，依次類推，假設(shè)執(zhí)行2次以后，那么最后2個(gè)數(shù)就不需要比較了

執(zhí)行n-1次排序，結(jié)果完成

代碼：

voidBubbleSort(RecordTyper[],intlength)

/*對(duì)記錄數(shù)組r做冒泡排序，length為數(shù)組的長度*/

{intn,i,j;ntchange;RecordTypex;n=length;change=TRUE;

for(i=1;i=n-1change;++i)

{change=FALSE;

for(j=1;j=n-i;++j)

if(r[j].keyr[j+1].key)

x=r[j];

r[j]=r[j+1];

r[j+1]=x;

change=TRUE;

}/*BubbleSort

特點(diǎn)：

穩(wěn)定排序

時(shí)間復(fù)雜度O(n*n),空間復(fù)雜度O(1)

2.快速排序

動(dòng)態(tài)演示：

算法講解：

快速排序講起來稍微有點(diǎn)復(fù)雜，其實(shí)就是劃分區(qū)域

建立兩個(gè)指針lowhigh分別指向第一個(gè)和第二個(gè)元素，把第一個(gè)元素的值賦給x變量

high向前移動(dòng)，假如high指向的值小于x，則high指向的值與x互換

low向后移動(dòng)，假如low指向的值大于x，則low指向的值與x互換

重復(fù)34兩步，知道high==low，第一次結(jié)束

將low指向第二個(gè)元素，把第二個(gè)元素的值賦給x變量

重復(fù)操作，知道元素有序

代碼：

1.遞歸算法:

voidQKSort(RecordTyper[],intlow,inthigh)

/*對(duì)記錄數(shù)組r[low..high]用快速排序算法進(jìn)行排序*/

intpos;

if(lowhigh)

pos=QKPass(r,low,high);/*調(diào)用一趟快速排序，將樞軸元素為界劃分兩個(gè)子表*/

QKSort(r,low,pos-1);/*對(duì)左部子表快速排序*/

QKSort(r,pos+1,high);/*對(duì)右部子表快速排序*/

}

2.非遞歸算法：

intQKPass(RecordTyper[],intleft,intright)

/*對(duì)記錄數(shù)組r中的r[left]至r[right]部分進(jìn)行一趟排序，并得到基準(zhǔn)的位置，使得排序后的結(jié)果滿足其之后（前）的記錄的關(guān)鍵字均不小于（大于）于基準(zhǔn)記錄*/

RecordTypex;intlow,high;

x=r[left];/*選擇基準(zhǔn)記錄*/

low=left;high=right;

while(lowhigh)

while(lowhighr[high].key=x.key)/*high從右到左找小于x.key的記錄*/

high--;

if(lowhigh){r[low]=r[high];low++;}/*找到小于x.key的記錄，則進(jìn)行交換*/

while(lowhighr[low].keyx.key)/*low從左到右找大于x.key的記錄*/

low++;

if(lowhigh){r[high]=r[low];high--;}/*找到大于x.key的記錄，則交換*/

r[low]=x;/*將基準(zhǔn)記錄保存到low=high的