十大排序法对大量数据综合排序的设计和实现文档信息开发小组：组长：于微成员：郑鸿、张雪莹、杨宝英单位：软件设计工作室文档类型：软件开发用技术文档当前版本：Microsoft Word作者：杨宝英、郑鸿完成时间：2010年10月10日软件信息系统名称：十大排序法对大量数据综合排序运行环境Windows Seven 环境下Visual C+ + 6.0版本参与编写：于微、郑鸿、张雪莹、杨宝英日期：2010年10月5号-2010年10月10号系统简介：系统面向大众人群，囊括了起泡排序、插入排序、二分排序、选择排序、希尔排序、快速排序、堆排序、桶排序、基数排序、二路归并排序这十个常用排序，此系统可对一百万个随机数进行综合排序，计算各排序时间，以比较各排序工作的效率。
一、序言 (3)二、需求分析说明书 (3)2.1系统介绍 (3)2.2系统面向的用户群体 (3)2.3系统的功能性需求 (3)2.4系统的非功能性需求 (4)2.4.1用户界面需求 (4)2.4.2软硬件环境需求 (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)随着社会的发展，人们迎来了信息时代，各种信息日益丰富，需要处理的信息也急剧增加，对数据的排序正是这些处理中的重要一部分。
排序讲究效率，而历来的排序算法种类繁多，各有优劣，难以比较。
所以本次设计运用了人们常用的十大排序算法对一百万个随机数据进行综合排序，以便比较出各种算法的优劣。
选择出几种效率较高的算法应用在实际应用中，使计算机的运行效率更高，更加准确，更加科学化和正规化。
二、需求分析说明书2.1系统介绍本系统定位于大众人群，系统开发平台为Windows Seven,程序设计语言为C++，程序的运行环境为Visual C+ + 6.0。
Visual C+ + 6.0版本主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。
用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。
2.2系统面向的用户群体系统面向的用户群体为研究排序算法优劣及需要对数据进行排序的人群。
或是对排序算法感兴趣的大众人群。
2.3系统的功能性需求2.3.1数据排序的功能系统提供了基数排序、起泡排序、选择排序、插入排序、希尔排序、二分排序、快速排序、桶排序、堆排序、二路归并排序这十大常用排序。
用户可根据自身需要在键盘上输入各排序算法对应的字符，系统即可实现这些算法的排序，并将排序结果显示在系统界面上。
2.3.2大量数据的导入系统为用户提供大量可供排序的数据。
运行程序时，系统将随机产生一百万个数字以便于用户使用。
导入数据应快速稳定。
2.3.2排序时间的自行显示为了比较各个排序算法的效率，系统界面除了显示排序结果以外还会显示所使用的算法的排序时间，以秒为单位，便于用户对比。
2.4系统的非功能性需求2.4.1用户界面需求简洁、易用、易懂，美观、大方、标准，具备一定的兼容性。
、2.4.2软硬件环境需求软件：程序代码在操作系统windows95及以后版本VC++6.0开发环境中编译。
硬件：硬盘 2GB以上。
三、可行性分析报告排序算法在我们日常编写程序中经常会用到，特别是编写信息管理系统之类的程序更是运用得非常广泛，因此对于这十个常用的排序算法都比较熟悉。
通过相关书籍的阅读和网上信息的查询可以很快掌握这些算法。
小组一共四个人，经过合理的分工，从十月五号到十月十号，这六天时间里可以完成代码的编写和程序相关功能的实现以及文档写作这些工作。
再加上工作室提供了很好的编程环境和网络支持，因而该系统的实现是可行的。
四、概要设计4.1系统总体结构图图4.1五、详细设计5.1主函数与各模块的关系图5.1程序运行时，主函数进行初始化操作，从系统导入一百万个随机数。
通过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;i<n;i++){t=0;tmp=dat[i];while(tmp>0){t++;tmp/=10;}if(bit_num<t)bit_num=t;}return bit_num;}void r_sort(int *dat,int n){int coun[10];//对各位数字计数int bit_num=maxbit(dat,n);int i,tmp;int *tmp_dat;tmp_dat=new int[n];int denominator=1;while(bit_num--)//最大有几位就排几次，从个位到最高位，位数不足的前边自动补0{memset(coun,0,sizeof(coun));for(i=0;i<n;++i){tmp=dat[i]/denominator%10;++coun[tmp];}for(i=1;i<10;++i)coun[i]+=coun[i-1];for(i=n-1;i>=0;--i){tmp=dat[i]/denominator%10;--coun[tmp];tmp_dat[coun[tmp]]=dat[i];}for(i=0;i<n;i++)dat[i]=tmp_dat[i];denominator*=10;}cout << "基数法排序结果如下:" << endl;del(dat,n);}5.2.2起泡排序函数的实现函数声明：void bubblesort(int a[],int n)；起泡排序的基本思想是将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。
依次类推，直至第n-1个记录和第n个记录的关键字进行比较为止。
起泡排序是一种稳定的排序方法，在随机产生数的情况下，总的时间复杂度为O(n2)。
代码实现如下：void bubblesort(int a[],int n){int temp,i;int left = 1;int right = n-1;int bound=n;do{for (i = right;i >= left; i--){if(a[i] <a[i-1]){temp = a[i-1];a[i-1] = a[i];a[i] = temp;bound = i;}}left = bound+1;for (i = left; i<right+1; i++){if(a[i] < a[i-1]){temp = a[i-1];a[i-1] = a[i];a[i] = temp;bound = i;}}right = bound-1;}while(right-left>1);cout<<"\n起泡法排序结果如下:"<<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; i<n; i++) //对n个记录进行n-1趟简单选择排序{min=i; //记录关键码码最小的位置for (j=i+1; j<n; j++)if (a[j] < a[min]) min=j;if (i!=min){t=a[i];a[i]=a[min];a[min]=t;}}cout<<"\n选择法的排序结果如下:"<<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<n; i++){temp= a[i]; //取出要插入的数a[i]，用临时变量temp储存for (j=i-1;j>=0&&temp<a[j];j--) //寻找位置a[j+1] = a[j];a[j+1] = temp;//插入}cout<<"\n插入法的排序结果如下:"<<endl;del(a,n);}5.2.5希尔排序函数的实现函数声明：void Sellsort(int a[],int n)；希尔排序又称增量缩小排序，基本思想是先将序列按增量划分为元素个数相同的若干子序列，在子序列内分别进行直接插入排序，然后不断缩小增量直至为1，最后使用直接插入排序法完成排序。
代码实现如下：void Sellsort(int a[],int n){int i,j,d,temp;for (d = n/2; d >= 1; d = d/2) //以d为增量进行插入排序{for (i = d+1; i<n; i++) //将a[i]插入到所属的子序列中{temp = a[i];for (j = i-d; j>0 && temp<a[j]; j = j-d)a[j+d] = a[j]; //后移记录a[j+d] = temp;}}cout<<"\n希尔法的排序结果如下:"<<endl;del(a,n);}5.2.6二分排序函数的实现函数声明：void Dichotomy(int a[],int n)；二分排序法的基本思想是：在插入第i个元素时，对前面的0～(i-1)个元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半元素进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。