数据结构 内部排序实验

数据结构与算法课程实验报告

实验六：排序实践

姓名：沈靖雯

班级：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