《数据结构实验四报告排序》由会员分享，可在线阅读，更多相关《数据结构实验四报告排序（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验名称： 实验四 排序学生姓名： 班 级 ： 班内序号：学 号： 日 期： 2013 年 12 月 16 日1 实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为 3次移动） 。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对 2和 3的结果进行分析，验证上述各种算法的
2、时间复杂度编写测试 main()函数测试线性表的正确性。2. 程序分析2.1 存储结构使用最简单的一维数组存储待排序的数据。共使用三个数组，一个用来构造正序数组，一个是逆序数组，还有一个是随机数组。每种排序使用的数组都是具有相同初始值的，因而使得试验结果具有可比较性。2.2关键算法分析 2.2.1 插入排序算法插入排序的思想是：每次从无序区取一元素将其添加到有序区中。2.2.2 希尔排序算法希尔排序是一种缩小增量排序的算法，首先将待排序元素集按照一定间隔分成多个子集，分别对这些子集进行直接插入排序，整个序列部分有序。然后缩小间隔，在进行直接插入排序，直到间隔为 1，此时，整个序列已全部有序。2
3、.2.3 起泡排序 起泡排序的思想是：两两比较相邻的元素，如果反序，则交换次序，直到没有反序的元素为止。在此思想指导下首先将待排序元素划分为有序区和无序区，初始状态有序区为空，无序区所有待排序素； 对无序区从前向后依次将相邻元素关键码进行比较，若反序，则交换 重复执行直到无序区中没有元素。 2.2.4快速排序算法 2,2,4,1一趟快速排序算法自然语言描述如下 选取区间第一个元素作为轴值 读取区间首尾坐标，并将其左右侧待比较元素 右侧扫描：从后向前找到第一个比轴值小的元素，和左侧待比较元素交换（左侧第一个带比较元素为轴值） 左侧扫描：从前向后找到第一个比轴值大的元素，和右侧待比较元素交换 重复
4、，直到左右两侧带比较元素的坐标相等 其c+描述如下2.2.4.2完整的快速排序算法如下：2.2.5选择排序算法 选择排序自然语言描述如下： 在r1rn待排序元素序列中选出最小记录，将其与第一个元素rn交换 在r2rn待排序元素序列中选出最小记录，将其与第一个元素ri交换 直至rn-1rnC+描述如下： 2.2.6堆排序 2.2.6.1堆的建立，按照小根堆的定义建立堆的算法如下 说明：根节点存放在r1中，ri的左孩子为r2*i,右孩子为r2*i+1 2.2.6.2调整数组为升序排列 输出堆顶元素 将堆中最后一个元素移至堆顶，并将剩余元素调整为小根堆 反复执行两个元素，直到堆中只有一个元素 2.2
5、.6.2堆排序完整算法如下 3. 程序运行结果测试主函数运行流程图：开 始初 始 化 数 组 ， 计数 器排 序 ， 输 出 比 较次 数 和 移 动 次 数结 束 源代码#include#includetime.husing namespace std;void InsertSort(int r, int n)/直接插入排序 int count1 = 0, count2 = 0;/分别用来记录插入排序比较和移动次数的计数器 for (int i = 2; i = 1; d = d / 2) /以增量为d进行直接插入排序 for (i = d + 1; i0 & r0rj + 1) /相邻元素
6、比较 temp = rj; /交换rj和rj+1 rj = rj + 1;rj + 1 = temp;pos = j; /记录每一次发生记录交换的位置 当j=0时说明一次比较也没有了 即已经全部有序了 count2 = count2 + 3; /一个交换语句为一次移动 共移动了次 cout rj)break; /根结点已经大于左右孩子中的较大者则结束循环 elsetemp = ri;ri = rj;rj = temp; /将根结点与结点j交换 i = j;j = 2 * i + 1; /下一个被筛结点位于原来结点j的位置 count2 = count2 + 3; /移动次数加 void Hea
7、pSort(int r, int n)/堆排序 int count1 = 0, count2 = 0; /计数器 计比较和移动次数 int i;int temp;for (i = n / 2; i = 0; i-) /初始建堆 从下向上(从最后一个分支结点开始)的过程(整体) Sift(r, i, n, count1, count2);for (i = n - 1; i0; i-) /重复执行移走堆顶及重建堆的操作 temp = ri; /将堆顶元素与将堆顶记录和当前未经排序子序列r1.i中最后一个记录相互交换 ri = r0;r0 = temp; /完成一趟排序 输出记录的次序状态 Sift
8、(r, 0, i - 1, count1, count2); /重建堆 cout 比较 count1 移动 count2;void Newarray(int a, int b)/产生顺序、逆序及随机数组 a0 = 0;b0 = 0;for (int s = 1; s501; s+)as = s; /顺序数组bs = 501 - s; /逆序数组void main()srand(time(NULL);int c501;c0 = 0;cout 随机数组： ;for (int s = 1; s 501; s+)cs = rand() % 50 + 1;cout cs ;const int num =
9、 501; /赋值 最大的数组的容量 int anum;int bnum;int c1num;a0 = 0;b0 = 0; Newarray(a, b);cout 顺序数组:;for (int j = 1; jnum; j+)cout aj ;cout endl;cout 逆序数组:;for (int j = 1; jnum; j+)cout bj ;cout endl;cout endl;cout 排序方式 正序 逆序 随机endlendl;cout 直接插入排序 ;Newarray(a, b);int count1 = 0, count2 = 0;InsertSort(a, num);co
10、ut ;InsertSort(b, num);cout ;InsertSort(c, num);count1 = 0, count2 = 0;cout endlendl;cout 希尔排序 ;Newarray(a, b);ShellSort(a, num);cout ;ShellSort(b, num);cout ;ShellSort(c, num);count1 = 0, count2 = 0;cout endlendl;cout 起泡排序 ;Newarray(a, b);BubbleSort(a, num);cout ;BubbleSort(b, num);cout ;BubbleSort
11、(c, num);count1 = 0, count2 = 0;cout endlendl;cout 快速排序 ;Newarray(a, b);QuickSort(a, 0, num - 2, count1, count2);cout 比较 count1 移动 count2 ;count1 = 0, count2 = 0;QuickSort(b, 0, num - 2, count1, count2);cout 比较 count1 移动 count2 ;count1 = 0, count2 = 0;QuickSort(c, 0, num - 1, count1, count2);cout 比较 count1 移动 count2 endlendl;count1 = 0, count2 = 0;Newarray(a, b);cout 简单选择排序 ;SelectSort(a, num);cout ;SelectSort(b, num);cout ;SelectSort(c, num);cout endlendl;Newarray(a, b);count1 = 0, count2 = 0;cout 堆排序 ;HeapSort(a, num);cout ;HeapSort(b, num);cout ;HeapSort(c, num);cout endl;cout 程序结束！;
