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

数据结构课程设计报告

—几种排序算法的演示

时间: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的有序序列。

程序的主要流程图

退出系统 输出排序结果 直插 折半 冒泡 选择 快排 堆排 归并 选择排序方法 进入主菜单 开始

程序的主要模块(要求对主要流程图中出现的模块进行说明) 程序的主要模块主要分为主菜单模块和排序算法演示模块。

<1>主菜单

主要功能:程序运行时,可使运行者根据提醒输入相关操作,从而进入不同的排序方法或者退出。

<2>排序方法及输出

根据运行者对排序的不同选择,进入排序过程

a.直接插入排序:根据直接排序的算法,输出排序过程 b.折半插入排序:根据折半插入的算法,输出排序过程 c.冒泡排序:根据冒泡排序算法,输出排序过程