• / 6
  • 下载费用:10 金币  

实验八 排 序.doc

关 键 词:
实验八 排 序.doc
资源描述:
1实验八 排 序一、 实验目的和要求1 掌握各种排序方法的排序过程。2 了解一些排序算法的实现(如插入排序、选择排序、冒泡排序、快速排序、堆排序等) 。二、 基本概念排序就是把一组元素按照某个域的值的递增或递减的次序重新排列的过程。(1) 直接插入排序首先令排序表中的第 1 个记录有序,然后将第 2 个记录插入到有序表中合适位置,有序表就增加到了两个元素。再将第 3 个记录插入到有序表中的合适位置,依此类推,直到表中元素全部有序。(2)希尔排序取一个整数 d,将全部记录 n 分为 d 个子序列,将所有距离为 d 的记录放在同一个子序列中;在每个子序列内分别施行直接插入排序;然后缩小间隔d,重复上述子序列划分和排序,直到最后取 d = = 1,将所有记录放在同一个序列中排序为止。 (3) 简单选择排序首先在所有的记录中选出关键字最小的记录,把它与第一个记录交换,然后在其余的记录中再选出关键字最小的记录,与第二个记录交换,依次类推,直到所有记录排序完成。(4)冒泡排序在待排序的记录序列中,从第一个待排序记录开始,依次比较两个相邻记录的关键字,如果是反序,则将两个记录进行交换。这样,在一趟比较完毕后,关键字最大的记录就被交换到最后。然后对前面 n-1 记录执行上述过程。(5)快速排序在待排序记录序列中任取一个记录作为枢轴,以它作为比较的“基准” ,将待排序划分为左右两个子序列,使行左边子序列中记录的关键字均小于等于枢轴,右边子序列中各记录的关键字都大于等于枢轴。对所划分的两组分别重复上述过程,直到各个序列的记录个数为 1 时为止。 。三、 程序例题例题 8.1 编写一程序要求能够实现直接插入排序、希尔排序、简单选择排序、冒泡排序和快速排序,并用测试函数对其进行测试。算法设计:根据题目要求,设计 5 个排序函数,实现各种排序功能。2(1) 直接插入排序函数 InsSort( ):设计思想,首先令排序表中的第 1 个记录有序,然后将第 2 个记录插入到有序表中合适位置,有序表就增加到了两个元素。再将第 3 个记录插入到有序表中的合适位置,依此类推,直到表中元素全部有序。(2) 希尔排序函数 ShellSort( ):设计思想,取一个整数 d,将全部记录 n分为 d 个子序列,将所有距离为 d 的记录放在同一个子序列中;在每个子序列内分别施行直接插入排序;然后缩小间隔 d,重复上述子序列划分和排序,直到最后取 d = = 1,将所有记录放在同一个序列中排序为止。(3) 简单选择排序函数 SelectSort( ):首先在所有的记录中选出关键字最小的记录,把它与第一个记录交换,然后在其余的记录中再选出关键字最小的记录,与第二个记录交换,依次类推,直到所有记录排序完成。(4)冒泡排序函数 BubbleSort( )。(5)快速排序函数 QuickSort(int low, int high)。算法实现:#include “iostream.h“#define MaxSize 100typedef int DataType;class SeqList{ DataType list[MaxSize];int length;public:SeqList( ) {length = 0;}void SLCreat(int n); //创建顺序表void InsSort( ); //直接插入排序void ShellSort( ); //希尔排序void SelectSort( ); //简单选择排序void BubbleSort( ); //冒泡排序void QuickSort( ); //快速排序void QuickSort(int low, int high); //快速排序int partition(int i, int j);void SLPrint( ); //将顺序表显示在屏幕上};//创建顺序表void SeqList::SLCreat(int n);{ DataType x;length = 0;cout x;list[i] = x;length++;}}//直接插入排序3void SeqList::InsSort( ){ SLCreat(5);DataType x;int i, j;for(i = 0; i = 0; j--)if(x = 1; d/= 2){ //按不同分量进行排序for(i = d; i = 0; j-= d){ if(x = i; j--)if(list[j] = pivotkey) --j;if(i ch;switch(ch){ case 1: myList1.InsSort( ); break;case 2: myList2.ShellSort( ); break;case 3:
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:实验八 排 序.doc
链接地址:https://www.weizhuannet.com/p-9475377.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开