数据结构实验四报告排序.docx

数据结构实验报告实验名称： 实验四排序学生姓名： 班 级： 班内序号：学 号： 日 期： 2013年12月16日1 实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2. 程序分析2.1 存储结构使用最简单的一维数组存储待排序的数据。共使用三个数组，一个用来构造正序数组，一个是逆序数组，还有一个是随机数组。每种排序使用的数组都是具有相同初始值的，因而使得试验结果具有可比较性。2.2关键算法分析2.2.1插入排序算法插入排序的思想是：每次从无序区取一元素将其添加到有序区中。2.2.2希尔排序算法希尔排序是一种缩小增量排序的算法，首先将待排序元素集按照一定间隔分成多个子集，分别对这些子集进行直接插入排序，整个序列部分有序。然后缩小间隔，在进行直接插入排序，直到间隔为1，此时，整个序列已全部有序。 2.2.3起泡排序起泡排序的思想是：两两比较相邻的元素，如果反序，则交换次序，直到没有反序的元素为止。在此思想指导下首先将待排序元素划分为有序区和无序区，初始状态有序区为空，无序区所有待排序素；对无序区从前向后依次将相邻元素关键码进行比较，若反序，则交换重复执行直到无序区中没有元素。2.2.4快速排序算法2,2,4,1一趟快速排序算法自然语言描述如下选取区间第一个元素作为轴值读取区间首尾坐标，并将其左右侧待比较元素右侧扫描：从后向前找到第一个比轴值小的元素，和左侧待比较元素交换（左侧第一个带比较元素为轴值）左侧扫描：从前向后找到第一个比轴值大的元素，和右侧待比较元素交换重复，直到左右两侧带比较元素的坐标相等其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+12.2.6.2调整数组为升序排列输出堆顶元素将堆中最后一个元素移至堆顶，并将剩余元素调整为小根堆反复执行两个元素，直到堆中只有一个元素2.2.6.2堆排序完整算法如下3. 程序运行结果测试主函数运行流程图： 源代码#include#includetime.husing namespace std;void InsertSort(int r, int n)/直接插入排序 int count1 = 0, count2 = 0;/分别用来记录插入排序比较和移动次数的计数器 for (int i = 2; i = n - 1; i+)if (riri - 1)/查找插入位置 r0 = ri; /设置哨兵 count2+; /移动次数加1int j;for (j = i - 1; count1+, r0rj; j-) /寻找插入位置 rj + 1 = rj; /元素后移 count2+; /移动次数加1rj + 1 = r0;/插入记录 count2+;else count1+;/此时虽然没有移动但是已经进行了一次比较 cout 比较 count1 移动 = 1; d = d / 2) /以增量为d进行直接插入排序 for (i = d + 1; i0 & r0rj; j = j - d)/每隔d个记录进行一次比较和移动 rj + d = rj; /记录后移d个位置 rj + d = r0;count1+;count2 = count2 + d;/每次都移动d个位置 count1+;cout 比较 count1 移动 count2; void BubbleSort(int r, int n) /起泡排序 int temp, pos, bound;int count1 = 0, count2 = 0;pos = n - 1; /第一趟起泡排序的范围是r1到rn while (pos != 0) /仅当上一趟排序有记录交换才进行本趟排序 bound = pos; /本次无序元素的范围 pos = 0; /控制外循环结束 for (int j = 1; jrj + 1) /相邻元素比较 temp = rj; /交换rj和rj+1 rj = rj + 1;rj + 1 = temp;pos = j; /记录每一次发生记录交换的位置当j=0时说明一次比较也没有了即已经全部有序了 count2 = count2 + 3; /一个交换语句为一次移动共移动了次 cout 比较 count1 移动 count2;int Partition(int r, int first, int end, int &count1, int &count2)/快速排序一次划分 int i = first; /初始化 int j = end;int temp;while (ij)while (ij & ri = rj)j-; /右侧扫描 count1+;if (ij)temp = ri;ri = rj; /将较小记录交换到前面 rj = temp;i+;count2 = count2 + 3;count1+;while (ij & ri = rj)i+; /左侧扫描 count1+;if (ij)temp = ri;ri = rj; /将较小记录交换到前面 rj = temp; /将较大记录交换到后面 j-;count2 = count2 + 3;count1+;return i; /i为轴值记录的最终位置 void QuickSort(int r, int first, int end, int &count1, int &count2)/快速排序 if (firstend) /递归结束,继续执行下边的操作 int pivot = Partition(r, first, end, count1, count2); /一次划分 QuickSort(r, first, pivot - 1, count1, count2);/递归地对左侧子序列进行快速排序 QuickSort(r, pivot + 1, end, count1, count2); /递归地对右侧子序列进行快速排序 void SelectSort(int r, int n)/简单选择排序 int i;int j;int index; /初始化 int temp;int count1 = 0, count2 = 0;for (i = 1; in; i+) /对n个记录进行n-1趟简单选择排序 index = i; /假设index是最小的 for (j = i + 1; jn; j+) /在无序区中选取最小记录 if (rjrindex) /如果该元素比现在第i个位置的元素小 index = j;/赋值给index count1+; /比较次数加一 /count1+; /在判断不满足循环条件jn时比较了一次 if (index != i)temp = ri; /将无序区的最小记录与第i个位置上的记录交换 ri = rindex;rindex = temp;count2 = count2 + 3; /移动次数加 cout 比较 count1 移动 count2;void Sift(int r, int k, int m, int &count1, int &count2)/小根堆筛选算法 筛选法调整堆,st分别为比较和移动次数,m为编号最大的叶子结点的编号 int i = k;int j = 2 * i + 1; /置i为要筛的结点j为i的左孩子 int temp;while (j = m) /筛选还没有进行到叶子 if (jm & rjrj)break; /根结点已经大于左右孩子中的较大者则结束循环 elsetemp = ri;ri = rj;rj = temp; /将根结点与结点j交换 i = j;j = 2 * i + 1; /下一个被筛结点位于原来结点j的位置 count2 = count2 + 3; /移动次数加 void HeapSort(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(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 = 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);cout ;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(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 endle