数据结构实训报告
实验名称：数据结构
题目：部排序比较
专业：班级：：学号：实验日期：
一、实验目的：通过随机数据比较各部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。训练学生综合设计算法能力。
二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。
三、实验容
1、待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于3种；
2 、待排序的元素的关键字为整数；
3 、比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。
4、演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。
5、最后要对结果作简单的分析。
6、测试数据：用伪随机数产生程序产生。
四、实验编程结果或过程：
1. 数据定义
typedef struct { KeyT ype key; }RedT ype; typedef struct { RedT ype r[MAXSIZE+1]; int length;
}SqList;
2. 函数如下，代码详见文件“排序比较.cpp”
int Create_Sq(SqList &L)
void Bubble_sort(SqList &L)//冒泡排序
void InsertSort(SqList &L)//插入排序
void SelectSort(SqList &L) //简单选择排序
int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法
void QuickSort(SqList &L)
void ShellInsert(SqList &L,int dk)//希尔排序
void ShellSort(SqList &L,int dlta[ ])
3. 运行测试结果，运行结果无误，如下图语速个数为20
元素个数为100
错误调试无。
影响排序的因素：
1、待排序的记录数目n 的大小。
2、记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。
3、关键字的结构及其分布情况。
4、对排序稳定性的要求
五、实验总结：
（1）实验中的存在问题和提高
1、存在问题：程序有待增强。
2、提高：界面处理简洁。
（2）收获与体会：
1、随机数的生成；
2、排序的算法的比较次数与移动次数的计算
3、各种排序的算法
附录源程序
/*一.选择排序算法：
算法基本原理：
一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，否则交换min与i位置上数。
算法实现：*/
#include
//选择排序，如果第一个数字小于后面的则向后移动，依次类推
//该排序时不稳定的，时间复杂度是N平方
int main()
{
int array[10] = {112,4,2,3,5,33,6,7,8,9};//定义一个数组
int length = sizeof(array)/sizeof(array[0]);//得到数组的长度
int min, k=0, s=0, i=0, j=0;//k保存临时结果，s，i，j为循环变量
//选择排序开始
for(i=0;i{min=i;
for(j=i+1;j{
if(array[i]>array[j])
{min=j;
}
if(min!=i)
{k=array[i];
array[i]=array[j];
array[j]=k;
}
}
}
//选择排序结束，输出显示排序的结果
for(s=0; s{
printf("%d \n",array[s]);
}
return 0;
}
/*二.冒泡排序
算法基本原理：
对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。
算法实现：*/
#include
//冒泡排序,开始的时候两个数进行比较，大的向后小的向前，第一次比较很容易的就把最大的一个数字放到了最后小的呢，继续向前，第二次当然也找到了第二个大的，放到倒数第二的位置，如此下去便可。这个是优化的冒泡排序方法，让k=j保存最后的那个数的下标，这样k后面的数都是排序好的了,这个排序是稳定的，时间复杂度是N平方
int main()
{
int array[10] = {1,2,11,22,33,4,23,234,4,6};
int length = sizeof(array)/sizeof(array[0]);
int k=0, s=0, i=0, j=0, m=0;
//冒泡排序开始
for(i = length-1;i>0;i=k)
{
for(j=0, k=0;j{
if(array[j]>array[j+1])//把比较出来大的数据向后移动
{
m=array[j];
array[j]=array[j+1];
array[j+1]=m;
k=j;
}
}
}
//冒泡排序结束，输出显示排序的结果
for(s=0; s{
printf("%d \n",array[s]);
}
return 0;
}
/*三.快速排序
算法基本原理：
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法实现：*/
#include
//快速排序开始，使用递归方法，取其中一个数（任意基本上都是以第一个为准），先从后面比较，如果这个数比后面的大交换之，如果不大继续比较直到大为止，如果大，
