数据结构-实验9各种排序算法

发布时间 : 2024/4/25 20:43:56 星期四 文章数据结构-实验9各种排序算法更新完毕开始阅读

9.1 实现希尔排序算法

一， 实验目的

1.熟悉掌握各种排序算法，深刻理解各种排序算法及其执行的过程； 2.学会分析各种排序算法的过程和性能。

二， 实验内容

9.1 实现希尔排序算法

编写一个程序实现希尔排序，dk={5,3,1}，并输出{6,9,7,8,0,1,3,2,4,5}的排序过程。

9.2 实现快速排序算法

编写一个程序实现快速排序，并输出{49,38,65,97,76,13,27,49}的排序过程（要求输出每次枢轴记录到位后的关键字序列）。 9.3 实现堆排序算法

编写一个程序实现堆排序，并输出{49,38,65,97,76,13,27,49}的排序过程（要求输出初始堆、第一个记录与堆尾交换后、重新调整成堆，直至排好序后的关键字序列）。

三， 源代码及结果截图

9.1

//9.1 实现希尔排序算法 #include using namespace std; #define MAX 10

void ShellSorts(int sorts[],int dk) //一次希尔排序 {

int temp,j,i;

cout<<\希尔排序过程：\

for(i=dk;i

if(sorts[i-dk]>sorts[i]) {

temp=sorts[i]; sorts[i]=sorts[i-dk];

for(j=i-dk;j>=0&&sorts[j]>temp;j-=dk)

sorts[j+dk]=sorts[j]; sorts[j+dk]=temp; } } for(i=0;i

cout<

cout<

int dlta[]={5,3,1}; //希尔排序的DK void SHELL(int sorts[],int dk[]) //希尔排序 {

for(int k=0;k<3;k++) ShellSorts(sorts,dlta[k]); }

void ShowSorts(int a[]) //显示排序后的结果 {

int i=0;

for(i;i

void main() {

int S[MAX]={6,9,7,8,0,1,3,2,4,5}; // //int JG[MAX]={0,1,2,3,4,5,6,7,8,9}; //便自己看的 int j=0;

cout<<\待排序数组: \

for(j;j

待排序数组 正确排序结果，方

cout<

SHELL(S,dlta); //希尔排序 cout<<\希尔排序后的结果: \

ShowSorts(S); //显示拍完序后的数组 }

9.2

//9.2 实现快速排序算法 #include #define MAXE 20 typedef int KeyType; typedef char InfoType[8]; typedef struct //记录类型 {

KeyType key;

//关键字项

//线性表中最多元素个数

InfoType data; }RedType;

//其他数据项,类型为InfoType

void QuickSort(RedType R[],int l,int h) //对R[s]至R[t]的元素进行快速排序 {

int i=l,j=h,k; RedType temp; if (l

temp=R[l];

//用区间的第个记录作为基准

//区间内至少存在一个元素的情况

while (i!=j)

{

//从区间两端交替向中间扫描,直至i=j为止

while (j>i && R[j].key>temp.key) j--;

//从右向左扫描,找第个关键字小于temp.key的R[j] /*表示找到这样的R[j],R[i]、R[j]交换*/

if (i

{ }

R[i]=R[j]; i++;

while (i

i++;

//从左向右扫描,找第个关键字大于temp.key的记录

R[i]

if (i

//表示找到这样的R[i],R[i]、R[j]交换/