2023年数据结构实验报告实现典型的排序算法

佛山科学技术学院

实验报告

课程名称数据结构

实验项目实现典型的排序算法

专业班级10网络工程2姓名张珂卿学号—

指导教师成绩日期20

23.11.27

一、实验目的

1.掌握排序的基本概念；

2.熟悉排序中使用的存储结构,掌握多种排序算法，如堆排序、希尔排序、快速排序算法

等。

二、实验内容

1.几种典型的排序算法；

2.计算不同的排序算法的时间复杂度；

3.鉴定某种排序算法是否稳定的标准。

三、实验原理

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有

序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完毕，则称

此类排序问题为内部排序。反之，若参与排序的记录数量很大，整个序列的排序过程不也许

在内存中完毕,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序

序列长度的过程。

四、实验环节

1.输入记录的基本结点与信息，选用相关的存储结构，完毕记录的存储、输入的初始化工

作。

2.选择“直接插入排序”，“希尔排序”，“快速排序”，“简朴选择排序”和“堆排序”几种

排序中的任意三种排序，编程实现排序算法。用菜单形式选择排序方法，并显示排序过程和

排序结果。

3.计算排序算法的时间复杂度并进行稳定性分析。

五、程序源代码及注释

#inc1ude“iostream”

usingnamespacestd；

#defineMAX_N0_0F_KEY8

#defineRADIX10〃关键字基数

#defineMAX_SPACE1000

typedefstruct

{

。intkeys[MAX_N0_0F_KEY];〃关键字

intdata;〃其他数据项

3intnext;

)SLCe11;

typedefstruet

(

oSLCe11r[MAX_SPACE];//静态链表可运用空间

intkeynum;//记录的当前关键字个数

intreenum;〃静态链表的当前长度

}SLList;

typedefintArrType[RADIX];〃指针数组类型

int1en;//数组长度

//插入排序

voidDirectlnsertSort(intElemArr口)

(

inti,j;

ofor(i=2;i<len;i++)

(

»Elem_Arr[0]=Elem_Arr[i];

for(j=i-l；j>=1；j­)

ooif(Elem_Arr[0]<E1em_Arr[j])

®Elem_Arr[j+1]=E1em_Arr[j];

»e1se

«~break;

«Elem_Arr[j+l]=E1em_Arr[0];

)

)

//希尔排序

voidShe11Insert(intElem_Arr[],intadd)//add为某趟希尔排序的

增量

(

inti,j;

ofor(i=add+1;i<len;i++)

。{

sElem_Arr[0]=Elem_Arr[i];

«>for(j=i-add;j>O&&Elem_Arr[j]>E1em_Arr[0];j-=add)

gE1em_Arr[j+add]=Elem_Arr[j];

Elem_Arr[j+add]=Elem_Arr[0]；

)

)

voidShe1ISort(intElem_Arr[])

(

ointt;

youtV<〃请输入增量数组元素个数:end1;

空in>〉t;

int*dlta=newint[t]；

〃请依次输入增量数组元素：〃〈Vendl;

«>for(inti=0；i<t；i++)

cin»dlta[i];

®for(intk=O;k〈t;++k)

She11Insert(Elem_Arr,dlta[k])；〃一趟增量为dlta[k]的插入排序

}

〃快速排序

intPartition(intElem_Arr[],inti,intj)//实现一分为二，pivotkey为枢

轴变量

{

bintpivotkey；

叩ivotkey=Elem_Arr[i];

while(i<j)

awhile(i<j&&Elem—Arr[j]>=pivotkey)

3Lj；

E1em_Arr[i]=E1em_Arr[j]；

while(i<j&&E1em_Arr[i]<=pivotkey)

©++i；

»Elem_Arr[j]=E1em_Arr[i];

。}

«>Elem_Arr[i]=pivotkey;

oreturni;

}//Partition

voidQSort(intElem_Arr[],intlow,inthigh)

(

intpivot1oc;

eif(low<high)

gpivot1oc=Partition(Elem_Arr,low,high)

oQSort(E1em_Arr,1ow,pivotloc-1);

oQSort(Elem_Arr,pivotloc+1,high)；

voidQuickSort(intElem_Arr口)

(

oQSort(Elem_Arr,1,1en-l);

}

//简朴选择排序

intSe1ectMin(intElem_Arr[],inti)

(

ointmin=i;

ofor(intj=i+1;j<len;j++)

oif(E1em_Arr[min]>Elem_Arr[j])

8min=j;

»returnmin;

}

voidSe1ectSort(intElem_Arr[])

(

intt,j;

for(inti=1;i<len;++i)

j=SelectMin(Elem_Arr,i);

f(i!=j)

(

8t二Elem_Arr[i];

1em_Arr[i]=E1em_Arr[j];

3Elem_Arr[j]=t;

)

)

}//Se1ectSort

//堆排序

voidHeapAdjust(intElem_Arr[],inti,intm)

(

<>E1em_Arr[0]=Elem_Arr[i];

for(intj=2*i;j<=m;j*=2)

gif(j<m&&E1em_Arr[j]<Elem_Arr[j+1])

8++j；

»if(Elem_Arr[0]>Elem_Arr[j])

gbreak；

®Elem_ArrLi]=Elem_Arr[j];

3i=j；

)

«>E1em_Arr[i]=ElemArr[0];

)

voidHeapSort(intE1em_Arr[])

(

for(inti=(len-l)/2;i>0;--i)

«>HeapAdjust(ElemArr,i,len-1);

for(i=len-1;i>l；一一i)

(

«>E1emArr[0]=Elem_ArrEi];

ElemArr[i]=E1em_Arr[1];

1em_Arr[l]=Elem_Arr[0];

«>HeapAdjust(Elem—Arr,1,i—1)；

)

)

〃归并排序

voidMerge(intE1em_Arrl口,intElem_Arr[],inti,intm,intn)//

将有序的SR[i♦和SR[m+L.n]归并为有序的TR[i♦.n]

{

ointj,k;

«>for(j=m+l,k=i;i<=m&&j<=n;++k)

d(

“/将SR中记录由小到大地并入TR

gif(Elem_Arrl[i]<ElemArr1[j])

Elem_Arr[k]=Elem_Arrl[i++]；

«>else

gElem_Arr[k]=Elem_Arrl[j++];

if(i<=m)//TR[k..n]=SR[i..m];将剩余的SR[i..m]复制到TR

awhile(k<=n&&i<=m)

gE1em_Arr[k++]=Elem_ArrlLi++]；

8if(j<=n)〃将剩余的SR[j..n]复制到TR

owhile(k<=n&&j<=n)

3Elem_Arr[k++]=E1em_Arr1[j++];

)

voidMSort(intElem_Arrl[],intElem_Arr[],ints,intt)〃将SR[s..t]归并

排序为TRl[s..t]

{

intm；

intTR2[20];

if(s==t)

Elem_Arr[t]=Elem_Arrl[s];

比1se

(

om=(s+t)/2;〃将SR[s..t]平分为SR[s..m]和SR[m+l..t]

oMSort(E1em_Arrl,TR2,s,m);〃递归地将SR[s..m]归并为有序的TR2

[s..m]

。MSort(Elem_Arrl,TR2,m+1,t);〃将SR[m+l..t]归并为有序的TR2[m+

1..t]

oMerge(TR2,Elem_Arr,s,m,t);//将TR2[s..m]和TR2[m+L.t]归并到

TRl[s..t]

voidMergeSort(intE1em_Arr[])〃对顺序表L作归并排序。

(

int*E1em_Arrl=newint[1en]；

for(inti=0;i<len；i++)

«>Elem_Arrl[i]=E1em_Arr[i];

MSort(E1em_Arr1,Elem_Arr,1,len—1);

}

//基数排序

intsucc(intf[],intj)

(

intk=j;

for(j;j<10；j++)

if(f[j]!=0)break；

elsek++;

«>if(j<10)returnk;

eIsereturn0；

)

voidCreateL(SLList&L)

(

cout<<”请依次输入元素:“<Vend1;

ofor(inti=1;i〈=L.recnum;i++)

{

ocin>>L.r[i].data;

oL.r[i].keys[0]=L.r[i].data%10；

3L.r[i].keysE1]=(L.rLi].data%100-L.rLi].keys[0])/10;

«>L.r[i].keys[2]=L.r[i].data/100;

}

voidDistribute(SLList&L,inti,ArrType&f,ArrType&e)

(

//算法10.15

“/静态链表L的r域中记录已按(keys[0],keys[i-1])有序，

。//本算法按第i个关键字keys[i]建立RADIX个子表，

//使同一子表中记录的keys]i]相同。f[0..RADIXT]和e[0..RADIX-1j

“/分别指向各子表中第一个和最后一个记录。

intj,p；

for(j=0;j<RADIX;++j)

»(

°f[j]=0；

«e[j]=0；

)//各子表初始化为空表

»for(p=L.r[0].next;p!=0；p=L.r[p].next)

»(

d=L.r[p].keysLi]://将记录中第i个关键字映射到[0..RADIX-1],

°if(fEj]==O)

°f=P；

oe1se

°L.r[e[j]].next=p;

e[j]=p;//将p所指的结点插入第j个子表中

}IIDistribute

voidPrint_SLList(SLListL,inti)

(

»for(intp=L.r[0].next;p!=0；p=L.r[p],next)

ocout«L.r[p].data«z/

}

voidCollect(SLList&L,ArrTypef,ArrTypee)

(

。//本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成

//一个链表，e[0..RADIX-1]为各子表的尾指针

intt,j=0;

j=succ(f,j)；

L.r[0].next=fEj];//L.r[0].next指向第一个非空子表中第一个结点

t=e[j];

j++；

j=succ(f,j);

while(j!=O&&f[j]!=0)

{//找下一个非空子表//链接两个非空子表

L.r[t].next=f[j];

t=eEj];j++;

j=succ(f,j)；

if(succ(f,j)==0)

sbreak；

)

L.r[t].next=0；//t指向最后一个非空子表中的最后一个结点

}

voidRadixSort(SLList&L)

(

“/L是采用静态链表表达的顺序表。对L作基数排序，使得L成为按关键字自小到大的

有序静态链表，L.r[0]为头结点。

inti;

oArrTypef,e;

»L.keynum=3;

cout请输入所需排序元素个数(当前记录关键字个数<==3)：〃<Vendl；

cin>>L.recnum；

»CreateL(L);

»for(i=l;i<=Lrecnum;++i)

L.r[i-1].next=i;

L.r[L.recnumJ.next=0;//将L改造为静态链表

for(i=0;i<Lkeynum;++i)//按最低位优先依次对各关键字进行分派和收集

(

Distribute(L,i,f,e);//第i趟分派

。Co1lect(L,f,e)；〃第i趟收集

b}d

cout〈V”基数排序结果为："<<endl;

Print_SLList(L,i)；

)

voidCreatElemArr(intElem_Arr[])

(

ocout<〈”请依次输入元素："<<endl；

for(inti=l；i<len;i++)

cin»Elem_Arr[i]；

}

voidShowElem_Arr(intElem_Arr[])

(

for(inti=1;i<len；i++)

»cout«Elem_Arr

}

voidoperate(intElem_Arr[])

(

»inta,b,c;

cout<V”直接排序请输入数字l”〈<end1;

»cout«"希尔排序请输入数字2"V〈endl;

。cout<<"快速排序请输入数字3z/«end1;

ocout<<H-----------------------------------〃V<end1;

yin>>a；

dif(a==l)

{

gintNO；

«>coutVV”请输入需要排序元素个数：〃〈〈endl；

oi>cin>>N0;

<>len=N0+1;

凸E1em_Arr=newint[1en]；

CreatE1em_Arr(Elem_Arr);

«>DirectlnsertSort(E1em_Arr);

youtV〈”直接排序结果为:〃V<endl;

3showElem_Arr(E1em_Arr);

比Iseif(a==2)

(

«>intNO;

yout<<〃请输入需要排序元素个数：〃<Vendl；

cin»NO;

glen=NO+1;

oElem_Arr=newint[len];

«CreatElem_Arr(Elem_Arr)；

8she11Sort(E1em_Arr);

oocout<<H希尔排序结果为:〃〈〈end1；

«>ShowE1em_Arr(Elem_Arr)；

。}

elseif(a==3)

(

intNO;

。cou〃请输入需要排序元素个数：〃。endl;

cin>>NO;

^len=NO+l;

oElem_Arr=newint[len];

CreatElem_Arr(Elem_Arr);

QuickSort(Elem_Arr);

cout<<〃快速排序结果为：〃<Xend1;

oShowE1em_Arr(EIem_Arr);

9

oe1seif(a==4)

£

~>intNO;

^cout<<”请输入需要排序元素个数：M<<endl;

gcin>>NO;

en=N0+l;

«>Elem_Arr=newint[len];

★reatElemArr(ElemArr);

®Se1ectSort(Elem_Arr);

cout<〈〃简朴选择排序结果为：〃<<end1;

<>ShowE1em_Arr(Elem—Arr);

elseif(a==5)

°{

gintNO;

Cout。〃请输入需要排序元素个数：”〈Vend1;

3cin>>NO;

1en=N0+l;

oE1em_Arr=newint[1en];

ooCreatElem_Arr(E1emArr);

HeapSort(Elem_Arr);

。cout<<〃堆排序结果为:〃<<endl;

ShowElem_Arr(Elem_Arr);

9

elseif(a==6)

。(

ointNO;

叱out。〃请输入需要排序元素个数：〃<<endl;

枳in>>N0;

«>len=NO+l；

«>Elem_Arr=newintElen]；

。CreatE1em_Arr(E1em_Arr);

MergeSort(Elem_Arr)；

oocout。"归并排序结果为："<<endl;

3ShowElem_Arr(Elem_Arr);

}

eeIseif(a==7)

(

SLListL;

bRadixSort(L)；

e1secout<<〃输入错误！M«end1;

cout<<n-----------------------------------------------------------------

---------------〃<<end1;

空out。〃操作完毕，请输入“1”返回主菜单，否则请按其他任意键退出！〃“endl；

COUt<<Z，-------------------------