數據結構 內部排序實驗

數據結構與算法課程實驗報告

實驗六：排序實踐

姓名：沈靖雯

班級：14信科二班

學號：2022326601094

實驗六排序實踐

【實驗內容】

實現各排序算法并進行性能比較

【實驗目的】

掌握各排序算法的實現方法，并分析各排序算法的時間和空間性能。

【問題描述】

實現各排序算法，必須實現希爾排序和快速排序算法，其他排序算法選做，

并分析各算法的性能。

【問題實現】

(1)數據結構類

#defineMAXSIZE20

typedefstruct{

intkey;

)Redtype;

typedefstruct{

Redtyper[MAXSIZE+l];

intlength;

}SqList;

(2)主要算法函數：

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");

}

完整實現序列的希爾排序代碼如下，其中增量序列簡化為例題所用序列5,3,1：

voidShellsort(SqList&Q)〃希爾排序

{intdlta[10];

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

She川nsert(Qk);

}

)

2).快速排序；

快速排序是對起泡排序的一種改進。下面是一次快速排序的函數代碼，

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

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;

)

遞歸法完整實現序列的快速排序，每次將序列以軸樞為界分為兩部份

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

進行快速排序……以此類推直至序列全部排序完成：

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).起泡排序；

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

【總結】

希爾排序：將序列分組為子序列分別進行直接插入排序，關鍵字較小的記錄

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

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

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

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

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

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

i=n

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

快速排序：作為起泡排序的改進，平均時間為T⑻;由的，k為某個常

avg

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

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

時間復雜度為。(小)。快速排序空間復雜度O(nlogn)。

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

排序較好。

程序運行截圖:

圖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