文档介绍：数据结构实验报告
实验名称: 实验四——排序
学生姓名:
班级:
班内序号:
学号:
日期: 2013年12月16日
实验要求
使用简单数组实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序(选作)
7、归并排序(选作)
8、基数排序(选作)
9、其他
要求:
1、测试数据分成三类:正序、逆序、随机数据
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。
2. 程序分析
存储结构
使用最简单的一维数组存储待排序的数据。共使用三个数组,一个用来构造正序数组,一个是逆序数组,还有一个是随机数组。每种排序使用的数组都是具有相同初始值的,因而使得试验结果具有可比较性。
  
 插入排序算法
插入排序的思想是:每次从无序区取一元素将其添加到有序区中。
 希尔排序算法
 希尔排序是一种缩小增量排序的算法,首先将待排序元素集按照一定间隔分成多个子集,分别对这些子集进行直接插入排序,整个序列部分有序。然后缩小间隔,在进行直接插入排序,直到间隔为1,此时,整个序列已全部有序。
 起泡排序 
起泡排序的思想是:两两比较相邻的元素,如果反序,则交换次序,直到没有反序的元素为止。 
在此思想指导下①首先将待排序元素划分为有序区和无序区,初始状态有序区为空,无序区所有待排序素;             
②对无序区从前向后依次将相邻元素关键码进行比较,若反序,则交换             
③重复执行
②直到无序区中没有元素。     
 
2,2,4,1一趟快速排序算法自然语言描述如下 
① 选取区间第一个元素作为轴值 
② 读取区间首尾坐标,并将其左右侧待比较元素 
③ 右侧扫描:从后向前找到第一个比轴值小的元素,和左侧待比较元素交换(左侧第一个带比较元素为轴值) 
④ 左侧扫描:从前向后找到第一个比轴值大的元素,和右侧待比较元素交换 
⑤ 重复②③,直到左右两侧带比较元素的坐标相等 其c++描述如下
:
 
选择排序自然语言描述如下: 
① 在r[1]~r[n]待排序元素序列中选出最小记录,将其与第一个元素r[n]交换
 ② 在r[2]~r[n]待排序元素序列中选出最小记录,将其与第一个元素r[i]交换 
………… 
③ 直至r[n-1]~r[n]
 C++描述如下: 
 
,按照小根堆的定义建立堆的算法如下 
  说明:根节点存放在r[1]中,r[i]的左孩子为r[2*i],右孩子为r[2*i+1] 
    
①输出堆顶元素 
②将堆中最后一个元素移至堆顶,并将剩余元素调整为小根堆    
③反复执行①②两个元素,直到堆中只有一个元素 
 
 
3. 程序运行结果
测试主函数运行流程图:
源代码
#include<iostream>
#include""
using namespace std;
void InsertSort(int r[], int n)//直接插入排序
{
int count1 = 0, count2 = 0;//分别用来记录插入排序比较和移动次数的计数器
for (int i = 2; i <= n - 1; i++)
{
if (r[i]<r[i - 1])//查找插入位置
{
r[0] = r[i]; //设置哨兵
count2++; //移动次数加1
int j;
for (j = i - 1; count1++, r[0]<r[j]; j--) //寻找插入位置
{
r[j + 1] = r[j]; //元素后移
count2++; //移动次数加1
}
r[j + 1] = r[0];//插入记录
count2++;
}
else count1++;//此时虽然没有移动但是已经进行了一次比较
}
cout << "比较" << count1 << "移动" << count2;
}
void ShellSort(int