数据结构课程设计-排序.doc

五.综合排序1、 设计目的对于数据处理工作，排序是其最基本的运算之一。在当今的计算机系统中，花费在排序上的时间占系统cpu运行时间的很大比重（约20%60%）。为了提高计算机的工作效率，人们提出了各种各样的排序算法，这些算法充分地展示了算法设计的某些重要原则和高超技巧。本设计旨在对一些常用的内部排序算法作深入地探讨和理解，通过比较，评价各算法的优劣。 2、 问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 3、 设计要求 (1) 实现基本排序方法：直接插入排序、希尔排序、冒泡、快速排序、直接选择、堆排序；（我们要求至少实现三种算法）(2) 对每种基本排序方法尽量给出改进算法； (3) 利用随机函数产生不少于100个随机整数，利用直接插入排序、希尔排序、冒泡、快速排序、直接选择、堆排序等排序方法进行递增排序，统计各算法的关键字比较次数和关键字移动次数； (4) 以菜单的形式组织程序各功能； (5) 至少要用5组不同的输入数据作比较，比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）； (6) 观察所有实验结果并汇集成表格加以总结。 4、 相关知识介绍将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。排序的目的是为了便于查找和处理，提高数据检索的效率。排序问题是要把若干无序数据元素序列排成一个有序序列。因此排序问题的数据元素集合是线性结构。在这个数据元素集合上也允许存取任意位置的数据元素，所以排序问题的数据结构是线性表。任何算法的实现方法都和算法所处理数据元素的存储结构有关。线性表的存储结构有顺序表和链表两种，因为数组具有随机存取特性，而链表不具备，所以排序算法基本上是基于顺序表设计的。排序的方法很多，若按待排序记录所在位置可分为外部排序（排序过程中需对外存进行访问的排序）和内部排序（待排序记录存放在内存）；按排序依据的不同原则来看，内部排序又可分为插入排序（直接插入排序、折半插入排序、希尔排序等）、交换排序（冒泡排序、快速排序等）、选择排序（简单选择排序、堆排序）、归并排序（2-路归并排序）和基数排序。因为排序过程常包括两个基本操作：比较两个关键字大小；将记录从一个位置移动到另一个位置，所以我们通过统计各算法的关键字比较次数和关键字移动次数的方法，直观地感受不同算法的时间复杂度。5、 课程设计分析插入排序的基本思想是，每次将一个待排序的记录按其关键字的大小插入到前面已经排好序的有序序列中的适当位置，直到全部记录插入完成为止。（1）直接插入排序是一种简单的排序方法，它的基本思想是将待插入记录ri与有序区的记录rj从右向左(j=i-1,i-21)比较，若rj ri则rj右移一个位置到rj+1；否则，将ri插入到j+1处。在改进算法中引进附加记录r0称为监视哨，其作用有两个：在进入查找（插入位置）循环之前，它保存了ri的副本，保证不至于因记录后移而丢失ri的内容；在查找循环中，避免检测下标变量j是否越界，从而减少算法运行时间。（2）希尔排序的排序过程是先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。该算法的执行时间依赖于增量序列（d1,d2,di）的选择，好的增量序列具有的共同特征是：最后一个增量是必须为1，并应该尽量避免序列中的值（尤其是乡邻的值）互为倍数的情况。不妨用下列算式计算增量d=d/3+1(d初始值为n)。交换排序主要通过记录间关键字的比较与存储位置的交换来达到排序的目的，其特点是将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。应用交换排序思想的主要排序方法有冒泡排序和快速排序。（1）冒泡算法需要n1趟排序，在算法中可作如下改进：设置一个布尔量exchange，在每趟排序前，先将其值设为false；若在排序过程中发生了交换，则将其置为true;若在某趟排序中未发现exchange变化，则终止整个算法。（2）快速排序的基本思想是通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序，就平均时间而言，快速排序是目前被认为最好的一种内部排序。选择排序是的基本思想是，每一趟处理都是在n-i+1(i=1,2,n-1)个记录中选择关键字最小的记录与其最后对应位置的记录交换，作为有序序列中的第i个记录。选择排序中常用的方法有直接选择排序和堆排序。（1） 直接选择排序的排序过程：首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录（用k指示），将它与第一个记录交换；再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；重复上述操作，共进行n-1趟排序后，排序结束。堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆。 堆排序：将无序序列建成一个堆，得到关键字最小的记录；输出堆顶的最小值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫。堆排序需解决的两个问题：如何由一个无序序列建成一个堆？（初建堆）如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？（调整堆）第二个问题解决方法筛选输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”第一个问题解决方法从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。6、实现提示：（1） 主要工作是设法在各算法程序适当的地方插入计数操作。（2） 注意分块调试的方法。（3） 排序对象用下列顺序存储结构表示：#define n 100 /*待排序的记录数目*/typedef int keytype; /关键字类型typedef struct rectype /记录类型keytype key; /关键字项/其它数据项依赖于具体应用而定义;rectype seqlistn+1;/表中第0个单元用作哨兵或暂存空间6、c语言源代码#include #include #include #define n 100 typedef int keytype; typedef struct rectype keytype key;rectype seqlistn+1;rectype datan; unsigned compcount=0; unsigned movecount=0; void insertsort(rectype r,int n) int i,j; for(i=2;i=n;i+) r0=ri; movecount+; j=i-1; while(r0.key1) for(j=d+1; j=0)&(r0.keyrprocess.key) compcount+; rprocess+d=rprocess; process=process-d; movecount+; rprocess+d=r0; movecount+; d=d/3+1; void bubblesort(rectype r,int n) int i,j; int exchange; for (i=1; i=i;j-) if(rj-1.keyrj.key) exchange=1; r0=rj; rj=rj-1; rj-1=r0; movecount +=3; compcount+; if (!exchange) break; void quicksort(rectype r,int low,int high) int i,j,k; if(low=high) return; i=low; j=high; r0=ri; while(ij) while(i=r0.key) j-;compcount+; if(ij) ri=rj;i+;movecount+; while(ij)&(ri.key=r0.key) i+;compcount+; if(ij) rj=ri;j-;movecount+; ri=r0; movecount+; quicksort(r,low,i-1); quicksort(r,i+1,high);void selectsort(rectype r,int n) int i,j,k; for(i=1;in;i+) k=i; for(j=i+1;j=n;j+) if(rj.keyrk.key) k=j; compcount+; if(i!=k) r0=ri; ri=rk; rk=r0; movecount += 3; int menu() int cn; char s; clrscr(); gotoxy(2,8); cprintf(*); gotoxy(2,9); cprintf(* *); gotoxy(2,10); cprintf(* 1: creat data *); gotoxy(2,11); cprintf(* *); gotoxy(2,12); cprintf(* 2: simple insert sort *); gotoxy(2,13); cprintf(* *); gotoxy(2,14); cprintf(* 3: shell sort *); gotoxy(2,15); cprintf(* *); gotoxy(2,16); cprintf(* 4: bubble sort *); gotoxy(2,17); cprintf(* *); gotoxy(2,18); cprintf(* 5: quick sort *); gotoxy(2,19); cprintf(* *); gotoxy(2,20); cprintf(* 6: simple select sort *); gotoxy(2,21); cprintf(* *); gotoxy(2,22); cprintf(* 7: exit *); gotoxy(2,23); cprintf(*); do gotoxy(2,25); cprintf(input 1-7: ); s=getche(); cn=(int)s-48; while (cn7); return cn;void createdata() int i; srand(unsigned int)time(null); for (i=0; in; i+) seqlisti+1.key=datai.key=rand()%1000; printf(nyou have created source data. press any key to continue.n); getch();void display(int manner) int i; clrscr(); printf(nnthe source data are below:nn); for (i=0; in; i+) if (i+1)%20)=0) printf(n); printf(%4d,datai.key); printf(nn); switch (manner) case 2: printf(nyou choose simple insert sort.);break; case 3: printf(nyou choose shell sort.);break; case 4: printf(nyou choose bubble sort.);break; case 5: printf(nyou choose quick sort.);break; case 6: printf(nyou choose simple select sort.);break; printf(the result is below.nn); for (i=1; i=n; i+) if (i%20)=0) printf(n); printf(%4d,seqlisti.key); printf(nncompcount=%u movecount=%un,compcount,movecount); printf(npress any key to go on.); getch();void main() int order; int flag=1; while (flag) order=menu(); switch (order) case 1: createdata(); break; case 2: compcount=0; movecount=0; insertsort(seqlist,n); display(order); break; case 3: compcount=0; movecount=0; shellsort(seqlist,n); display(order); break;