十大排序法综合排序的设计和实现 - 图文

十大排序法对大量数据综合排序的设计和实现

文档信息

开发小组： 组长：于微 成员：郑鸿、张雪莹、杨宝英 单位：软件设计工作室 完成时间：

软件信息

系统名称： 十大排序法对大量数据综合排序 2010年10月10日 当前版本： 作 者： Microsoft Word 杨宝英、郑鸿 文档类型： 软件开发用技术文档 运行环境 Windows Seven 环境下Visual C+ + 6.0版本 参与编写： 日期： 系统简介： 于微、郑鸿、张雪莹、杨宝英 2010年10月5号-2010年10月10号 系统面向大众人群，囊括了起泡排序、插入排序、二分排序、选择排序、希尔排序、快速排序、堆排序、桶排序、基数排序、二路归并排序这十个常用排序，此系统可对一百万个随机数进行综合排序，计算各排序时间，以比较各排序工作的效率。

第 1 页 共 23 页

目录 一、 序言......................................................................................................................................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 页 共 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大量数据的导入

系统为用户提供大量可供排序的数据。运行程序时，系统将随机产生一百万个数字以便于用户使用。导入数据应快速稳定。

第 3 页 共 23 页

2.3.2排序时间的自行显示

为了比较各个排序算法的效率，系统界面除了显示排序结果以外还会显示所使用的算法的排序时间，以秒为单位，便于用户对比。 2.4系统的非功能性需求

2.4.1用户界面需求

简洁、易用、易懂，美观、大方、标准，具备一定的兼容性。、 2.4.2软硬件环境需求

软件：程序代码在操作系统windows95及以后版本 VC++6.0开发环境中编译。

硬件： 硬盘 2GB以上。

三、可行性分析报告

排序算法在我们日常编写程序中经常会用到，特别是编写信息管理系统之类的程序更是运用得非常广泛，因此对于这十个常用的排序算法都比较熟悉。通过相关书籍的阅读和网上信息的查询可以很快掌握这些算法。小组一共四个人，经过合理的分工，从十月五号到十月十号，这六天时间里可以完成代码的编写和程序相关功能的实现以及文档写作这些工作。

再加上工作室提供了很好的编程环境和网络支持，因而该系统的实现是可行的。

四、概要设计

4.1系统总体结构图

第 4 页 共 23 页

图4.1

五、详细设计

5.1主函数与各模块的关系

图5.1

第 5 页 共 23 页

程序运行时，主函数进行初始化操作，从系统导入一百万个随机数。通过switch-case语句结构对用户指令进行辨别，根据用户指令调用相应功能模块函数。

5.2各模块功能函数 5.2.1基数排序函数的实现

函数声明：void r_sort(int *dat,int n);

基数排序是将数字按位数划分出n个关键字，每次针对一个关键字进行排序，然后针对排序后的序列进行下一个关键字的排序，循环至所有关键字都使用过则排序完成。 代码实现如下：

int maxbit(int *dat,int n)//求最大位数，n个元素 { }

void r_sort(int *dat,int n) {

int i,tmp,bit_num=0,t; for(i=0;i

return bit_num;

t=0; tmp=dat[i]; while(tmp>0) { }

if(bit_num

bit_num=t; t++; tmp/=10;

第 6 页 共 23 页

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

}

第 7 页 共 23 页

{ }

cout << \基数法排序结果如下:\del(dat,n);

memset(coun,0,sizeof(coun)); for(i=0;i

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

coun[i]+=coun[i-1]; tmp=dat[i]/denominator; ++coun[tmp];

for(i=n-1;i>=0;--i) { }

for(i=0;i

dat[i]=tmp_dat[i];

tmp=dat[i]/denominator; --coun[tmp];

tmp_dat[coun[tmp]]=dat[i];

denominator*=10;

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]

temp = a[i-1];

a[i-1] = a[i]; a[i] = temp; bound = i; } }

left = bound+1;

for (i = left; i

if(a[i] < a[i-1])

第 8 页 共 23 页

{

temp = a[i-1];

a[i-1] = a[i]; a[i] = temp; bound = i; } }

right = bound-1; }while(right-left>1); }

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

min=i; //记录关键码码最小的位置 for (j=i+1; j

if (a[j] < a[min]) min=j; if (i!=min)

第 9 页 共 23 页

cout<<\起泡法排序结果如下:\del(a,n);

}

}

{ }

t=a[i]; a[i]=a[min]; a[min]=t;

cout<<\选择法的排序结果如下:\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

{

temp= a[i]; //取出要插入的数a[i]，用临时变量temp储存 for (j=i-1;j>=0&&temp

a[j+1] = a[j];

a[j+1] = temp;//插入

} }

第 10 页 共 23 页

cout<<\插入法的排序结果如下:\del(a,n);

5.2.5希尔排序函数的实现

函数声明：void Sellsort(int a[],int n)；

希尔排序又称增量缩小排序，基本思想是先将序列按增量划分为元素个数相同的若干子序列，在子序列内分别进行直接插入排序，然后不断缩小增量直至为1，最后使用直接插入排序法完成排序。

代码实现如下： void Sellsort(int a[],int n) { }

5.2.6二分排序函数的实现

函数声明：void Dichotomy(int a[],int n)；

二分排序法的基本思想是：在插入第i个元素时，对前面的0～(i-1)个元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半元素进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

int i,j,d,temp;

for (d = n/2; d >= 1; d = d/2) //以d为增量进行插入排序 { }

cout<<\希尔法的排序结果如下:\del(a,n);

for (i = d+1; i

temp = a[i];

for (j = i-d; j>0 && temp

a[j+d] = a[j]; //后移记录

a[j+d] = temp;

第 11 页 共 23 页

代码实现如下：

void Dichotomy(int a[],int n) { }

第 12 页 共 23 页

int i,j; int temp; int mid; int left; int right; for(i=1;i

temp=a[i]; }

cout<<\二分法排序结果如下:\del(a,n);

left=0; right=i-1; while(left<=right) { }

for(j=i-1;j>=left;j--)

a[j+1]=a[j]; mid=(left+right)/2; if(temp

right=mid-1;

else

left=mid+1;

if(left!=i)

a[left]=temp;

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(i

while(i

j--; //j前移

if(i

{ }

temp = a[j]; a[j] = a[i];

a[i] = temp; //进行交换 i++; //i后移

while(i

if(i

temp = a[i]; a[i] = a[j];

第 13 页 共 23 页

}

}

}

a[j] = temp; //进行交换 j--;

return i;

5.2.8桶排序函数的实现

函数声明：void inc_sort(int keys[],int size,int bucket_size)；

代码实现如下： typedef struct node {

int key;

struct node * next;

}KeyNode;

void inc_sort(int keys[],int size,int bucket_size) {

int a[100000];

int count=0;

KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode

*));

for(int i=0;i

bucket_table[i]=(KeyNode *)malloc(sizeof(KeyNode)); bucket_table[i]->key=0; //记录当前桶中的数据量 bucket_table[i]->next=NULL;

}

第 14 页 共 23 页

for(int j=0;j

{

KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode)); node->key=keys[j]; node->next=NULL;

int index=keys[j]/10; //映射函数计算桶号

KeyNode *p=bucket_table[index]; //初始化P成为桶中数据链表的头指针

if(p->key==0) //该桶中还没有数据

{

bucket_table[index]->next=node;

(bucket_table[index]->key)++;

}else {

//链表结构的插入排序

while(p->next!=NULL&&p->next->key<=node->key)

p=p->next;

node->next=p->next; p->next=node;

(bucket_table[index]->key)++; }

}

cout<<\桶排序的结果如下:\

for(int b=0;b

for(KeyNode *k=bucket_table[b]->next;k!=NULL;k=k->next)

第 15 页 共 23 页

cout<key<<\

cout<

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 < low && Tree[j] < Tree[j + 1]) //如果左孩子小于右孩子 j++; //使j指向右孩子

//总之哪个孩子的关键码较大，就使j指向哪一个 if (Tree[i] > Tree[j])

break; //如果根节点大于左右孩子其中的任何一个，那么比较结束

第 16 页 共 23 页

} /*

}

else //否则进行交换 { }

t = Tree[i]; Tree[i] = Tree[j]; Tree[j] = t;

i = j; //让被筛选的结点位于原来j的位子上 j = 2*i;

************************************** 进行初始建堆 和 重建堆

************************************** */

void Set_Tree(int Tree[], int low) {

int T; int i; int k;

for(i = low/2-1; i >= 0; i--) //从最后一个分支结点开始筛选，进行堆的初始化

Slect(Tree, i, low);

for(k = low-1; k >= 2; k--) //重复移走堆顶，重新建堆 { }

T = Tree[0];

第 17 页 共 23 页

T = Tree[0]; Tree[0] = Tree[k];

Tree[k] = T; //堆顶和最后一个结点进行交换 Slect(Tree, 0, k-1 ); //进行筛选，从Tree[0]到Tree[low-2]

}

Tree[0] = Tree[k];//进行筛选，从Tree[0]到Tree[1] Tree[k] = 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) { }

//进行一趟归并

void MergePass(int a[], int b[], int n, int lenth) {

int i = 0, k;

第 18 页 共 23 页

int i= low, j = mid + 1,k = low; while ((i <= mid) && (j <= high)) { }

if(i <= mid)

while(i <= mid)

b[k++] = a[i++]; if(a[i] <= a[j])

b[k++] = a[i++];

else b[k++] = a[j++];

else

while(j <= high)

b[k++]=a[j++];

}

while(i <= n - 2*lenth) { }

if(i < n - lenth )

Merge(a, b, i, i + lenth -1, n-1);

Merge(a, b, i, i + lenth -1, i + 2*lenth -1); i += 2*lenth;

else

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

b[k] = a[k];

//进行二路归并

void MergeSort(int a[], int n) {

int* b=(int*)malloc(n*sizeof(int)); }

int lenth = 1; while(lenth < n) { }

cout<<\二路归并法排序结果如下:\del(a,n);

MergePass(a, b,n, lenth); lenth = 2*lenth; MergePass(b, a, n, lenth); lenth = 2*lenth;

第 19 页 共 23 页

5.2.11过滤重复数据

函数声明：void del(int a[],int n)；

系统产生的随机数里有很多重复的数据，如果全部用来排序会占用系统内存，因此需要把重复的数据过滤掉，使只出现一次。过滤数据后不影响排序结果。

代码实现如下：

void del(int a[],int n) //打印结果，过滤重复的 { int i;

for(i = 0;i

{

int guide=a[i];

if(a[i+1]!=guide)

cout<

}

cout<

六、使用说明

登入界面

第 20 页 共 23 页

图6.1

系统运行后进入操作界面，显示菜单栏，1至10个数字分别对应不同的排序算法。界面显示产生1000000个随机数的运行时间。随即系统自行产生随机数，并将产生的随机数存储到文件中。下图为文件中的部分随机数。

图6.2

用户选择需要的排序算法，从键盘输入对应的字符，系统即按该排序方法对随机数进行排序，并将排序结果保存到文件中。同时界面上会显示本次排序所用的时间。下图以二路归并排序为例。

第 21 页 共 23 页

图6.3

此为文件中二路归并的部分排序结果。

图6.4

用户根据上述方法可以进行十个排序算法的运行，每个算法的排序时间都会在界面上显示，便于用户比较。

第 22 页 共 23 页

七、心得体会

通过该设计的操作与实践，训练我们灵活应用所学知识，独立完成对算法的理解、分析、掌握，编程实现算法全过程的综合实践能力，巩固、深化我们的理论知识。掌握排序算法的思想，提高对排序算法的正确分析能力，更好的掌握递归思想，巩固应用递归思想，提高分析能力。

集体的力量是强大的，要团结一致，这些天，经过大家的共同努力，完成了本次的十个排序算法程序。在解决不了的问题时，要像同学或老师请教，而且要学会要多到图书馆或上网查阅资料来解决所遇到的问题。

八、参考资料

[1] 谭浩强 . C++程序设计. 北京：清华大学出版社, 2005。

[2] 王红梅 胡明 王涛. 数据结构（C++版）. 北京：清华大学出版社，2005。

第 23 页 共 23 页

本文来源：https://www.bwwdw.com/article/2x58.html