数据结构-内部排序算法比较

数据结构-内部排序算法比较PAGE1PAGE15内部排序算法比较1、课程设计的目的本课程设计为了更好的了解和认识数据结构常用的内部排序算法。排序对于数据结构的管理来说是至关重要的，所以熟悉掌握和深入了解这些常用的经典内部排序算法是有必要的。2、课程设计的要求1.掌握常用的排序方法和各种排序方法的特点。2.熟悉排序的基本概念。3、课程设计的内容3.1需求分析编制一个演示内部排序算法比较的程序。可对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆排序进行比较。3.2概要设计（1）冒泡排序基本思想是：设数组a中存放了n个数据元素，循环进行n-1次如下的排序过程：第一次时，依次比较相邻两个数据元素a[i]和a[i+1].key(i=0,1,2,3...,n-2).若为逆序，则交换两个数据元素，否则不交换，这样，当作完n-1次比较后数值最大的数据元素将比放置在a[n-1]中。第二次时，数据元素个数减1，即数据元素个数为n-1，操作方法与第一次类似，这样，n个数据元素集合中数值次大的数据元素将被放置在a[n-2]中。当第n-1次排序结束时，n个数据元素集合中次小的数据元素将被放置在a[1]中，而a[0]中放置了最小的数据元素。冒泡排序算法的空间复杂度为o(n2)。（2）直接插入排序基本思想是:顺序地把待插入的数据元素按其关键字的大小插入到已排序数据元素子集合的适当位置.子集合的数据元素个数从只有一个数据元素开始逐次增大,当子集合最终与集合大小相同时排序完毕.数据结构-内部排序算法比较全文共15页，当前为第1页。设待排序的N个数据元素存放在数组A中,初始时子集合a[0]以排好序.第一次循环准备把数据元素a[1]插入到以排好序的子集合中,这只需比较a[0].key和a[1].key,若a[0].key<=a[1].key,则说明序列已有序,否则,将a[1]插入到a[0]之前,这样子集合的大小增大为2;第二次循环是把数据元素a[2]插入到以排好序的子集合中,这需要先比较a[2].key和a[1].key,已确定是否需要把a[2]插到a[1]之前,然后比较a[2].key和a[0].key,以确定是否需要把a[2]插入到a[0]之前;这样的循环过程一直进行到a[n-1]插入完为止.这时,数据元素集合a[0],a[1],a[2],...,a[n-1]就全部排好了序。数据结构-内部排序算法比较全文共15页，当前为第1页。直接插入排序算法最坏情况下的时间复杂度为O(n2).（3）直接选择排序基本思想是：从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置的数据元素集合中选取关键字最小的数据元素并将它与原始数据集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。直接选择排序算法的时间复杂度为O(n2)。（4）快速排序快速排序是一种二叉树结构的交换排序方法，其基本思想是：设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个元素作为标准，调整数组a中各个元素的位置，使排在标准元素前面元素的关键字均小于标准元素的关键字，排在标准元素后面元素均大于或等于标准元素的关键字。这样一次过程结束后，一方面将标准元素放在了未来排好序的数组中该标准元素应在的位置上，另一方面将数组中的元素以标准元素为中心分为了两个子数组，位于标准元素左边均大于等于标准元素的关键字。然后对这两个子数组中的元素分别再进行方法类同的递归快速排序。（5）堆排序堆排序的基本思想是：循环执行如下过程直到数组为空：(1)把堆顶a[0]元素为最大元素与当前最大堆的最后一个元素交换；(2)最大堆元素个数减1；(3)若此时根节点不满足最大堆的定义，则调整根节点使之满足最大堆的定义。堆排序算法的时间复杂度为O(nlog2n)。（6）各种排序的比较通过计算各种排序算法的平均时间复杂度等来比较几种算法。冒泡排序算法平均时间复杂度为o(n2)。冒泡排序算法的空间复杂度为o(1).显然，冒泡排序是一种稳定的排序方法。数据结构-内部排序算法比较全文共15页，当前为第2页。数据结构-内部排序算法比较全文共15页，当前为第2页。直接选择排序算法的时间复杂度为O(n2)。直接选接排序算法的空间复杂度为o(2)。显然,直接选择排序算法是一种不稳定的排序算法.快速排序算法的平均算法复杂度为O（log2n）。平均空间复杂度为O（log2n）。快速排序算法是一种不稳定的排序方法。堆排序算法的时间复杂度为O(nlog2n)。堆排序算法的空间复杂度为O(1)。观察例子即可发现，堆排序算法是一种不稳定的排序方法。3.3详细设计（源代码）#include<stdio.h>#include<time.h>#include<stdlib.h>#include<malloc.h>typedefintDataType;#defineMaxSize100staticintSortTAndTs[6][4];voidSortTimeAndTimes(intNo,inttime,inttimes)//算法的数据交换次数和算法耗时{SortTAndTs[No][1]=No; SortTAndTs[No][2]=time;SortTAndTs[No][3]=times;}voidShowResult(){ printf("排序方法\t数据交换次数\t排序所耗时间\n"); for(inti=1;i<=6;i++) { if(SortTAndTs[i][1]==1) { printf("冒泡排序法\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==2) { printf("直接插入排序\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); }数据结构-内部排序算法比较全文共15页，当前为第3页。数据结构-内部排序算法比较全文共15页，当前为第3页。 { printf("直接选择排序\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==4) { printf("快速排序\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } elseif(SortTAndTs[i][1]==5) { printf("堆排序\t\t"); printf("%d\t\t",SortTAndTs[i][2]); printf("%d\n",SortTAndTs[i][3]); } } }voidNoSort(intb[],intn)//排序前乱序数据输出{ inti; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; printf("排序前数据\t"); for(i=0;i<n;i++) { printf("%4d",a[i]); //printf("\t"); } printf("\n\n");}voidMaoPao(intb[],intn)//冒泡法排序{ NoSort(b,n); inti,j,flag=1; intq; inta[MaxSize];数据结构-内部排序算法比较全文共15页，当前为第4页。数据结构-内部排序算法比较全文共15页，当前为第4页。 a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定义计时器 DataTypetemp; printf("冒泡法排序\n"); printf("排序过程\n"); begin=clock();//开始计时 for(i=1;i<n&&flag==1;i++) { flag=0; for(j=0;j<n-i;j++) { if(a[j]>a[j+1]) { flag=1; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } printf("第%d次排序结果\t",i); for(q=0;q<n;q++) { printf("%4d",a[q]);//printf("\t"); } printf("\n\n"); } end=clock();//结束计时SortTimeAndTimes(1,i,end-begin); printf("所用时间%d\n",end-begin);}voidZhiJie(intb[],intn)//直接插入排序{ NoSort(b,n); inti,j; DataTypetemp; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0';数据结构-内部排序算法比较全文共15页，当前为第5页。数据结构-内部排序算法比较全文共15页，当前为第5页。 printf("直接插入排序\n"); printf("排序过程\n"); begin=clock();//开始计时 for(i=0;i<n-1;i++) { temp=a[i+1]; j=i; while(j>-1&&temp<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=temp; printf("第%d次排序结果\t",i+1); for(q=0;q<n;q++) { printf("%4d",a[q]);//printf("\t"); } printf("\n\n"); } end=clock();//结束计时 SortTimeAndTimes(2,i+1,end-begin); printf("所用时间%d\n",end-begin);}voidSelectSort(intb[],intn)//直接选择排序{ NoSort(b,n); inti,j,small; DataTypetemp; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定义计时器 printf("直接选择排序\n"); printf("排序过程\n"); begin=clock();//开始计时 for(i=0;i<n-1;i++) {数据结构-内部排序算法比较全文共15页，当前为第6页。数据结构-内部排序算法比较全文共15页，当前为第6页。 for(j=i+1;j<n;j++) if(a[j]<a[small])small=j; if(small!=i) { temp=a[i]; a[i]=a[small]; a[small]=temp; } printf("第%d次排序结果\t",i+1); for(q=0;q<n;q++) { printf("%4d",a[q]); } printf("\n\n"); } end=clock();//结束计时 SortTimeAndTimes(3,i+1,end-begin); printf("所用时间%d\n",end-begin);}voidQuickSort(DataTypeb[],intn,intlow,inthigh)//快速排序{ inti; staticintsum=1; intleap=0; intq; inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; clock_tbegin,end;//定义计时器 DataTypetemp=a[low];/*第一个元素为标准数据元素*/ begin=clock();//开始计时i=low; intj=high; while(i<j) { while(i<j&&temp<=a[j])j--;/*在数组的右端扫描*/ if(i<j)数据结构-内部排序算法比较全文共15页，当前为第7页。数据结构-内部排序算法比较全文共15页，当前为第7页。 a[i]=a[j]; i++; leap=1; } while(i<j&&a[i]<temp)i++;/*在数组的左端扫描*/ if(i<j) { a[j]=a[i]; j--; leap=1; } } a[i]=temp; if(leap==1) { printf("第%d次排序结果\t",sum); for(q=0;q<n;q++) { printf("%4d",a[q]); } sum++; printf("\n\n"); } if(low<i)QuickSort(a,n,low,i-1);/*对左端子集合进行递归*/ if(i<high)QuickSort(a,n,j+1,high);/*对右端子集合进行递归*/ if(high>low) { end=clock();//结束计时 SortTimeAndTimes(4,sum,end-begin); printf("所用时间%d\n",end-begin); } } intCreatHeap(DataTypea[],intn,inth){ inti,j,flag; staticintsum=0,q=0; DataTypetemp; i=h;数据结构-内部排序算法比较全文共15页，当前为第8页。数据结构-内部排序算法比较全文共15页，当前为第8页。 temp=a[i]; flag=0; while(j<n&&flag!=1) { if(j<n-1&&a[j]<a[j+1])j++; if(temp>a[j]) flag=1; else { a[i]=a[j]; i=j; j=2*i+1; } } a[i]=temp; if(flag==0) { printf("第%d次排序结果\t",sum+1); for(q=0;a[q]!='\0';q++) { printf("%4d",a[q]); } printf("\n"); printf("\n"); sum++; } returnsum;}voidInitCreatHeap(DataTypea[],intn){ inti; for(i=(n-1)/2;i>=0;i--) CreatHeap(a,n,i);}voidHeapSort(intb[],intn)//堆排序{ NoSort(b,n); inti;数据结构-内部排序算法比较全文共15页，当前为第9页。数据结构-内部排序算法比较全文共15页，当前为第9页。 inta[MaxSize]; for(i=0;i<n;i++) a[i]=b[i]; a[i]='\0'; DataTypetemp; clock_tbegin,end;//定义计时器 printf("堆排序\n"); printf("排序过程\n"); begin=clock();//开始计时 InitCreatHeap(a,n); for(i=n-1;i>0;i--) { temp=a[0]; a[0]=a[i]; a[i]=temp; times=CreatHeap(a,i,0); } end=clock();//结束计时 SortTimeAndTimes(6,times,end-begin); printf("所用时间%d\n",end-begin);}voidmain(){ intBiaoChang=0; inti=0,j=0; intptrData[MaxSize]; intchoose; charpause; while(1) {printf("**************************************************************\n"); printf("****\n"); printf("****\n");printf("**欢迎使用内部排序算法分析器**\n"); printf("****\n"); printf("**算法选择提示**\n");数据结构-内部排序算法比较全文共15页，当前为第10页。 printf("**数据结构-内部排序算法比较全文共15页，当前为第10页。printf("**1.冒泡排序**\n"); printf("**2.直接插入排序**\n"); printf("**3.简单选择排序**\n"); printf("**4.快速排序**\n"); printf("**5.堆排序**\n"); printf("**6.所有排列比较**\n"); printf("**0.退出程序**\n"); printf("****\n"); printf("************************************************************\n"); printf("请输入要排序的数据表的表长"); scanf("%d",&BiaoChang);printf("请输入要排序的数据\n"); //srand((unsigned)time(NULL)); for(i=0;i<BiaoChang;i++) { scanf("%d",&ptrData[i]); //ptrData[i]=rand()*10%1000; }ptrData[i]='\0'; //for(q=0;q<BiaoChang;q++) // { // printf("%d",ptrData[q]);//printf("");// // }printf("请选择排序方法\n");printf("\n"); scanf("%d",&choose); switch(choose) { case1:MaoPao(ptrData,BiaoChang);break; case2:ZhiJie(ptrData,BiaoChang);break; case3:SelectSort(ptrData,BiaoChang);break; case4: printf("快速排序\n");printf("排