软件算法综合设计说明书

                           ---排序综合

学院：信息与电气工程学院

专业：计算机科学与技术

班级：10-02

姓名：

学号：100210214

2012.6.28

软件算法综合设计说明书

一、课程设计目的

1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力；

2、进一步提升C语言的应用能力；

3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法

和技能；

4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应

具备的科学的工作方法和作风；

6、提升文档写作能力

二、课程设计题目及要求

排序综合（限3人完成）

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进

行排序。

要求：

1、至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希

尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序

2、统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），

找出其中两种较快的方法。

三、题目分析

冒泡排序：

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

四、大体设计

五、设计详细源代码

1.冒泡排序

#include <iostream>

#include <time.h>

using namespace std;

#define N 20000

void main()

{

   int a[N];

   int i, j, temp;

   srand(time(0));

   for (i = 0; i < N; i++)

   {

       a[i] = rand();

   }

   int flag = 1;

   for (i = 0; i < N - 1 && flag == 1; i++)

   {

       flag = 0;

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

       {

          if (a[j + 1] < a[j])

          {

              temp = a[j + 1];

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

              a[j] = temp;

              flag = 1;

          }

       }

   }

   for (i = 0; i < N; i++)

   {

       printf("%d ", a[i]);

   }

}

2、统计性能

#include <stdio.h>

#include<stdlib.h>

#include<time.h>

#define N 10000

void main()

{

 int i,j,k,n;

 int n1,t;

 int a[N],b[N];

 FILE *fp;

 clock_t start,finish;

 int time1,time2,time3;

 printf("输入要产生的随机数个数:");

 scanf("%d",&n);

 srand((unsigned)time(NULL));

 for(i=0;i<n;i++)

  a[i]=rand();

 for(i=0;i<n;i++)b[i]=a[i];

 printf("**************************\n");

 printf("\t插入排序\n");

 printf("**************************\n");

 start=clock();

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

 {

  t=b[i];

  for(j=i-1;j>=0&&t<b[j];j--)

   b[j+1]=b[j];

  b[j+1]=t;

 }

 finish=clock();

 time1=finish-start;

 printf("插入排序耗时%d毫秒!\n\n\n",time1);

 fp=fopen("output1.txt","w");

 for(i=0;i<n;i++)

  fprintf(fp,"%d ",b[i]);

 fclose(fp);

 for(i=0;i<n;i++)b[i]=a[i];

 printf("**************************\n");

 printf("\t选择排序\n");

 printf("**************************\n");

 start=clock();

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

 {

  k=i;

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

   if(b[k]>b[j])k=j;

  t=b[i];

  b[i]=b[k];

  b[k]=t;

 }

 finish=clock();

 time2=finish-start;

 printf("选择排序耗时%d毫秒!\n\n\n",time2);

 fp=fopen("output2.txt","w");

 for(i=0;i<n;i++)

  fprintf(fp,"%d ",b[i]);

 fclose(fp);

 for(i=0;i<n;i++)b[i]=a[i];

 printf("**************************\n");

 printf("\t冒泡排序\n");

 printf("**************************\n");

 start=clock();

 n1=n-1;

 while(n1>0)

 {

  j=0;

  for(i=0;i<n1;i++)

   if(b[i]>b[i+1])

   {

    t=b[i];

    b[i]=b[i+1];

    b[i+1]=t;

    j=i;

   }

   n1=j;

 }

 finish=clock();

 time3=finish-start;

 printf("冒泡排序耗时%d毫秒!\n\n\n",time3);

 fp=fopen("output3.txt","w");

 for(i=0;i<n;i++)

  fprintf(fp,"%d ",b[i]);

 fclose(fp);

}

六、程序的调试与运行结果说明

运行结果1、使用冒泡程序完成题目要求运行结果如图1：

图1

运行结果2、三钟排序方法耗时 结果如图2：

图2

结果说明：

插入排序和选择排序耗费时间较少

七、课程设计总结

通过这次课程设计的学习让我学会了许多，加深了对数据结构排序算法的认识。在这次课程设计中，我们完成了每种排序算法。排序算法选了三个，包括：插入排序、选择排序、冒泡排序。同时也实现了随机数的生成。并把排序后的结果保存在不同的文件中。虽然在算法完成的过程中从网上参考了一些资料，但对这次课程设计的成果还是非常满意的。

这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。链表归并算法不是对链表直接操作，而是将链表中的元素放入数组中进行排序，我想了很多方法都没有想出对链表的直接操作的算法。由于时间限制，只在课程设计快结束时完成了产生随机文件这部分，我想以后有时间再来完成它。

同时在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的文件读写操作。撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。当然，还包括如何写出操作简便，感觉友好的界面。

但我还是认为自己还有很多不足，希望以后能弥补。

参考文献：

[1] 严蔚敏，《数据结构 C语言》，清华大学出版社；

[2] 谭浩强，《c语言程序设计》，清华大学出版社；

[3]http://wenku.baidu.com/view/5f397e30b90d6c85ec3ac62f.html

第二篇：4.4排序算法设计

排序算法设计

一、内容分析

【教学目标】

1、理解排序的概念

2、了解常用排序方法

3、理解冒泡排序的基本思路

4、应用冒泡排序法进行排序

【重点难点】

1、冒泡排序法的基本思路

2、应用冒泡排序法进行排序

二、教学内容

（一）常用排序

排序的概念：

排序就是把一组元素（数据或记录）按照元素的值的递增或递减的次序重新排列元素的过程。

如：49 38 76 27 13

常用排序的方法：

1、冒泡排序：冒泡排序是一种简单而饶有趣味的排序方法，它的基本思想是：每次仅进行相邻两个元素的比较，凡为逆序（a(i)>a(i+1)），则将两个元素交换。

2、插入排序：它是一种最简单的排序方法，它的基本思想是依次将每一个元素插入到一个有序的序列中去。这很象玩#9@k牌时一边抓牌一边理牌的过程，

抓了一张就插到其相应的位置上去。

3、选择排序：这是一种比较简单的排序方法，其基本思想是，每一趟在n-i+1（i=1，2，3，...，n-1）个元素中选择最小的元素。

冒泡排序：

冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。

整个的排序过程为：

先将第一个元素和第二个元素进行比较，若为逆序，则交换之；接着比较第二个和第三个元素；依此类推，直到第n-1个元素和第n个元素进行比较、交换为止。如此经过一趟排序，使最大的元素被安置到最后一个元素的位置上。然后，对前n-1个元素进行同样的操作，使次大的元素被安置到第n-1个元素的位置上。重复以上过程，直到没有元素需要交换为止。

例题：对49 38 76 27 13 进行冒泡排序的过程：

初始状态： [49 38 76 27 13 ]

第一趟排序后：[38 49 27 13] 76

第二趟排序后：[38 27 13 ] 49 76

第三趟排序后：[27 13 ] 38 49 76

第四趟排序后：13 27 38 49 76

课堂练习：

用冒泡排序对68 45 35 75 55 17 41进行排序，第二趟排序后的状态为：

A、45 35 68 55 17 41 75

B、35 17 41 45 55 68 75

C、35 45 55 17 41 68 75

D、35 45 17 41 55 68 75

作业：

1、以下两组数据按有小到大排序，请写出每一趟排序后的结果

45 82 12 75 13 89 95

90 87 76 65 54 43 32 21

2、以下两组数据按有大到小排序，请写出每一趟排序后的结果

45 52 12 18 85 46 32

12 23 34 45 56 67 78 89 91

拓展：

随机生成10个不同的整数存于数组a（1 to 10）中，按从小到大的顺序输出。

三、小结

冒泡排序：

冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。

整个的排序过程为：

先将第一个元素和第二个元素进行比较，若为逆序，则交换之；接着比较第二个和第三个元素；依此类推，直到第n-1个元素和第n个元素进行比较、交换为止。如此经过一趟排序，使最大的元素被安置到最后一个元素的位置上。然后，对前n-1个元素进行同样的操作，使次大的元素被安置到第n-1个元素的位置上。

重复以上过程，直到没有元素需要交换为止。

例题：对49 38 76 27 13 进行冒泡排序的过程： 初始状态： [49 38 76 27 13 ]

第一趟排序后：[38 49 27 13] 76

第二趟排序后：[38 27 13 ] 49 76

第三趟排序后：[27 13 ] 38 49 76

第四趟排序后：13 27 38 49 76 排序算法编程相关知识：

1、数组的定义：

声明数组的一般格式如下：

Dim 数组名（[下界 to ] 上界）As 数据类型

2、数组元素的输入输出：

（1）生成随机整数(1-100之间)

Randomize

for i=1 to n

a(i)=int(rnd*100+1)

next i

（2）输出数组元素

for i=1 to n

print a(i);

next i

3、冒泡排序的算法实现：

冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：

每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。

用两个FOR循环实现：

for j=n-1 to 1 step -1

for i=1 to j

if a(i)>a(i+1) then

t=a(i)

a(i)=a(i+1)

a(i+1)=t

end if

next i

next j

排序算法的应用：

1、随机生成10个不同的整数存于数组a（1 to 10）中，按从小到大的顺序输出。

2、随机生成20个学生的考试成绩，其中前50%的学生可以参加夏令营。输出这50%的学生的成绩。

3、数组A和数组B 分别记录6个数据，现在要把这两个数组合并成一个有序的数组。（从大到小的顺序）