冒泡排序、选择排序、堆排序算法课程设计

《算法设计与分析导论》

课程设计

题目：排序

院系： 000000000000000000

专业： 00000000000000

学号姓名： 0000000000 000000 指导老师： 0000 日期： 2017 年 6 月 20 日

摘要

排序是计算机程序设计的一种重要操作，它的功能是将一组任意顺序的数据元素，根据一个或几个关键字按照一定的顺序重新排列成为有序的序列。.如何进行排序，特别是高效地处理进行排序是计算机应用中的主要课题之一。

由于待排序的记录数量不同，使得排序过程中能涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序的记录数量很大，以致内存不能一次容纳全部记录，在排序过程中尚需要对外存进行访问的排序过程。

本次课程设计就是研究内部排序中的三个常用的排序方法：直接插入排序、冒泡排序、堆排序。分析排序的实质，排序的应用。应用Java语言采用数组存储结构实现了三个排序算法，利用面向对象编程实现了本排序的综合系统。

关键词：排序，数据处理，时间复杂度

目录

引言 (1)

1 需求分析 (2)

1.1 任务 (2)

1.2 功能模块的划分 (2)

1.2.1 选择排序方法模块 (2)

1.2.2 输入模块 (2)

1.1.3 输出模块 (2)

1.3 排序模块分析 (2)

1.3.1 直接插入排序 (2)

1.3.2 冒泡排序 (2)

1.3.3 堆排序 (3)

2 概要设计 (4)

2.1 程序结构图 (4)

2.2 程序结构图 (5)

3 详细设计 (6)

3.1 开发平台及工具 (6)

3.2 核心算法设计 (6)

3.2.1 直接插入排序 (6)

3.2.2 冒泡排序 (7)

3.2.3 堆排序 (8)

3.3窗口设计 (9)

4 设计结果及分析 (10)

4.1 样例展示 (10)

4.2 数据记录分析 (12)

5 结论 (13)

谢辞 (14)

参考文献 (15)

附录 (16)

引言

由于排序运算在计算机应用中所处的重要地位，熟悉内部排序法的排序过程和各种算法的时间复杂度分析结果及其分析方法，以便在实际应用中，根据实际问题要求，选用合适的排序方法。

本次课程设计目的是通过程序语言设计并实现三种排序算法，直接插入排序、冒泡排序、堆排序的综合系统。通过对不同的数据计量进行实际排序对结构进行分析，找出它们之间的优势和劣势，并结合理论总结在实际运用排序算法过程中需要注意的问题。

1 需求分析

1.1 任务

输入N个乱序的数字，对这些数据分别采用直接插入排序、冒泡排序、堆排序进行排序，输出排序后的数据、数据的个数和排序所花费的时间。分析在相同数据下，采用不同算法所耗时间的差别。

1.2 功能模块的划分

1.2.1 选择排序方法模块

通过点击界面的单选按钮来选择何种算法进行排序，包括的算法有：直接插入排序、冒泡排序、堆排序。

1.2.2 输入模块

在文本框上输入需要排序的数据，数据可以使整型，也可是浮点型。数据之间用空格分开。

1.1.3 输出模块

在输出文本框上输出排序后的数据、数据的个数N还有排序数据所耗的时间。

1.3 排序模块分析

1.3.1 直接插入排序

插入排序重复地将一个新的元素插入到一个拍好序的子线性表中，直到整个线性表排好序。1.3.2 冒泡排序

冒泡排序算法多次遍历数组，在每次遍历中连续比较相邻的元素，如果元素没有按顺序排列，则换它们的值。

1.3.3 堆排序

把n个记录存与向量r之中，把它看成是完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步来处理。

初建堆，从堆的定义出发，当i=1、2、······、[2/n]时应该满足ki,<=k2i+1。所以先取i=[n/2]（它一定是第n个节点的双亲编号），将以i结点为根的子书调整为堆，然后令i=i-1。此时可能会反复调整某些结点，知道i=1为止，堆初步建成。

堆排序，首先输出堆顶的元素（一般是最小值），让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复的步骤。

2 概要设计

2.1 程序结构图

图3.1程序结构图

排序综合系统

生成窗口类

直接插入排序类

堆排序类

冒泡排序类

退出

2.2 程序结构图

开始

生成界面

选择算法，输入

数据

输出数据 直接插入排序类

堆排序类

冒泡排序类

退出

结束

图3.2 程序流程图

3 详细设计

3.1 开发平台及工具

本次课程设计开发的平台是Windows7。使用的程序开发语言是Java，编程环境是JDK8，使用的程序开发软件是eclipse。

3.2 核心算法设计

3.2.1 直接插入排序

假设待排序的记录存放在数组R[n]中，排序过程的某一中间时刻，R被划分为两个子区间[R[1],R[i-1]]和[R[i],R[n-1]]，其中：前一个子区间是已经排好序的有序区；后一个子区间则是当前未排序的部分，不妨称其未无序区.直接插入排序的基本操作是将当前无序区的第一个记录R[i]插入到有序区中适当位置，使得R[1]到R[i]变为新的有序区.

初始时，令i=1，因为一个记录自然是有序的，故R[1]自成为一个有序区，无序区则是R[2]到R[n-1]，然后依次将R[2],R[3],…，插入到当前的有序区中，直至i=n-1时，将R[n-1]插入到有序区为止.

现在的问题是：如何将一个记录R[i](i=2,3,…,n-1)插入到当前的有序区，使得插入后仍保证该区间记录是按关键字有序的.显然，最简单的方法是：首先，在当前有序区R[1]到R[i-1]中查找R[i]的正确插入位置k(1<=k<=i-1)，然后，将R[k]到R[i-1]中记录均后移一个位置，腾出k位置上的空间插入R[i].当然，若R[i]的关键字大于R[1]到R[i-1]中所有记录的关键字，则R[i]就是插入原位置.但是，更为有效的方法是使查找比较操作和记录移动操作交替地进行，具体做法是将待插入记录R[i]的关键字依次与有序区中记录R[j](j=i-1,i-2,…,1)的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；若R[j]的关键字小或等于于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置.因为关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可.

程序清单：

public static double[] insertionSor(double[] list){

for (int i=1;i

double currentElement=list[i];

int k;

for(k=i-1;k>=0&&list[k]>currentElement;k--){

list[k+1]=list[k];

}

list[k+1]=currentElement;

}

return list;

}

3.2.2 冒泡排序

设想排序的记录数组R[0]到R[n-1]垂直竖立，将每个记录R[i]看作是重量为R[i]的气泡.根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡大神轻者在上，重者在下为止.

初始时，R[0]到R[n-1]为无序区，第一趟扫描从该区底部向上依次比较相邻两个气泡的重量，若发现轻者在下，重者在上，则交换两者的位置.本扫描完毕时，最轻的气泡就漂浮到顶上面，即关键字最小的记录被放在最高位置R[0]上.第二趟扫描时，只需扫视R[1]到R[n-1]，扫描完毕时，次轻气泡漂浮到R[1]的位置上.一般地，第i趟扫描时，R[0]到R[i-1]和R[i]到R[n-1]分别为当前的有序区和无序区，扫描仍是从无序区底部向上直至该区顶部，扫描完毕时，该区中最轻气泡漂浮到顶部位置R[i]上，结果是R[0]到R[i]变为新的有序区.

因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中的气泡的重量，所以，整个冒泡排序过程至多需要进行n-1趟排序.但是，若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止.图1.1中，在第四趟（图中第六列）排序过程中就没有气泡交换位置，此时整个文件已达到有序状态.

44 11 11 11 11 11 11 11 11

33 44 22 22 22 22 22 22 22

66 33 44 33 33 33 33 33 33

77 66 33 44 44 44 44 44 44

88 77 66 66 66 55 55 55 55

11 88 77 77 77 66 66 66 66

22 22 88 88 88 77 77 77 77

55 55 55 55 55 88 88 88 88

图3.1 从下往上的冒泡排序

程序清单：

public static void bubbleSor(double[] list){

boolean needNextPass=true;

for(int k=1;k

needNextPass=false;

for(int i=0;i

if(list[i]>list[i+1]){

double temp=list[i];

list[i]=list[i+1];

list[i+1]=temp;

needNextPass=true;

}

}

}

}

3.2.3 堆排序

把n个记录存与向量r之中，把它看成是完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步来处理。

初建堆，从堆的定义出发，当i=1、2、······、[2/n]时应该满足ki,<=k2i+1。所以先取i=[n/2]（它一定是第n个节点的双亲编号），将以i结点为根的子书调整为堆，然后令i=i-1。此时可能会反复调整某些结点，知道i=1为止，堆初步建成。

堆排序，首先输出堆顶的元素（一般是最小值），让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复的步骤。

程序清单：

见附录

3.3窗口设计

窗口实现三大模块，第一模块是堆排序进行选择，第二模块是输入数据，第三模块是输出数据。功能是，首先选择一种排序方法，接着输入需要排序的数据，然后输出排序后的数据，最后输出数据的个数和排序所耗的时间。

图3.2 生成的排序界面

4 设计结果及分析

4.1 样例展示

输入100个数字后分别进行直接排序、冒泡排序、堆排序后的结果如下：

图4.1 直接排序结果

图4.2 冒泡排序结果

图4.1 堆排序结果

4.2 数据记录分析

输入不同的数据量N分别在直接排序、冒泡排序、堆排序算法下进行排序，记录所耗时间如下表：

数据个数

100 500 1000 2000 5000 10000 排序方法

直接排序33,552 127,893 473,678 1,863,526 11,418,786 47,611,698 冒泡排序552,229 779,220 2,461,149 8,015,413 45,312,783 149,498,158 堆排序185,919 258,944 544,334 1,229,982 3,253,375 6,020,442

表4.1 排序耗时（单位：ns）

通过对上表数据进行分析可知，当数据量N比较小时，如N=<1000，直接排序算法排序速度较快，堆排序次之，冒泡排序较慢；当N.>1500时，堆排序算法排序速度较快，直接排序次之，冒泡排序较慢；但数据量较大时，如N>5000，堆排序据有明显的优势，而冒泡排序这时很明显不可取。

在对算法进行分析是我们知道，对于直接排序、冒泡排序、堆排序，它们理论上的耗时分别为O(n*n)、O(n*n)、O(nlogn)，与我们队数据进行分析得出的结论相符。

5 结论

在小组成员的分工合作下，本次课程设计完成了对直接插入排序、冒泡排序、堆排序的算法在Java编程语言下的实现，并整合成了一个可以实际应用的软件。在课程设计的过程中我们不仅对三个算法分别进行了时间复杂度的分析，还我们在所开发的软件上完成了运行测试、数据记录与分析。由此，我们掌握了三种排序算法的优势和劣势，知道了实际运用排序算法过程中需要注意的问题。当然，本课程成设计也存在很多的不足，例如，对输入数据量N的跨度过大，测试数据不够多，对所记录数据分析不够透彻，我们可以通过借助数学软件进行改进。

参与课程设计的成员分工如下：

0000：负责对整个架构进行设计、编写直接排序、冒泡排序、堆排序算法代码、编写软件界面、对课程设计结果进行分析、撰写课程设计报告。

通过对算法设计与分析的学习，并在老师的讲解和指导下，我深刻认识到了在程序设计的过程中算法分析的重要性。正如本次课程设计所展现的，对于解决同一个问题，不同的算法具有不同的优点和缺点。只有深入地理解算法设计与分析并结合实践，我们才能设计出高效的程序。

在本次课程设计过程中，我们深深的感受到了基础知识的重要性.在以后的学习生活中切不可急于求成而忽略了基础的夯实，对一门系统学科，应该扎实的学习他的每一部分知识，充分利用各种实践环节，切实做到理论联系实践，学以致用。

[1] 唐策善，李龙澍，黄刘生，《数据结构-用C语言描述》.高等教育出版社，1995

[2] 李家同，《算法设计与分析导论（英文版）》.机械工业出版社，2007

[3] 梁勇《Java语言程序设计》.机械工业出版社，2016

附录

SortWindonw.java//界面窗口生成类

import javafx.application.Application;

import javafx.stage.Stage;

import https://www.doczj.com/doc/9610942208.html,yout.HBox;

import https://www.doczj.com/doc/9610942208.html,yout.VBox;

import javafx.scene.Scene;

import https://www.doczj.com/doc/9610942208.html,bel;

import javafx.scene.control.RadioButton;

import javafx.scene.control.TextArea;

import javafx.scene.control.TextField;

import javafx.scene.control.ToggleGroup;

import javafx.scene.control.Button;

import javafx.geometry.*;

import java.util.Scanner;

public class SortWindonw extends Application {

RadioButton rd1=new RadioButton("直接插入排序");

RadioButton rd2=new RadioButton("冒泡排序");

RadioButton rd3=new RadioButton("堆排序");

TextArea ta1=new TextArea();//数据输入文本区域

TextArea ta2=new TextArea();//数据输出文本区域

Button bt=new Button("进行排序");//执行排序按钮

TextField textField1=new TextField();//输入数据个数显示文本域

TextField textField2=new TextField();//调用排序算法执行耗时显示文本域String string=new String();//排序算法返回字符串

String string1=new String();//排序后数据字符串

String string2=new String();//排序算法耗时字符串

String string3=new String();//输入数据个数字符串

int n=0;

double time=0;

/**

* 生成界面

*/

@Override

public void start(Stage primaryStage){

HBox hBox=new HBox(90);

HBox hBoxend=new HBox(15);

VBox vBox=new VBox(15);

Label Label1=new Label("请选择一种排序算法");

Label Label2=new Label("请输入需要排序的数据，数据间用空格分开");

Label Label3=new Label("排序后的数据");

Label Label4=new Label(" 数据个数");

Label Label5=new Label(" 排序耗时");

textField1.setPrefColumnCount(4);

textField2.setPrefColumnCount(13);

ToggleGroup group=new ToggleGroup();

rd1.setToggleGroup(group);

rd2.setToggleGroup(group);

rd3.setToggleGroup(group);

ta1.setPrefColumnCount(20);

ta1.setPrefRowCount(3);

ta1.setWrapText(true);

ta2.setPrefColumnCount(20);

ta2.setPrefRowCount(3);

ta2.setWrapText(true);

ta2.setEditable(false);

hBox.getChildren().addAll(rd1,rd2,rd3);

HBox hBox1=new HBox();

hBox1.getChildren().add(bt);

hBox1.setAlignment(Pos.CENTER_RIGHT);

hBoxend.getChildren().addAll(Label4,textField1,Label5,textField2) ;

vBox.getChildren().addAll(Label1,hBox,Label2,ta1,hBox1,Label3,ta2 ,hBoxend);

vBox.setPadding(new Insets(15,15,15,15));

insertionSort();//事件触发

Scene scene=new Scene(vBox,480,380);

primaryStage.setTitle("排序");

primaryStage.setScene(scene);

primaryStage.show();

}

/**主函数*/

public static void main(String[] args) {

https://www.doczj.com/doc/9610942208.html,unch(args);

}

/**

数据结构课程设计-排序

一、问题描述 1、排序问题描述 排序是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。简单地说，就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法，分析了排序的实质，排序的应用，排序的分类，同时进行各排序方法的效率比较，包括比较次数和交换次数。我们利用java语言来实现本排序综合系统，该系统包含了：插入排序、交换排序、选择排序、归并排序。其中包括： （1）插入排序的有关算法：不带监视哨的直接插入排序的实现； （2）交换排序有关算法：冒泡排序、快速排序的实现； （3）选择排序的有关算法：直接选择排序、堆排序的实现； （4）归并排序的有关算法：2-路归并排序的实现。 2、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 本人设计的是交换排序，它的基本思想是两两比较带排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 冒泡排序的基本思想是：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的”，关键字值较大的纪录看作“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮；较大关键字值的纪录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。 冒泡排序的步骤： 1)置初值i=1； 2)在无序序列｛r[0],r[1],…，r[n-i]｝中，从头至尾依次比较相邻的两个记录r[j] 与r[j+1]（0<=j<=n-i-1）,若r[j].key>r[j+1].key，则交换位置； 3)i=i+1； 4)重复步骤2）和3），直到步骤2）中未发生记录交换或i=n-1为止； 要实现上述步骤，需要引入一个布尔变量flag，用来标记相邻记录是否发生交换。 快速排序的基本思想是：通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。 快速排序步骤： 1)设置两个变量i、j，初值分别为low和high，分别表示待排序序列的起始下

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

中南大学数据结构与算法第10章内部排序课后作业答案

第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937

(2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）

算法排序问题实验报告

《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0] 小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low=privotkey do high←high-1 A[low]←A[high] //将比枢轴记录小的记录移到低端 while low

拓扑排序课程设计报告

数据结构课程设计 设计题目：有向图拓扑排序 专业：信息与计算科学 学号：021240616 姓名：黄秋实 指导教师：文军 2013年11月28日

数据结构课程设计 ----拓扑排序 一需求分析 1.问题描述 本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序列 拓扑排序的基本思想为： 1).从有向图中选一个无前驱的顶点输出；2).将此顶点和以它为起点的弧删除；3). 重复1),2)直到不存在无前驱的顶点；4). 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。 2.拓扑排序有向图拓朴排序算法的基本步骤如下：①从图中选择一个入度为0的顶点，输出该顶点；②从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度-1）；③重复执行①、②直到所有顶点均被输出，拓朴排序完成或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）。 3基本要求 (1) 输入的形式和输入值的范围； 首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。 (2) 输出的形式； 首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。 (3) 程序所能达到的功能； 因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。 二概要设计 1. 算法中用到的所有各种数据类型的定义 在该程序中用邻接表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。 拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。 2.各程序模块之间的层次调用关系 第一部分，void ALGraph *G函数构建图，用邻接表存储。这个函数没有调

综合课程设计

可用C++(Visual C++ 6.0),JA V A（JSP，STRUTS），C#(https://www.doczj.com/doc/9610942208.html, ，Visual Studio 2005)，试题目而定。 1、综合购物频道（限最多3人选） 项目描述：是一个在线销售系统，是一个B-C模式的电子商务系统，由前台的B/S模式购物系统和后台的C/S模式的管理系统两部分组成。该电子商务系统可以实现会员注册、浏览商品、查看商品详细信息、选购商品、取消订单和查看订单等功能，前台系统的详细功能。目的：了解项目开发的一个基本流程以及如何运用现行的框架搭建一个大型的综合型系统2、某大型企业内部OA（限最多3人选） 项目描述：采用网络办公自动化系统，不仅能快速提高企业的运作效率，节省大量的办公费用，能全面提升企业的核心竞争力和生产力以及提高工作效率。该企业内部OA系统采用模型组件与WEB技术结合的方式，具有强大的功能，广泛的适用性、可靠安全性和可扩展性。目的：学习运用当前热门的前台技术。 3、产品展示厅（限最多3人选） 项目描述： 在互联网发达的今天，当您想客户宣传自己的产品时，最好的方式是拥有自己的网站，通过网络来传播和展示您的产品信息。产品展示系统，为客户详细介绍自己的产品，提供了一个功能强大的平台。 系统界面友好、功能强大、操作简便，用户可以方便迅速掌握系统的操作。 4人事管理系统（限最多3人选） 项目描述：人事档案完整资料、人事分类管理（员工户口状况、员工政治面貌、员工生理状况、员工婚姻状况、员工合同管理、员工投保情况、员工担保情况）、考勤管理、加班管理、出差管理、人事变动管理（新进员工登记、员工离职登记、人员变更记录）、员工培训管理（员工培训、员工学历）、考核奖惩、养老保险等几大模块。系统具有人事档案资料完备，打印灵活，多样、专业的报表设计，灵活的查询功能等特点。 主要技能：掌握项目的开发流程：需求分析、详细设计、测试等；熟悉VC的多文档的开发技能和技巧；利用ADO技术操作SQL Server数据库；掌握数据库的开发和操作技能。 5、即时通讯系统（限最多3人选） 项目描述：系统采用UDP协议，具有：收发在线和离线消息、添加/删除好友、服务器端存储好友列表、在客户端存储好友资料和聊天记录、添加/删除好友组、可以群发消息、收发文件等功能。 主要技能：掌握项目的开发流程：需求分析、详细设计、测试等；熟悉VC的网络通信的开发技能和技巧，包括：TCP和UDP协议、线程等；利用ADO技术操作SQL Server数据库； 6、推箱子（限最多3人选） 【规则】本游戏的目的就是把所有的箱子都推到目标位置上。箱子只能推动而不能拉动。一次只能推动一个箱子。 经典的推箱子是一个来自日本的古老游戏,目的是在训练你的逻辑思考能力。在一个狭小的仓库中,要求把木箱放到指定的位置,稍不小心就会出现箱子无法移动或者通道被堵住的情况,所以需要巧妙的利用有限的空间和通道~！ 7、贪吃蛇（限最多3人选） 【规则】： A 用键盘的方向键控制蛇的上下左右移动。 B 游戏分为三种难度，SLUG为慢速，每吃一朵花得1分；WORM 为中速，每吃一朵花得2分；PYTHON为快速，每吃一朵花得3分。 C 游戏目标：操纵屏幕上那条可爱的小蛇，在黑框中不停吃花，而每吃一朵

《数据结构与算法分析》课程设计：顺序表、单链表、顺序栈、查找、排序算法

*******大学 《数据结构与算法分析》课程设计 题目：数据结构上机试题 学生姓名： 学号： 专业：信息管理与信息系统 班级： 指导教师： 2014年04月

目录 一、顺序表的操作 (2) 【插入操作原理】 (2) 【删除操作原理】 (2) 【NO.1代码】 (3) 【运行截图演示】 (7) 二、单链表的操作 (10) 【创建操作原理】 (10) 【插入操作原理】 (10) 【删除操作原理】 (10) 【NO.2代码】 (11) 【运行截图演示】 (20) 三、顺序栈的操作 (25) 【数值转换原理】 (25) 【NO.3代码】 (26) 【运行截图演示】 (30) 四、查找算法 (32) 【顺序查找原理】 (32) 【折半查找原理】 (32) 【NO.4代码】 (33) 【运行截图演示】 (38) 五、排序算法 (40) 【直接插入排序原理】 (40) 【快速排序原理】 (40) 【NO.5代码】 (41) 【运行截图演示】 (46)

一、顺序表的操作 （1）插入元素操作：将新元素x 插入到顺序表a 中第i 个位置； （2）删除元素操作：删除顺序表a 中第i 个元素。 【插入操作原理】 线性表的插入操作是指在线性表的第i-1个数据元素和第i 个数据元素之间插入一个新的数据元素，就是要是长度为n 的线性表： ()11,,,,,i i n a a a a -………… 变成长度为n+1的线性表： ()11,,,,,,i i n a a b a a -………… 数据元素1i a -和i a 之间的逻辑关系发生了变化。 （其【插入原理】在课本P23的算法2.3有解释） 【删除操作原理】 反之，线性表的删除操作是使长度为n 的线性表： ()111,,,,,,i i i n a a a a a -+………… 变成长度为n-1的线性表： ()111,,,,,i i n a a a a -+………… 数据元素1i a -、i a 和1i a +之间的逻辑关系发生变化，为了在存储结构上放映这个变化，同样需要移动元素。 （其【删除原理】在课本P24的算法2.4有解释）

数据结构课程设计报告---几种排序算法的演示(附源代码)

? & 数据结构课程设计报告 —几种排序算法的演示( ； 时间：2010-1-14 … 一需求分析

运行环境 Microsoft Visual Studio 2005 程序所实现的功能 对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。 程序的输入（包含输入的数据格式和说明） % <1>排序种类三输入 <2>排序数的个数的输入 <3>所需排序的所有数的输入 程序的输出（程序输出的形式） <1>主菜单的输出 <2>每一趟排序的输出，即排序过程的输出 " 二设计说明 算法设计思想 <1>交换排序（冒泡排序、快速排序） 交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 <2>插入排序（直接插入排序、折半插入排序） % 插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 <3>选择排序（简单选择排序、堆排序） 选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 <4>归并排序（两路归并排序） 两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为

教学计划安排检验程序(拓扑排序)报告书

设计题目： 示例数据：输入：学期数：5，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6 输出：第1学期应学的课程：v1 v9 第2学期应学的课程：v2 v4 v10 v11 第3学期应学的课程：v3 v6 v12 第4学期应学的课程：v5 v8 第5学期应学的课程：v7

一需求分析 1.1 引言 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。 一般应用：拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。 1.2 拓扑排序的了解 ①.问题的描述 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之

《HTML网页编程技术综合课程设计》教学实施方案

《HTML网页编程技术综合课程设计》教学实施方案

————————————————————————————————作者：————————————————————————————————日期：

《网页编程技术综合课程设计》教学方案 一、课程设计目标 通过该课程设计综合应用本学期所学的网页制作知识，全面建立对网站的认知，建立网站设计与网页制作的基本思想；学会网站功能规划、网站布局、网页制作、网页配色等的基本技巧，掌握网页制作与网站设计相关软件的使用方法；通过课程设计教学环节能够制作有一定实用性的网站；能解决一些实际应用问题并以此为基础进一步扩展到相关的学科上；通过本课程设计提高网页的审美意识；通过团队合作制作网站，培养团队协作精神，初步了解软件企业开发软件系统模式，为将来适应工作打开良好的基础。 二、设计要求 1．本课程设计分小组进行，各小组成员原则上2~4人，不得超过4人,由小组长协调分工,每个组员充分发挥团队协作精神。 2．自选主题，使用Dreamweaver网页设计与制作软件，设计并制作一个内容完整、结构规范合理的静态网站，要求选取内容健康，网站中出现一定数量的图像和多媒体。网站主题应大小适中、内容健康、具有时代气息；网站提供的信息应与网站主题相符合, 主题突出、内容丰富； 3.页面设计合理、美观，有创意，适用于各种显示器的分辨率和颜色。 4.每个页面都要求有导航条和页脚信息，需要将这些信息制作成库项目，然后根据需要将之插入到模板或其它页面中。各个页面都要有标题，而且布局要合理、美观、大方。布局网页时要尽量主流布局方法（必须使用Div、表格等），并要有一定复杂度。 5.页面中需要有文字、图像、多媒体、超链接等，要求达到图文并茂的效果。所使用的文字的大小、字体和颜色要认真处理，除非特殊需要，不能出现空链接，文字不能简单用截图代替；所需图像和多媒体素材尽量自己设计，如有下载，自己必须再作处理，不得直接使用现有商业网站标志。 6. 为了保证页面的设计效果更好地兼容各种浏览器以及便于改版，要求用独立的CSS文件设置页面内容格式。 7.为主页添加背景音乐。 8.需要使用一定量的JavaScript脚本，使网页具有一定的交互功能。每小组必须制作一个表单，表单输入内容需要使用正则表达式进行验证。

排序算法课程设计

排序算法课程设计 专业 班级 学号 姓名 指导老师

一：课程设计的目的 1.掌握各种排序的基本思想 2.掌握各种排序的算法实现 3.掌握各种排序的算法优劣分析花费的时间计算 4.掌握各种排序算法所适用的不同场合。 二：课程设计的内容 （1）冒泡、直插、选择、快速、希尔、归并、堆排序算法进行比较； （2）待排序的元素的关键字为整数。其中的数据用伪随机产生程序产生（如10000个,1000个），再使用各种算法对其进行排序，记录其排序时间，再汇总比较；（3）将每次测试所用的时间，用条形图进行表示，以便比较各种排序的优劣。 三：课程设计的实现 （1）直接插入排序 #include typedef int keytype; struct datatype { keytype key; }; /* int rand(void); void srand(unsigned int seed ); */ #include #include #include #include void InsertSort (datatype a[], int n) //用直接插入法对a[0]--a[n-1]排序 { int i, j; datatype temp; for(i=0; i

while(j > -1 && temp.key <= a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } } void main() { /*srand((unsigned)time(NULL));// 随机种子*/ /*time_t t; srand((unsigned)time(&t));*/ time_t t1,t2; srand((unsigned)GetCurrentTime()); datatype num[10000]; t1=GetCurrentTime(); for(int i=0;i<10000;i++) { num[i].key=rand(); } int n=10000; InsertSort(num,n); for(int j=0;j<10000;j++) cout< /* int rand(void); void srand(unsigned int seed ); */ #include #include #include #include typedef int keytype; struct datatype { keytype key;

几种常见内部排序算法比较

常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析.

详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key

数据结构课程设计排序算法总结

排序算法： (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 （1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。 （2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。 （3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；……以此类推，直至的到一个递增的表。 (4)简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。 【算法实现】 （1）直接插入排序： void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i]L.elem[0];j--) L.elem [j+1]=L.elem [j]; L.elem [j+1]=L.elem[0]; } } （2）折半插入排序：

数据结构课程设计报告

《数据结构课程设计》报告 题目：课程设计题目2教学计划编制 班级：700 学号：09070026 姓名：尹煜 完成日期：2011年11月7日

一．需求分析 本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。 （一）输入形式：文件 文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。 格式：第一行给出课程数量。大于等于0的整形，无上限。 之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。 课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。 先给出边的数量。大于等于0的整形。 默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。 例： （二）输出形式：1.以图形方式显示有向无环图

2.以文本文件形式存储课程安排 （三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系） 以图形方式输出课程的有向无环图。 拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果）

二．概要设计 数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个 是为了实现核心算法拓扑排序。 2.ArrayList list用来存储课程信息。DrawInfo类是一个辅助画图的类，其中 包括成员变量num、name、shuxing、xuefen分别代表课程的编号、名称、属性、 学分。ArrayList是一个DrawInfo类型的数组，主要用来在ReadFile、DrawG、DrawC、SaveFile、Window这些类之间辅助参数传递，传递课程信息。 3.Class DrawInfo, 包括int num;String name;String shuxing;float xuefen;四个成员变量。 4.Class Edge包括int from;int to;double weight;三个成员变量。 5.Class Vertex包括int value一个成员变量。 主要程序的流程图： //ReadFile.java

数据结构课程设计之综合排序代码及使用方法

题目1： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求： 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结 果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 代码如下： #include //标准输入输出头文件 #include //定义杂项函数及内存分配函数 #include //字符串处理 #include //定义关于时间的函数 #define N 20000 clock_t Start,Now;//时钟 void Wrong()//错误输出 { printf("\n*****按键错误!请重新输入*****\n"); getchar();//从标准输入获取字符并返回下一个字符 } void change(int a[])//十个一行输出 { int i; system("cls");//清除之前的操作 for(i=0;i

数据结构课程设计(内部排序算法比较 C语言)

课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------|

|-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构课程设计报告---几种排序算法的演示(附源代码)

数据结构课程设计报告 —几种排序算法的演示 时间：2010-1-14 一需求分析 运行环境 Microsoft Visual Studio 2005

程序所实现的功能 对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。 程序的输入（包含输入的数据格式和说明） <1>排序种类三输入 <2>排序数的个数的输入 <3>所需排序的所有数的输入 程序的输出（程序输出的形式） <1>主菜单的输出 <2>每一趟排序的输出，即排序过程的输出 二设计说明 算法设计思想 <1>交换排序（冒泡排序、快速排序） 交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 <2>插入排序（直接插入排序、折半插入排序） 插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 <3>选择排序（简单选择排序、堆排序）

选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 <4>归并排序（两路归并排序） 两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。 程序的主要流程图