数据结构课程设计报告(各种排序实现及对比)

数据结构课程设计报告

设计题目：学生姓名：系 别：专 业：班 级：学 号：指导教师：

2010年版

目 录

一、设计题目……………………………………………………4

二、运行环境（软、硬件环境）………………………………4

三、算法设计的思想……………………………………………4

3.1简单选择排序………………………………………………4

3.2直接插入排序……………………………………………….4

3.3希尔排序……………………………………………………4

3.4冒泡排序……………………………………………………4

3.5快速排序……………………………………………………4

四、算法的流程图……………………………………………….5

4.1主函数的算法流程图………………………………………...5.

4.2简单选择排序的算法流程图………………………………….6

4.3直接插入排序的算法流程图………………………………….7

4.4希尔排序的算法流程图………………………………………8

4.5冒泡排序的算法流程图………………………………………9

4.6快速排序的算法流程图（1）………………………………..10

4.7快速排序的算法流程图（2）………………………………..11

五、算法设计分析………………………………………………11

5.1简单选择排序………………………………………………11

5.2直接插入排序……………………………………………….12

5.3希尔排序……………………………………………………12

5.4冒泡排序……………………………………………………13

5.5快速排序……………………………………………………13

六、源代码………………………………………………………14

七、运行结果分析………………………………………………23

八、收获及体会…………………………………………………26

2

一、

设计题目

各种排序

二、

运行环境（软、硬件环境）

软件环境: 操作系统的名称windows、版本号XP；

程序开发的环境: Microsoft Visual C++ 6.0

硬件环境：内存：512M，硬盘：80G

三、

算法设计的思想

3.1简单选择排序

<1> 基本思想

每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。

3.2插入排序

<1> 基本思想

插入排序的思想就是读一个，排一个，将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．

3.3希尔排序

<1> 基本思想

希尔排序法是1959年由提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组; 然后相隔2个成分,在按组排序......最后,对所有相邻成分进行排序.

3.4冒泡排序

<1> 基本思想

依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后...... 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.

3.5快速排序

<1> 基本思想

快速排序的基本思想是基于分治策略的。对于输入的子序列]，如果规模足够小则直接进行排序，否则分三步处理：

3

分解(Divide)：将输入的序列]划分成两个非空子序列L[p..q]和L[]，使L[p..q]中任一元素的值不大于L[]中任一元素的值。

递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[]进行排序。

合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[]都排好序后不需要执行任何计算]就已排好序。

四、

算法的流程图

4.1主函数的算法流程图

开始

输入数据个数length

create(),

visit()

输入select

7

select

0 1 2 3 4 5

ExitselectZhijiShelMao

(0) _sort(e(L) lSortpao(

L); () L);

输入y/n

n

y

结束

4

6

QuickSort(L);

select_sort(L);

Zhijie(L);

ShellSort(L,dlta,4);

Maopao(L);

QuickSort(L);

print(num);

4.2简单选择排序的算法流程图

开 始

int i=1;

假

i<

真

int j=i;

k=i+1

假

k<

真

L.r[j].key

.key

j=k;

k++

假

i!=j

真

L.r[i] L.r[j]

i++

结

5

束

4.3直接插入排序的算法流程图

开始

i=2

假

i<=

真

L.r[i].key

真

L.r[0]=L.r[i]；

L.r[i]=L.r[i-1]；

j=i-2；

假

假

L.r[0].key

真

L.r[j+1]=L.r[j]；

--j；

L.r[j+1]=L.r[0]

++i

结束

6

4.4希尔排序的算法流程图

开始

k=0

假

k

真

ShellInsert(&L,dlta[k],&r);

i=dk+1;

假

i<=

真

假

L.r[i].key

真

L.r[0]=L.r[i]；

j=i-dk；

j>0&&L.r[0].key

真

L.r[j+dk]=L.r[j]；

j-=dk；

假

L.r[j+dk]=L.r[0]

++i

++k

结束

7

4.5冒泡排序的算法流程图

开 始

int i=1;

i<

真

假

int j=1;

假

j<-i

真

L.r[j].key

真

假

L.r[j]

L.r[j+1]

j++

i++

结 束

8

4.6快速排序的算法流程图（1）

开始

L,low,high

L.r[0]=L.r[low]

Pivotkey=L.r[low].key

假

Low

L.r[high]=L.r[low]

真

结束

Low

&&L.r[high].key>=pivotkey

假

L.r[low]=L.r[high]

真

--high

Low

&&L.r[high].key<=pivotkey

假 真

++low

9

4.7快速排序的算法流程图（2）

开始

L，low，high

假

Low

L,low=pivotloc+1,high=high

真

Pivotloc=partioion(L,low,high),low=low,

high=pivotloc-1;

Low

真

Pivotloc=partioion(L,low,high),low=low,

high=pivotloc-1;

QSort(L,low,pivotloc-1)

假

结束

五、

算法设计分析

5.1简单选择排序

操作方法：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。

10

【效率分析】

空间效率：仅用了一个辅助单元。

时间效率：简单选择排序中，所需进行记录移动的操作次数较小，其最小值为0，最大值为3（n-1）。然而，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为n(n-1)/2。因此，总的时间复杂度也是O(n2)。

5.2直接插入排序

设有n个记录，存放在数组r中，重新安排记录在数组中的存放顺序，使得按关键码有序。即r[1].key≤r[2].key≤……≤r[n].key

先来看看向有序表中插入一个记录的方法：

设１<ｊ≤ｎ，r[1].key≤r[2].key≤……≤r[j-1].key，将r[j]插入，重新安排存放顺序，使得r[1].key≤r[2].key≤……≤r[j].key，得到新的有序表，记录数增１。

【效率分析】

空间效率：仅用了一个辅助单元。

时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。

最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。

总比较次数=n-1次

总移动次数=2(n-1)次

最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。

平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。

由此，直接插入排序的时间复杂度为O(n2)。是一个稳定的排序方法

5.3希尔排序(Shell’s Sort)

直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。

希尔排序方法：

1. 选择一个步长序列t1，t2，…，tk，其中ti>tj，tk=1；

2. 按步长序列个数k，对序列进行k趟排序；

3. 每趟排序，根据对应的步长ti，将待排序列分割成若干长度为

11

m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序列的方法。步长因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。

5.4冒泡排序

冒泡排序方法：对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]，如此重复，直到n个记录按关键码有序的表。

【效率分析】

空间效率：仅用了一个辅助单元。

时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。

移动次数：

最好情况下：待排序列已有序，不需移动。

5.5快速排序

快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。

【效率分析】

空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。

时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。

理想情况下：每次划分，正好将分成两个等长的子序列，则

T(n)≤cn+2T(n/2) c是一个常数

12

≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)

≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

······

≤cnlog2n+nT(1)=O(nlog2n)

最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

插入排序

交换排序

选择排序

排序方法

直接插入排序

希尔排序

冒泡排序

快速排序

最好时间

O(n)

O(n)

平均时间

O(n2)

O(n1.5)

O(n2)

最坏时间

O(n2)

O(n2)

稳定性

稳定

不稳定

稳定

不稳定

不稳定

O(nlogn) O(nlogn) O(n2)

直接选择排O(n2) O(n2) O(n2)

序

内部排序各种算法的性能比较(表)

六、

源代码

#include "stdlib.h"

#include"stdio.h"

#include"time.h"

#define MAXSIZE 200

typedef int KeyType;

typedef struct //定义存储记录关键字及其他信息的结构体

{ KeyType key;

char other;

}RedType;

typedef struct //定义存储所有记录的结构体

{ RedType r[MAXSIZE+1];

int length;

13

}SqList;

typedef struct{

int move; /*记录数据移动次数*/

int comp; /*记录数据比较次数*/

}Recode;

int dlta[5]={31,15,7,3,1}; //初始化希尔排序的增量序列

int num[10]={0}; //记录每个排序方法的移动次数和比较次数

int flag=0; //标记变量

//利用产生的随即数模拟用户输入的数据

void create(SqList *L,int length)

{ int i;

srand(time(0));

L->length=length;

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

{

L->r[i].key=rand()%1000;

L->r[i].other=rand()%26+65;

}

}

/*输出元素*/

void visit(SqList L)

{int i;

printf("n");

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

printf("%4d%2c",L.r[i].key,L.r[i].other);

printf("n");

}

/*简单选择排序*/

void select_sort(SqList L)

{ Recode r;

=0;

=0;

int i,j,k;

RedType t;

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

{ j=i;

for (k=i+1;k<=;k++)

14

{ ++;

if (L.r[j].key>L.r[k].key)

{

j=k;

}

}

if (i!=j)

{

t=L.r[j];

L.r[j]=L.r[i];

L.r[i]=t;

= +3;

}

}

if(!flag)

{ printf("本次随机数据排序的移动次数为:");

printf("%dn",);

printf("本次随机数据排序的比较次数为:");

printf("%dn",);

printf("简单选择排序后的结果：");

visit(L);

}

else{num[0]=;num[1]=;}

}

//直接插入排序

void Zhijie(SqList L)

{ Recode r;

=0;

=0;

int j;

for(int i=2;i<=;++i)

{ ++;

if(L.r[i].key

{

L.r[0]=L.r[i]; //复制为哨兵

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

= +2;

15

for(j=i-2;L.r[0].key < L.r[j].key;--j)

{

L.r[j+1]=L.r[j]; //记录后移

++;

++;

}

L.r[j+1]=L.r[0]; //插入到正确位置

++;

}

}

if(!flag)

{

printf("本次随机数据排序的移动次数为:");

printf("%dn",);

printf("本次随机数据排序的比较次数为:");

printf("%dn",);

printf("直接插入排序后的结果：");

visit(L);

}

else{num[2]=;num[3]=;}

}

//希尔排序

void ShellInsert(SqList *L,int dk,Recode *r)

{ int i,j;

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

{ r->comp ++;

if(L->r[i].keyr[i-1].key)

{ L->r[0]=L->r[i]; //暂存

r->move ++;

for(j=i-dk;j>0&&(L->r[0].key < L->r[j].key);j-=dk)

{ L->r[j+dk]=L->r[j]; //记录后移

r->move ++;

r->comp ++;

}

L->r[j+dk]=L->r[0]; //插入到正确位置

r->move ++;

}

16

}

}

void ShellSort(SqList L,int dlta[],int t)

{ //按增量序列-1]对顺序表L作希尔排序。

Recode r;

=0;

=0;

int k;

for(k=0;k

ShellInsert(&L,dlta[k],&r);//一趟增量为dlta[k]的插入排序

if(!flag)

{ printf("本次随机数据排序的移动次数为:");

printf("%dn",);

printf("本次随机数据排序的比较次数为:");

printf("%dn",);

printf("希尔排序后的结果：");

visit(L);

}

else{num[4]=;num[5]=;}

}

//冒泡排序法

void Maopao(SqList L)

{ Recode r;

=0;

=0;

int i,j;

RedType t;

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

for(j=1;j<=-i;j++)

{ ++;

if(L.r[j].key>L.r[j+1].key)

{ = +3;

t=L.r[j];

L.r[j]=L.r[j+1];

L.r[j+1]=t;

}

}

17

if(!flag)

{

printf("本次随机数据排序的移动次数为:");

printf("%dn",);

printf("本次随机数据排序的比较次数为:");

printf("%dn",);

printf("冒泡排序后的结果：");

visit(L);

}

else{num[6]=;num[7]=;}

}

//快速排序法

int Partition(SqList *L,int low,int high,Recode *r)

{

int pivotkey;

L->r[0]=L->r[low]; //用子表的第一个记录作枢轴记录

pivotkey=L->r[low].key; //枢轴记录关键字

r->move =r->move +2;

while(low

{

while(lowr[high].key >=pivotkey){ --high;

r->comp ++;}

L->r[low]=L->r[high]; //将比枢轴记录小的记录移到低端

while(lowr[low].key <=pivotkey) {++low;

r->comp++;}

L->r[high]=L->r[low]; //将比枢轴记录大的记录移到高端

r->move =r->move+2;

}

L->r [low]=L->r [0]; //枢轴记录到位

r->move ++;

return low; //返回枢轴位置

}

void QSort(SqList *L,int low,int high,Recode *r)

{ int pivotloc;

if(low

{ pivotloc=Partition(L,low,high,r); //将L->r[low..high]一分为二

18

QSort(L,low,pivotloc-1,r); /对低子表递归排序，pivotloc是枢轴位置

QSort(L,pivotloc+1,high,r); //对高子表递归排序

}

}

void QuickSort(SqList L)

{ Recode r;

=0;

=0;

QSort(&L,1,,&r);

if(!flag)

{ printf("本次随机数据排序的移动次数为:");

printf("%dn",);

printf("本次随机数据排序的比较次数为:");

printf("%dn",);

printf("快速排序后的结果：");

visit(L);

}

else{num[8]=;num[9]=;}

}

void print(int num[]) //打印排序方法比较表

{ int k=0;

printf("nnnt________________________________________________________________n");

printf("t|排序方法 | 关键字移动次数 |关键字比较次数 |n");

printf("t________________________________________________________________n");

printf("t|选择排序 | %5d

| %5d n",num[0],num[1]);

printf("t|直接插入排序 | %5d

| %5d n",num[2],num[3]);

printf("t|希尔排序 | %5d

| %5d n",num[4],num[5]);

printf("t|冒泡排序 | %5d

19

| %5d n",num[6],num[7]);

printf("t|快速排序 | %5d

| %5d n",num[8],num[9]);

printf("t_________________________________________________________________n");

printf("ntt ★★★★★★★★★★★★★★★★★★★★★n");

printf("tt ★

★n");

printf("tt ★ 本组数据排序方法比较表

★n");

printf("tt ★

★n");

printf("tt ★★★★★★★★★★★★★★★★★★★★★n");

}

void main()

{

char c;

int select,length;

SqList L;

do

{

printf("请输入需排序的数据个数(小于200)：n");

scanf("%d",&length);

create(&L,length);

printf("产生的随机序列为：n");

visit(L);

do

{

printf("nn ****************** 欢迎进入排序系统 *******************n ");

printf(" ★ 1 选择排序 2.直接插入排序 3.希尔排序 4.冒泡排序 ★n ");

printf(" ★ 5 快速排序 6.比较以上排序 7.更改数据 0.退出 ★n ");

20

printf(" Please input number（0-7）n");

scanf("%d",&select);

switch (select)

{

case 0:exit(0);

case 1:

select_sort(L); //选择排序

break;

case 2:

Zhijie(L); //直接插入排序

break;

case 3:

ShellSort(L,dlta,5); //希尔排序

break;

case 4:

Maopao(L); //冒泡排序

break;

case 5:

QuickSort(L); //快速排序

break;

case 6: //比较以上排序

flag=1;

select_sort(L);

Zhijie(L);

ShellSort(L,dlta,4);

Maopao(L);

QuickSort(L);

print(num);

flag=0;

break;

case 7: //更改数据

break;

default:printf("输入错误！请重新输入....n"); break;

}

if(select==7) break;

}while(1);

printf("是否更换数据重新进行排序？(y/n)");

21

getchar();

c=getchar();

if(c=='n'||c=='N')

break;

system("cls");

}while(1);

}

七、

运行结果分析

7.1开始运行时截图

7.2主界面截图

7.3选择排序截图

7.4直接插入排序截图

22

7.5希尔排序截图

7.6冒泡排序截图

7.6快速排序截图

23

7.7比较以上排序截图

7.8排序个数取900比较以上排序截图

分析： 由以上运行结果可以看出排序算法的稳定性和其时间复杂度。例如，在选择排序中当关键字为99时，存在两个此信息，一个为A，另一个为F，排序前F在A的前面，排序后F在A的后面，故可知选择排序为不稳定的排序。由以上运行结果可分析出稳定排序有直接插入排序和冒泡排序，不稳定排序有选择排序，希尔排序和快速排序。

由排序方法的比较表可知插入、冒泡排序的速度较慢。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。

24

通过比较他们在不同场合的时间复杂度，得知没有哪一种排序方法是绝对最优的。有的适用于N较大的情况，有的适用于N较小的情况，因此，在实用时需根据不同情况适当选用，甚至可将多种方法结合起来使用。

八、

收获及体会

通过这次课程设计作业我着实感受了一次编程的乐趣，从中也学到了不少知识。

虽然都说“程序＝数据结构＋算法”，但我们在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。

我们感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。我们还体会到深刻理解数据结构的重要性。只有真正理解定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。这次实验中我们也出现过一些错误。但我们经过反复调试后，发现并做了修改，从而完成了此次课程设计。

在这次的数据结构课程设计中，我此次的题目是各种排序，排序实际上是编程设计中应用比较广泛的知识，通过本次设计，我对一些基本的内部排序有了很好的理解和掌握，并且通过此次课程设计中的程序运行结果很好的理解了排序各种算法的稳定性和时间复杂度，既巩固了课堂上学到的排序理论，又为自己的编程增强了实践。总之，在这次的数据结构课程设计中，收获还是蛮多的。也让自己对数据结构这门课程有了更好的认识，相信在越来越多的尝试之后，自己会不断进步不断提高的。

25