快速排序和堆排序

题目：编程分别实现快速排序算法、堆排序算法

题目：编程分别实现快速排序算法、堆排序算法。

一、 需求分析

1. 用户可以根据自己的需求输入一个顺序表。

2. 通过利用快速排序法按非递减排序已有的顺序表。

3. 通过利用堆排序按非递减排序已有的顺序表。

4. 程序执行的命令包括：

（1）创建顺序表 （2）输出顺序表 （3）快速排序算法排序 （4） 堆排序算法排序

二、概要设计

⒈ 为实现上述算法，需要顺序表的抽象数据类型：

ADT sqlist {

数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可

唯一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P:

Creatsqlist(&l)

操作结果：构造一个具有n个数据元素的顺序表l。

ListLength(L)

初始条件：线性表L已经存在

操作结果：返回L中数据元素的个数。

destroylist(&l)

初始条件：顺序表l存在。

操作结果：销毁顺序表l。

displaylist（l）

初始条件：顺序表l存在。

操作结果：显示顺序表l。

quicksort (&l)

初始条件：顺序表l存在。

操作结果：通过快速排序得到一个有序的顺序表l。

heapsort (&l)

初始条件：顺序表l存在。

操作结果：通过堆排序得到一个有序的顺序表l。

heapadjust (&l，s，m)

初始条件：顺序表l存在。

操作结果：调整h->r[s]的关键字，使h->r[s]成为一个大顶堆

partion (&l，&low，high)

初始条件：顺序表l存在。

题目：编程分别实现快速排序算法、堆排序算法

操作结果：交换顺序表中子表r[low...high]的记录，使枢轴记录到

位，并返回其所在的位置。

}ADT sqlist

2. 本程序有三个模块：

⑴ 主程序模块

main(){

初始化；

{

接受命令；

显示结果；

｝

｝

⑵ 创建顺序表的模块：主要建立一个顺序表；

⑶快速排序模块：得到一个有序的顺序表；

(4)输出顺序表模块：显示已创建顺序表；

（5）堆排序模块：得到一个有序的顺序表。

三、详细设计

⒈元素类型，结点类型

typedef struct

{

int key;

}keytype;

typedef struct

{ keytype r[100];

int length;

}sqlist;

2.对抽象数据类型中的部分基本操作的伪码算法如下：

/*创建顺序表*/

void creat(sqlist *l)

{

int i,key;

printf("please intput it's length:");

scanf("%d",&l->length);

printf("\n\nplease intput %d data\n",l->length);

for(i=1;i<=l->length;i++)

{

scanf("%d",&key);

l->r[i].key=key;

}

}

/*交换顺序表中子表r[low...high]的记录，使枢轴记录到位，并返回其所在的位置*/ int partion(sqlist *l,int low,int high)

题目：编程分别实现快速排序算法、堆排序算法

{ int pivotkey;

l->r[0]=l->r[low];

pivotkey=l->r[low].key;

while(low<high)

{ while(low<high&&l->r[high].key>=pivotkey)

--high;

l->r[low]=l->r[high];

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

++low;

l->r[high]=l->r[low];

}

l->r[low]=l->r[0];

return low;

}

/*快速排序*/

void Qsort(sqlist *l,int low,int high)

{ int pivotloc;

if(low<high)

{ pivotloc=partion(l,low,high);

Qsort(l,low,pivotloc-1);

Qsort(l,pivotloc+1,high);

}

}

/*快速排序*/

void quicksort(sqlist *l)

{

Qsort(l,1,l->length);

}

/*显示顺序表*/

void display(sqlist *l)

{ int i;

for(i=1;i<=l->length;i++)

printf("%-4.2d",i);

printf("\n");

for(i=1;i<=2*l->length;i++)

printf("--");

printf("\n");

for(i=1;i<=l->length;i++)

题目：编程分别实现快速排序算法、堆排序算法

printf("%-4.2d",l->r[i].key);

}

/*调整h->r[s]的关键字，使h->r[s]成为一个大顶堆*/

void heapadjust(sqlist *h,int s,int m)

{ keytype rc;

int j;

rc=h->r[s];

for(j=2*s;j<=m;j*=2)

{ if(j<m&&h->r[j].key<h->r[j+1].key)

++j;

if(rc.key>=h->r[j].key) break;

h->r[s]=h->r[j];

s=j;

}

h->r[s]=rc;

}

/*对顺序表h进行堆排序*/

void heapsort(sqlist *h)

{ keytype rc;int i;

for(i=h->length/2;i>0;--i)

heapadjust(h,i,h->length);

for(i=h->length;i>1;--i)

{ rc=h->r[1];

h->r[1]=h->r[i];

h->r[i]=rc;

heapadjust(h,1,i-1);

}

}

3.主函数和其他函数的伪码算法

/*主函数*/

void main()

{ sqlist t;int i;

creat(&t);

Qsort(&t,1,t.length);

printf("\n\n");

printf("quicksort means:\n");

display(&t);

heapsort(&t);

题目：编程分别实现快速排序算法、堆排序算法

printf("\n");

printf("\nheapsort means:\n");

display(&t);

getch();

}

4 函数调用关系

heapadjust partion

四、调试分析

⒈开始的时候在编写快速排序算法的时候没有设置用子表的第一个记录作枢轴记录导致没

有得到正确的结果。

⒉在l->r[low]=l->r[high];语句进行交换时，写成l->r[low].key=l->r[high].key，一直

没有找到错误的地方，在看了参考资料后才发现是这里错了。

3. 算法的时空分析

各操作的算法时间复杂度比较合理

creat， partion，display为O(n) Qsort ，heapadjust，heapsort为 O(nlogn)

注：n为哈希表的长度。

5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使

调试也较顺利，各模块有较好的可重用性。

五、用户手册

⒈ 本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp10.c；

2. 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS

环境中，用户根据需求键入相应的数据，可以看到相应的结果。

六、测试结果

在dos下输入数据元素：

98 23 10 56 21 23 01 64 74 34

排序后的结果是：

01 10 21 23 23 34 56 64 74 98

则在dos界面输入如图所示：

题目：编程分别实现快速排序算法、堆排序算法

七、附录：源程序

#include<stdio.h>

typedef struct

{

int key;

}keytype;

typedef struct

{ keytype r[100];

int length;

}sqlist;

/*创建顺序表*/

void creat(sqlist *l)

{

int i,key;

printf("please intput it's length:");

scanf("%d",&l->length);

printf("\n\nplease intput %d data\n",l->length);

for(i=1;i<=l->length;i++)

{

scanf("%d",&key);

l->r[i].key=key;

}

}

/*交换顺序表中子表r[low...high]的记录，使枢轴记录到位，并返回其所在的位置*/ int partion(sqlist *l,int low,int high)

{ int pivotkey;

l->r[0]=l->r[low];

pivotkey=l->r[low].key;

while(low<high)

{ while(low<high&&l->r[high].key>=pivotkey)

题目：编程分别实现快速排序算法、堆排序算法

--high;

l->r[low]=l->r[high];

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

l->r[high]=l->r[low];

}

l->r[low]=l->r[0];

return low;

}

/*快速排序*/

void Qsort(sqlist *l,int low,int high)

{ int pivotloc;

if(low<high)

{ pivotloc=partion(l,low,high);

Qsort(l,low,pivotloc-1);

Qsort(l,pivotloc+1,high);

}

}

/*显示顺序表*/

void display(sqlist *l)

{ int i;

for(i=1;i<=l->length;i++)

printf("%-4.2d",i);

printf("\n");

for(i=1;i<=2*l->length;i++)

printf("--");

printf("\n");

for(i=1;i<=l->length;i++)

printf("%-4.2d",l->r[i].key);

}

/*调整h->r[s]的关键字，使h->r[s]成为一个大顶堆*/ void heapadjust(sqlist *h,int s,int m)

{ keytype rc;

int j;

rc=h->r[s];

for(j=2*s;j<=m;j*=2)

{ if(j<m&&h->r[j].key<h->r[j+1].key) ++j;

if(rc.key>=h->r[j].key) break;

h->r[s]=h->r[j];

s=j;

}

h->r[s]=rc;

}

题目：编程分别实现快速排序算法、堆排序算法

/*对顺序表h进行堆排序*/

void heapsort(sqlist *h)

{ keytype rc;int i;

for(i=h->length/2;i>0;--i) heapadjust(h,i,h->length); for(i=h->length;i>1;--i) { rc=h->r[1];

h->r[1]=h->r[i];

h->r[i]=rc;

heapadjust(h,1,i-1); }

}

/*主函数*/

void main()

{ sqlist t;int i;

creat(&t);

Qsort(&t,1,t.length);

printf("\n\n");

printf("quicksort means:\n"); display(&t);

heapsort(&t);

printf("\n");

printf("\nheapsort means:\n"); display(&t);

getch();

}

本文来源：https://www.bwwdw.com/article/3kui.html