数据结构实验报告用简单数组实现下面各种排序算法.doc

北京邮电大学电信工程学院数据结构实验报告实验名称： 实验4用简单数组实现排序日 期： 2009年12月6日1实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性2. 程序分析r1r2 ri-1 ri ri+1 rn有序区 无序区 直接插入排序的基本思想图解插入到合适位置rj rj+1 ri+1 rn-1 rn 无序区 有序区 1ji-1 已经位于最终位置 起泡排序的基本思想图解反序则交换 r1 r2 ri-1 ri ri+1 rmin rn 有序区 无序区 已经位于最终位置 rmin为无序区的最小记录 简单选择排序的基本思想图解交换 r1 ri-1 ri ri+1 rn 均ri 轴值 均ri 位于最终位置 快速排序的基本思想图解2.1 存储结构数组：数组下标： 0 1 2 3 4 5 6数组元素A7A6 A5A4 A3 A2 A1 2.2 关键算法分析快速排序为代码：1将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置；2重复下述过程，直到i=j 2.1右侧扫描，直到记录j的关键码小于基准记录的关键码；2.2 如果ij，则将rj与ri交换，并将i+； 2.3左侧扫描，直到记录i的关键码大于基准记录的关键码； 2.4 如果ij，则将ri与rj交换，并将j-；3退出循环，说明i和j指向了基准记录所在位置，返回该位置；直接顺序排序void InsertSort(int r, int n)int ay=0;int ab=0; for (int i=2; in; i+) ab+; r0=ri; /设置哨兵 for (int j=i-1; r0rj; j-) /寻找插入位置 rj+1=rj; /记录后移 rj+1=r0; ay+; for(int k=1;kn;k+)/循环输出数据 coutrk ; coutn;cout关键字移动次数：3*ayendl; cout关键字比较次数：ab=1; d=d/2) /以增量为d进行直接插入排序 for (i=d+1; i0 & r0rj; j=j-d) rj+d=rj; /记录后移d个位置 rj+d=r0; by+; for(i=1;in;i+)/循环输出数据 coutri ; coutn;cout关键字移动次数：3*byendl;cout关键字比较次数：bbendl;起泡排序void BubbleSort(int r, int n)int cy=0;int cb=0;int temp;int exchange;int bound; exchange=n-1; /第一趟起泡排序的范围是r0到rn-1while (exchange) /仅当上一趟排序有记录交换才进行本趟排序 cb+;bound=exchange; exchange=0; for (int j=0; jrj+1) temp=rj; rj=rj+1; rj+1=temp; exchange=j; /记录每一次发生记录交换的位置 cy+; for(int i=0;in;i+)/循环输出数据 coutri ;coutn;cout关键字移动次数：3*cyendl;cout关键字比较次数：(2*n-1-cb)*cb/2endl;快速排序一次划分int Partition(int r, int first, int end)int i=first; /初始化int j=end;int temp; while (ij) while (ij & ri= rj)j-; db+; /右侧扫描 if (ij) temp=ri; /将较小记录交换到前面 ri=rj; rj=temp; i+; dy+; while (ij & ri= rj) i+; db+; /左侧扫描 if (ij) temp=rj; rj=ri; ri=temp; /将较大记录交换到后面 j-; dy+; return i; /i为轴值记录的最终位/快速排序void QuickSort(int r, int first, int end) if (firstend) /递归结束 int pivot=Partition(r, first, end); /一次划分 QuickSort(r, first, pivot-1);/递归地对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); /递归地对右侧子序列进行快速排序简单选择排序void SelectSort(int r , int n) int ey=0,eb=0;int i;int j;int index;int temp; for (i=0; in-1; i+) /对n个记录进行n-1趟简单选择排序 eb+; index=i; for (j=i+1; jn; j+) /在无序区中选取最小记录 if (rjrindex) index=j; if (index!=i) temp=ri; ri=rindex; rindex=temp; ey+; for(i=0;in;i+) coutri ; coutn;cout关键字移动次数：3*eyendl;cout关键字比较次数：eb*(eb+1)/2endl;排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)希尔排序O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O (n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)简单选择排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O (nlog2n)O(1)归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)排序方法最好情况最坏情况平均情况直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)简单选择排序0O(n)O(n)3. 程序运行结果程序结束排序数据直接排序希尔排序起泡排序简单选择排序快速排序平均情况下快速排序为最优排序4总结排序过程通常要进行下列