一 需求分析
运行环境
Microsoft Visual C++ 6.0
程序所实现的功能
对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归
并排序算法的演示,并且输出每一趟的排序情况。
程序的输入(包含输入的数据格式和说明)
<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 的有序序列。
评论3
最新资源