数据结构六种常见的排序方法(超详细图解内附代码) |
您所在的位置:网站首页 › java排序的几种方法 › 数据结构六种常见的排序方法(超详细图解内附代码) |
这里写目录标题
实验目的实验内容实验要求六种排序方法细解直接插入排序冒泡排序简单选择排序希尔排序快速排序归并排序
六种排序好坏分析代码段运行结果
实验目的
1.能够清楚表述主要内部排序方法的设计思路。 2.能够用高级语言编写主要内部排序算法在计算机中的实现。 3.能够分析比较主要的内部排序方法之间的性能特点。 实验内容编程实现统计直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序和归并排序算法在运行时的比较次数和移动次数。 实验要求1.输入同样一组整型数据,作为待排序记录的关键字序列。 2.在进行直接插入排序、冒泡排序、简单选择排序的同时统计在排序过程中对关键字的比较次数和移动次数,并分别输出排序前的数据序列和排序后的数据序列及其统计结果。 3.在进行希尔排序、快速排序和归并排序的同时统计在排序过程中对关键字的比较次数和移动次数,并分别输出排序前的数据序列和排序后的数据序列及其统计结果。 4.在主程序中设计一个菜单,使用户可选择执行其中的任何一种或几种排序,并查看排序结果。 六种排序方法细解 直接插入排序
一第一趟为例,引入一个下标min,假设第一个元素最小,min=1,r[min]与r[2]~r[6]的所有元素逐一比较,发现最小的仍是r[1]则此时r[1]进入有序队列,然后将剩下的元素再进行选择排序。 希尔排序
下面展示六个排序的代码段(内附比较次数和交换次数)。 #include #include #include #define TRUE 1 #define FALSE 0 #define MAXSIZE 80 //顺序表的最大长度 typedef int KeyType; // 将关键字类型定义为整型 typedef int InfoType; // 将其它数据项类型也定义为整型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RedType; // 记录类型 typedef struct { RedType r[MAXSIZE+1]; //一般情况将r[0]闲置 int length; // 顺序表长度 } SqList; //顺序表的类型 struct { int cpn; //记录比较次数 int mvn; //记录移动次数 } cm[6]; //全局变量 void Sort_Insert(SqList &L) //带监视哨的直接插入排序算法 { int i,j; for(i=2; i0&&cm[0].cpn++,L.r[0].key1&&change; --i) { //控制做n-1趟排序 change=FALSE; //每趟排序开始时设置交换标志变量值为假 for(j=1; jL.r[j+1].key) { //比较关键字值时,比较次数加1 temp=L.r[j]; //相邻的两个记录交换 L.r[j]=L.r[j+1]; L.r[j+1]=temp; cm[1].mvn+=3; //移动次数加3 change=TRUE; }//if }// for i printf("比较次数为%d\n",cm[1].cpn); printf("移动次数为%d\n",cm[1].mvn); } void Sort_Select(SqList &L) //对表L进行直接选择排序 { for(int i=1; i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |