发布时间 : 星期一 文章数据结构课程设计_排序算法比较【完整版】更新完毕开始阅读
数据结构课程设计——排序算法比较
cout<
case 1:t1=time(NULL);insertsort(R,n);t2=time(NULL);tt1=difftime(t2,t1); cout<<\排序所需时间为：\直接插入排序算法实现
case 2:t1=time(NULL);Bubblesort(R,n);t2=time(NULL);tt2=difftime(t2,t1); cout<<\排序所需时间为：\ //冒泡排序算法实现
case 3:t1=time(NULL); cout<<\ for(x=0;x case 4:t1=time(NULL);selectsort(R,n);t2=time(NULL);tt4=difftime(t2,t1); cout<<\排序所需时间为：\ //直接选择排序算法实现 case 5:t1=time(NULL);mergesort(R,n); cout< 第 5 页 共 15 页 数据结构课程设计——排序算法比较 cout<<\元素交换次数为\次\ t2=time(NULL);tt5=difftime(t2,t1); cout<<\排序所需时间为：\ //二路归并排序算法实现 default:cout<<\ } } 五、算法及时间复杂度 （一）各个排序的算法思想： （1）直接插入排序算法思想：将一个记录插入到已排好的有序表中，从 而得到一个新的，记录数增加1的有序表。 （2）起泡排序算法思想：首先将第一个记录的关键字和第二个记录的关 键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。 （3）快速排序算法思想：通过一趟排序将待排记录分割成独立的两部 分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 （4）选择排序算法思想：通过N-I次关键字间的比较，从N-I+1个记录 中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换。 （5）二路归并排序算法思想：先将每个数确定为一个空间，然后两两比较，把排序后的结果放在新数组中，然后再两两比较，以此类推，最终把所有的子区间合并为一个区间。 （二）时间复杂度分析 排序算法 最差时间 O(n2) 时间复杂度 O(n2) 是否稳定？ 稳定 冒泡排序 第 6 页 共 15 页 数据结构课程设计——排序算法比较 快速排序 选择排序 O(n) O(n2) 2O(n*log2n) O(n2) 不稳定 稳定 六、程序源代码 /********************************************************************************************** 设计要求：利用随机函数产生N个随机整数（N = 1到500），利用直接插入排序，冒泡排序、快速排序、选择排序、二路归并排序五种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间，比较的总次数和交换的总次数。 #include #include using namespace std; const int maxsize=500; int R[maxsize]; int A[maxsize]; int i,n,right,left; int comN1=0,chaN1=0; //直接插入排序中元素比较的次数和交换的次数 int comN2=0,chaN2=0; //冒泡排序中元素比较的次数和交换的次数 int comN3=0,chaN3=0; //快速排序中元素比较的次数和交换的次数 int comN4=0,chaN4=0; //直接选择排序中元素比较的次数和交换的次数 int comN5=0,chaN5=0; //合并排序中元素比较的次数和交换的次数 class NuovSort{ public: void Myface(); void choose(); void insertsort(int R[],int n); //直接插入排序法 void Bubblesort(int R[],int n); //冒泡排序算法实现 void quicksort(int R[],int left,int right); //快速排序算法实现 void selectsort(int R[],int n); //直接选择排序算法实现 void merge(int R[],int A[],int s,int m,int t);//二路归并排序算法实现 void mergepass(int R[],int A[],int n,int c); void mergesort(int R[],int n); }; 第 7 页 共 15 页 数据结构课程设计——排序算法比较 void NuovSort::Myface() //界面 { cout<<\ -->各种排序算法实现<--\ cout<<\ cout<<\ 1.直接插入排序 #\ cout<<\ 2.冒泡排序 #\ cout<<\ 3.快速排序 #\ cout<<\ 4.直接选择排序 #\ cout<<\ 5.二路归并排序 #\ cout<<\ cout<<\} void Display(int R[], int n) { for(int i=0;i void NuovSort::choose() { int i,x,n,s,t; time_t t1,t2; double tt1,tt2,tt3,tt4,tt5; cout<<\欢迎您使用 高扬 的排序程序\ cout<<\请问，需要几个被排序数字？\ do{ cout<<\请输入个数(范围在 1~500 之间): \ cin>>n; } while((n<1)||(n>500)); int left=0,right=n-1; for(i=0;i R[i]=rand()?8+1; //产生随机数 cout<<\被排序的数字随机产生如下：\ for(i=0;i case 1:t1=time(NULL);insertsort(R,n);t2=time(NULL);tt1=difftime(t2,t1); 第 8 页 共 15 页