各种内排序算法的实现及性能的比较讲解.docx

实 验 报 告 （2015/2016学年 第2学期） 课程名称 数据结构A 实验名称 各种内排序算法的实现及性能的比较 实验时间 2016 年 6 月 20 日 指导单位 计算机科学与技术系 指导教师 骆健 学生姓名 班级学号 学院(系) 管理学院 专 业 信息管理与信息系统 一、 问题陈述 （1） 验证教材的各种内排序算法 （2） 分析各种内排序算法的时间复杂度 （3） 改进教材中的快速排序法，使得当子集和小于10个元素时改用直接插入排序 （4） 使用随机数发生器产生大数据集合，运行上述 各排序算法，使系统时钟测量个算法所需的实际时间，并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 Main.cpp调用Menu.h ，为主程序。Menu.h主菜单 Selectsort.h简单选择排序 Insertsort.h直接插入排序 Bubblesort.h冒泡排序 Quicksort.h快速排序 Mergesort.h合并排序 三、详细设计 ①简单选择排序：将初始序列（A[0]~A[n-1]）作为待排序序列，第一趟在待排序序列（A[0]~A[n-1]）中找最小元素，与该序列中第一个元素A[0]交换，这样子序列（A[0]）有序，下一趟排序在带牌子序列（A[1]~A[n-1]）中进行。第i趟排序子序列（A[i-1]~A[n-1]）中进行。经过n-1趟排序后使得初始序列有序。 程序流程图： ②直接插入排序：一个元素插入到有序表中，首先将其存入临时变量temp，然后从后往前查找插入位置。当temp小于表中元素时，就将该元素后移一个位置，继续比较、移动，直到temp大于等于表中元素或者到了有序表的第一个元素结束，这时就可将temp存入刚后移的元素的位置了。 程序流程图： ③冒泡排序：第一趟在序列（A[0]~A[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到A[n-1]中（即沉底）下一趟排序只需在子序列（A[0]~A[n-2]）中进行；如果在某一趟排序中未进行交换元素，说明子序列已经有序，则不再进行下一趟排序。 程序流程图： ④快速排序：取第一个元素作为分割元素，初始化i=left,j=right+1,i从左往右寻找第一个大于等于分割元素的元素，j从右往左找第一个小于等于分割元素的元素并交换，i和j继续移动，重复上述步骤，直到当i=j时将j与第一个元素交换。 程序流程图： ⑤两路合并排序：将有n 个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到[n/2]个长度为2或1的有序子序列，再两两合并…直到得到一个长度为n的有序序列时结束。 程序流程图： 四、程序代码 selectsort.h #include iostream.h//简单选择排序 template class T void SelectSort(T A[], int n) { int small; for (int i=0; in-1; i++) { small=i; for(int j=i+1;jn;j++) if(A[j]A[small])small=j; Swap(A[i],A[small]); } } Insertsort.h #include iostream.h//直接插入排序 template class T void InsertSort(T A[], int n) { for(int i=1; in; i++){ int j=i; T temp=A[i]; while(j0tempA[j-1]){ A[j]=A[j-1];j--; } A[j]=temp; } }/*ok!*/ Bubblesort.h #include iostream.h template class T void BubbleSort(T A[], int n) { int i,j,last; i=n-1; while(i0){ last=0; for(j=0;ji;j++) if(A[j+1]A[j]){ Swap(A[j],A[j+1]); last=j; } i=last; } } Quicksort.h #include iostream.h //改进的快速排序 templateclass T void quick(T A[],int n) { int *a; int top=0,right,left,j;