十大排序法综合排序的设计和实现.doc

第 1 页 共 23 页 十大排序法对大量数据综合排序的设计和实现十大排序法对大量数据综合排序的设计和实现 文档信息 文档类型：软件开发用技术文档 当前版本：Microsoft Word 作 者：杨宝英、郑鸿 开发小组： 组长：于微 成员：郑鸿、张雪莹、杨 宝英 单位：软件设计工作室 完成时间：2010 年 10 月 10 日 软件信息 系统名称：十大排序法对大量数据综合排序 运行环境Windows Seven 环境下 Visual C+ + 6.0 版本 参与编写：于微、郑鸿、张雪莹、杨宝英 日期：2010 年 10 月 5 号-2010 年 10 月 10 号 系统简介：系统面向大众人群，囊括了起泡排序、插入排序、二分排序、 选择排序、希尔排序、快速排序、堆排序、桶排序、基数排 序、二路归并排序这十个常用排序，此系统可对一百万个随 机数进行综合排序，计算各排序时间，以比较各排序工作的 效率。 第 2 页 共 23 页 目录目录 一、一、 序言.3 二、 需求分析说明书.3 2.1 系统介绍.3 2.2 系统面向的用户群体.3 2.3 系统的功能性需求.3 2.4 系统的非功能性需求.4 2.4.1 用户界面需求.4 2.4.2 软硬件环境需求.4 3、可行性分析报告 4 4、概要设计.5 五、详细设计 5 5.1 主函数于各模块的关系.5 5.2 各模块功能函数.6 5.2.1 基数排序函数的实现.6 5.2.2 起泡排序函数的实现.8 5.2.3 选择排序函数的实现.9 5.2.4 插入排序函数的实现.10 5.2.5 希尔排序函数的实现.11 5.2.6 二分排序函数的实现.11 5.2.7 快速排序函数的实现.13 5.2.8 桶排序函数的实现.14 5.2.9 堆排序函数的实现.16 5.2.10 二路归并排序函数的实现.18 5.2.11 过滤重复数据的实现.20 六、使用说明 20 七、心得体会.23 参考资料 23 第 3 页 共 23 页 一、序言一、序言 随着社会的发展，人们迎来了信息时代，各种信息日益丰富，需要处理的 信息也急剧增加，对数据的排序正是这些处理中的重要一部分。 排序讲究效率，而历来的排序算法种类繁多，各有优劣，难以比较。所以 本次设计运用了人们常用的十大排序算法对一百万个随机数据进行综合排序， 以便比较出各种算法的优劣。选择出几种效率较高的算法应用在实际应用中， 使计算机的运行效率更高，更加准确，更加科学化和正规化。 二、需求分析说明书二、需求分析说明书 2.1 系统介绍系统介绍 本系统定位于大众人群，系统开发平台为 Windows Seven,程序设计语言 为 C+，程序的运行环境为 Visual C+ + 6.0。 Visual C+ + 6.0 版本主要包括文本编辑器、资源编辑器、工程创建工具、 Debugger 调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、 打开和编辑文件、编译、链接、运行、调试应用程序。 2.2 系统面向的用户群体系统面向的用户群体 系统面向的用户群体为研究排序算法优劣及需要对数据进行排序的人群。 或是对排序算法感兴趣的大众人群。 2.3 系统的功能性需求系统的功能性需求 2.3.1 数据排序的功能 系统提供了基数排序、起泡排序、选择排序、插入排序、希尔排序、二 分排序、快速排序、桶排序、堆排序、二路归并排序这十大常用排序。用户可 根据自身需要在键盘上输入各排序算法对应的字符，系统即可实现这些算法的 排序，并将排序结果显示在系统界面上。 2.3.2 大量数据的导入 系统为用户提供大量可供排序的数据。运行程序时，系统将随机产生一 百万个数字以便于用户使用。导入数据应快速稳定。 第 4 页 共 23 页 2.3.2 排序时间的自行显示 为了比较各个排序算法的效率，系统界面除了显示排序结果以外还会显 示所使用的算法的排序时间，以秒为单位，便于用户对比。 2.4 系统的非功能性需求系统的非功能性需求 2.4.1 用户界面需求 简洁、易用、易懂，美观、大方、标准，具备一定的兼容性。 、 2.4.2 软硬件环境需求 软件：程序代码在操作系统 windows95 及以后版本 VC+6.0 开发环境 中编译。 硬件： 硬盘 2GB 以上。 三、可行性分析报告三、可行性分析报告 排序算法在我们日常编写程序中经常会用到，特别是编写信息管理系统之 类的程序更是运用得非常广泛，因此对于这十个常用的排序算法都比较熟悉。 通过相关书籍的阅读和网上信息的查询可以很快掌握这些算法。小组一共四个 人，经过合理的分工，从十月五号到十月十号，这六天时间里可以完成代码的 编写和程序相关功能的实现以及文档写作这些工作。 再加上工作室提供了很好的编程环境和网络支持，因而该系统的实现是可 行的。 四、概要设计四、概要设计 4.1 系统总体结构图 第 5 页 共 23 页 图 4.1 五、详细设计五、详细设计 5.1 主函数与各模块的关系 图 5.1 第 6 页 共 23 页 程序运行时，主函数进行初始化操作，从系统导入一百万个随机数。通过 switch-case 语句结构对用户指令进行辨别，根据用户指令调用相应功能模块函 数。 5.2 各模块功能函数 5.2.1 基数排序函数的实现 函数声明：void r_sort(int *dat,int n); 基数排序是将数字按位数划分出 n 个关键字，每次针对一个关键字进行排 序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字 都使用过则排序完成。 代码实现如下： int maxbit(int *dat,int n)/求最大位数，n 个元素 int i,tmp,bit_num=0,t; for(i=0;i0) t+; tmp/=10; if(bit_numt) bit_num=t; return bit_num; void r_sort(int *dat,int n) 第 7 页 共 23 页 int coun10;/对各位数字计数 int bit_num=maxbit(dat,n); int i,tmp; int *tmp_dat; tmp_dat=new intn; int denominator=1; while(bit_num-)/最大有几位就排几次，从个位到最高位，位数不足的 前边自动补 0 memset(coun,0,sizeof(coun); for(i=0;in;+i) tmp=dati/denominator%10; +countmp; for(i=1;i=0;-i) tmp=dati/denominator%10; -countmp; tmp_datcountmp=dati; for(i=0;in;i+) dati=tmp_dati; denominator*=10; cout 基数法排序结果如下: = left; i-) if(ai ai-1) temp = ai-1; ai-1 = ai; ai = temp; bound = i; left = bound+1; for (i = left; iright+1; i+) 第 9 页 共 23 页 if(ai 1); coutn 起泡法排序结果如下:endl; del(a,n); 5.2.3 选择排序函数的实现 函数声明：void Selectsort(int a,int n)； 选择排序法的基本思想是：第 i 趟排序通过 n-i 次关键码的比较，在 n-1+i (1 = i = n-1)个记录中选取关键码最小的记录，并和第 i 个记录交换 作为有序序列的第 i 个记录。选择排序是一种稳定的排序方法，总的时间复杂 度是 O(n2)。 代码实现如下： void Selectsort(int a,int n) int i,j,t; int min; for (i=0; in; i+) /对 n 个记录进行 n-1 趟简单选择排序 min=i; /记录关键码码最小的位置 for (j=i+1; jn; j+) if (aj amin) min=j; 第 10 页 共 23 页 if (i!=min) t=ai; ai=amin; amin=t; coutn 选择法的排序结果如下:endl; del(a,n); 5.2.4 插入排序函数的实现 函数声明：void InsertSort(int a,int n)； 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入 到排好序的有序表中，直到无序区中没有记录为止，从而得到一个新的有序表。 直接插入排序是一种稳定的排序方法，其时间复杂度为 O(n)。 代码实现如下： void InsertSort(int a,int n) int i,j,temp; for (i =1; i=0j-) /寻找位置 aj+1 = aj; aj+1 = temp;/插入 coutn 插入法的排序结果如下:= 1; d = d/2) /以 d 为增量进行插入排序 for (i = d+1; i0 j = j-d) aj+d = aj; /后移记录 aj+d = temp; coutn 希尔法的排序结果如下:right，然后再把第 i 个元素前 1 位与目标 第 12 页 共 23 页 位置之间的所有元素后移，再把第 i 个元素放在目标位置上。 代码实现如下： void Dichotomy(int a,int n) int i,j; int temp; int mid; int left; int right; for(i=1;in;i+) temp=ai; left=0; right=i-1; while(left=right) mid=(left+right)/2; if(temp=left;j-) aj+1=aj; if(left!=i) aleft=temp; coutn 二分法排序结果如下:endl; del(a,n); 第 13 页 共 23 页 5.2.7 快速排序函数的实现 函数声明：int partition(int a,int first,int end)； 基本思想是：首先选一个轴值（即比较的基准） ，将待排序记录分割成独立 的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或 等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。快速排序 是一种不稳定的排序方法，时间复杂度为 O（nlog2n） 代码实现如下： int partition(int a,int first,int end) /快速排序的一次 int i; int j; i = first;j = end; /对 i，j 进行初始化 int temp; /做临时变量 while(ij) while(ij /j 前移 if(ij) temp = aj; aj = ai; ai = temp; /进行交换 i+; /i 后移 while(ij if(inext=NULL; 第 15 页 共 23 页 for(int j=0;jkey=keysj; node-next=NULL; int index=keysj/10; /映射函数计算桶号 KeyNode *p=bucket_tableindex; /初始化 P 成为桶中数据链表的头指针 if(p-key=0) /该桶中还没有数据 bucket_tableindex-next=node; (bucket_tableindex-key)+; else /链表结构的插入排序 while(p-next!=NULL node-next=p-next; p-next=node; (bucket_tableindex-key)+; cout桶排序的结果如下:next) 第 16 页 共 23 页 coutkey ; coutendl; 5.2.9 堆排序函数的实现 函数声明：void Slect(int Tree, int high, int low)； 基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中 所有记录的最大者即堆顶记录，然后将它们从堆中移走（通常将堆顶记录和堆 中最后一个记录交换） ，并将剩余的记录再调整成堆，这样又找出了次大的记录， 依此类推，直到堆中只有一个记录为止。堆排序是一种不稳定的排序方法，总 的时间复杂度为 O(nlog2n)。 代码实现如下： /* * 筛选结点与左右孩子进行比较 * */ void Slect(int Tree, int high, int low) int i = high; /i 指向要筛选的结点 int j = 2*i+1; /j 指向结点的左孩子 int t; while (j = low) /筛选还没有进行到叶子 if (j = 0; i-) /从最后一个分支结点开始筛选，进行堆的初始化 Slect(Tree, i, low); for(k = low-1; k = 2; k-) /重复移走堆顶，重新建堆 T = Tree0; Tree0 = Treek; Treek = T; /堆顶和最后一个结点进行交换 第 18 页 共 23 页 Slect(Tree, 0, k-1 );/进行筛选，从 Tree0到 Treelow-2 T = Tree0; Tree0 = Treek;/进行筛选，从 Tree0到 Tree1 Treek = T; del(Tree,low); 5.2.10 二路归并排序函数的实现 函数声明：void MergeSort(int a, int n)； 基本思想是：将若干个有序序列进行两两归并，直至所有待排序记录都在 一个有序序列为止。二路归并排序是一种稳定的排序方法，其时间复杂度为 O(nlog2n)，空间复杂度为 O（n） 。 代码实现如下： void Merge(int a, int b, int low, int mid, int high) int i= low, j = mid + 1,k = low; while (i = mid) else bk+ = aj+; if(i = mid) while(i = mid) bk+ = ai+; else while(j = high) bk+=aj+; 第 19 页 共 23 页 /进行一趟归并 void MergePass(int a, int b, int n, int lenth) int i = 0, k; while(i = n - 2*lenth) Merge(a, b, i, i + lenth -1, i + 2*lenth -1); i += 2*lenth; if(i n - lenth ) Merge(a, b, i, i + lenth -1, n-1); else for(k = i; k = n-1; k+) bk = ak; /进行二路归并 void MergeSort(int a, int n) int* b=(int*)malloc(n*sizeof(int); int lenth = 1; while(lenth n) MergePass(a, b,n, lenth); lenth = 2*lenth; MergePass(b, a, n, lenth); lenth = 2*lenth; 第 20 页 共 23 页 coutn 二路归并法排序结果如下:endl; del(a,n); 5.2.11 过滤重复数据 函数声明：void del(int a,int n)； 系统产生的随机数里有很多重复的数据，如果全部用来排序会占用系 统内存，因此需要把重复的数据过滤掉，使只出现一次。过滤数据后不影 响排序结果。 代码实现如下： void del(int a,int n) /打印结果，过滤重复的 int i; for(