數(shù)據(jù)結(jié)構(gòu) 內(nèi)部排序?qū)嶒?yàn)

數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)六：排序?qū)嵺`

姓名：沈靖雯

班級(jí)：14信科二班

學(xué)號(hào)：2022326601094

實(shí)驗(yàn)六排序?qū)嵺`

【實(shí)驗(yàn)內(nèi)容】

實(shí)現(xiàn)各排序算法并進(jìn)行性能比較

【實(shí)驗(yàn)?zāi)康摹?/p>

掌握各排序算法的實(shí)現(xiàn)方法，并分析各排序算法的時(shí)間和空間性能。

【問(wèn)題描述】

實(shí)現(xiàn)各排序算法，必須實(shí)現(xiàn)希爾排序和快速排序算法，其他排序算法選做，

并分析各算法的性能。

【問(wèn)題實(shí)現(xiàn)】

(1)數(shù)據(jù)結(jié)構(gòu)類

#defineMAXSIZE20

typedefstruct{

intkey;

)Redtype;

typedefstruct{

Redtyper[MAXSIZE+l];

intlength;

}SqList;

(2)主要算法函數(shù)：

1).希爾排序；

一趟希爾插入排序代碼如下，其中dk為先后記錄位置的增量，一次希爾

排序后，記錄按增量dk有序：

voidShelllnsert(SqList&QJntdk)〃希爾插入排序

{inti,j;

for(i=dk+l;i<=Q.length;i++)

if(Q.r[i].key<Q.r[i-dk].key){

Q.r[0]=Q.r[i];

for(j=i-dk;j>0&&(Q.r[0].key<Q,r[j].key);j-=dk)

Q.r[j+dk]=Q.r[j];

Q.r[j+dk]=Q.r[O];

}

for(inti=l;i<=Q.length;i++){〃一次希爾排序輸出

printf("%d",Q.r[i].key);

)

printf("\n");

}

完整實(shí)現(xiàn)序列的希爾排序代碼如下，其中增量序列簡(jiǎn)化為例題所用序列5,3,1：

voidShellsort(SqList&Q)〃希爾排序

{intdlta[10];

for(intk=5;k>0;k-=2){

She川nsert(Qk);

}

)

2).快速排序；

快速排序是對(duì)起泡排序的一種改進(jìn)。下面是一次快速排序的函數(shù)代碼，

其中pivotkey表示軸樞，用子表第一個(gè)記錄做軸樞記錄，函數(shù)返回新的軸樞位置:

intpartition(SqList&Q,intlowjnthigh)

(

Q.r[0]=Q.r[low];

intpivotkey;

pivotkey=Q.r[low].key;

while(low<high){

while(low<high&&Q,r[high].key>=pivotkey)-high;

Q.r[low]=Q.r[high];

while(low<high&&Q,r[low].key<=pivotkey)++low;

Q.r[high]=Q.r[low];

)

Q.r[low]=Q.r[0];

for(inti=l;iv=QJength;i++){//一次快速排序輸出

printf(n%d”,Q.r[i].key);

}

printf("\n");

returnlow;

)

遞歸法完整實(shí)現(xiàn)序列的快速排序，每次將序列以軸樞為界分為兩部份

(子序列)，對(duì)子序列分別進(jìn)行快速排序，再將子序列以其軸樞為界分為兩部份

進(jìn)行快速排序……以此類推直至序列全部排序完成：

voidQSort(SqList&(Xintlowjnthigh){

if(low<high){

intpivotloc;

pivotloc=partition(Q,low,high);

QSort(Q,low,pivotloc-l);

QSort(Q,pivotloc+l,high);

}

}

voidQuickSort(SqList&Q){

QSort(Q,l,Q.length);

)

3).起泡排序；

在寫快速排序之前寫了起泡排序比對(duì)，起泡排序代碼詳細(xì)見附件。

【總結(jié)】

希爾排序：將序列分組為子序列分別進(jìn)行直接插入排序，關(guān)鍵字較小的記錄

跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序，只需少

量比較和挪移即可完成排序。時(shí)間復(fù)雜度具體取決于所取的增量序列函數(shù)，相較

于直接插入排序低；希爾排序空間復(fù)雜度0(1)。

起泡排序：若初始序列正序，只需一趟排序，進(jìn)行n-1次比較，不挪移記錄，

時(shí)間復(fù)雜度為0(n)；最壞情況即初始序列為逆序，需進(jìn)行n-1次排序，

(i-l)=n(n-1)/2次比較，并作等數(shù)量級(jí)挪移，時(shí)間復(fù)雜度為0(*)；起泡

i=n

排序空間復(fù)雜度0(1)。

快速排序：作為起泡排序的改進(jìn)，平均時(shí)間為T⑻;由的，k為某個(gè)常

avg

數(shù)，在所有同數(shù)量級(jí)(O(nlogn))排序方法中平均性能最好。時(shí)間復(fù)雜度最好情

況O(nlogn),最壞情況當(dāng)初始序列按關(guān)鍵字有序或者基本有序時(shí)，蛻化為起泡排序,

時(shí)間復(fù)雜度為。(小)?？焖倥判蚩臻g復(fù)雜度O(nlogn)。

相比較而言希爾排序和快速排序時(shí)間性能較好，空間性能則希爾排序和起泡

排序較好。

程序運(yùn)行截圖:

圖1

^牛：

源代碼：

#include<stdio.h>

include<math.h>

#defineMAXSIZE20

typedefstruct{

intkey;

}Redtype;

typedefstruct{

Redtyper[MAXSIZE+1];

intlength;

}SqList;

voidShelllnsert(SqList&Q,intdk)〃希爾插入排序

{intij;

for(i=dk+1;i<=Q.length;i++)

if(Q.r[i].key<Q.r[i-dk].key){

Q.r[0]=Q.r[i];

for(j=i-dk;j>0&&(Q.r[0].key<Q.r[j].key);j-=dk)

Q.r[j+dk]=Q.r[j];

Q.r[j+dk]=Q.r[O];

)

for(inti=1;iv=Q」ength;i++){//一次希爾排序輸出

printf("%d",Q.r[i].key);

)

printf("\n");

)

voidShellsort(SqList&Q)〃希爾排序

{intdlta[10];

for(intk=5;k>0;k-=2){

Shelllnsert(Q,k)；

〃快速排序

intpartition(SqList&Q,intlow,inthigh){

Q.r[0]=Q.r[low];

intpivotkey;

pivotkey=Q.r[low].key;

while(low<high){

while(low<high&&Q,r[high].key>=pivotkey)-high;

Q.r[low]=Q.r[high];

while(low<high&&Q,r[low].key<=pivotkey)++low;

Q.r[high]=Q.r[low];

)

Q.r[low]=Q.r[0];

for(inti=1;i<=Q」ength;i++){〃一次快速排序輸出

printf("%d",Q.r[i].key);

)

printf("\n");

returnlow;

)

voidQSort(SqList&Q,intlowjnthigh){

if(low<high){

intpivotloc;

pivotloc=partition(Q,low,high);

QSort(Q,low,pivotloc-1);

QSort(Q,pivotloc+1,high);

)

)

voidQuickSort(SqList&Q){

QSort(Q,1,Q.length);

)

voidBubbleSort(SqList&Q)〃冒泡排序

{intx,m;

intflag=1;

m=Q.length-1;

while((m>0)&&(flag==1))

{flag=O;

for(intj=1;j<=m;j++)

if(Q.r[j].key>Q.r[j+1].key)

(

flag=1;

x=Q.r[j].key;

Q.r[j].key=Q.r[j+1].key;

Q.r[j+1].key=x;

)

for(inti=1;i<=Q.length;i++){〃一次冒泡排序輸出

printf("%d",Q.r[i].key);

)

printf("\n");

m-;

intmain()

{SqListQ,L,M;

printf