资源描述：
《算法分析与设计和C中不同排序算法的分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、合并排序与冒泡算法的分析摘要：计算机是i种现代化的信息处理工具，他对信息进行处理并提供所需结果,描述的解题过程。对于给定的问题，有可能设计出多个算法，但不同的算法质量会不一样。衡量算法的主要因素是算法执行所耗费的时间和所需的存储空间，以及算法适用范围等。排序算法，是计算机编程中的一个常见问题。我们经常用到排序算法，下面就介绍合并排序、冒泡排序、快速与排序、直接选择排序、希尔排序等这几种排序的基本概念、基本的排序思想、使用算法、排序的性能分析、排序适用的范围。通过这些知识来了解各个排序算法。1合并排序1.1合并排序思路合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治发(Div
2、ideandConquer)的一个非常典型的应用。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全冇序的序列；即先使每个子序列冇序，再使子序列段间冇序。若将两个冇序表合并成•个冇序表，称为2■路归并。合并排序也叫归并排序。1・2合并排序使用算法121合并排序的示例将如下的两个A】｛3,4,7,9｝和A2｛126,10｝进行合并排序将A］中的3和A?中的1比较后放入笫一个位置:将A】屮3和A?屮2比较后放入第二个位置:将街中3和A2中6比较后放入第三个位置:将A
3、i中4和A2中6比较后放入第四个位置:将A】屮7和A?屮6比较后放入第五个位置:将A］中7和A?中10比较后放入第六个位置：1将A］中9和A2中10比较后放入第七个位置：1最后结果：12345679101.2.1合并排序主的程序#include#include#include〃合并排序算法voidheb_Sort(inta[],intstajntend)if(sta==end)return;intmid=(sta+end)/2;heb_Sort(a,sta,mid);heb_Sort(a,mid+1,end);intb[LEN];in
4、ti,j,k;i=staj=mid+l;k=0;while(i<=mid&&jv二end){if(a[i
5、>a
6、jl)b[k++]=a[j++];elseb[k++]二a[i++];}if(i<=mid)while(i<=mid)b[k++]二a[i++];elseif(j<=end)while(j<=end)b[k++
7、=a[j++];k=0;for(intm=sta;m<=end;m++){a[m]=b[k++];1.3合并排序性能分析合并排序复杂度分析：合并排序时间复杂性为O(nlogn),合并排序空间复杂度O(n)o1.4合并排序使用范围当需耍排序的序列的n很大，可以将其划分为小的
8、序列，将可以用合并排序进行排序。2冒泡排序2」冒泡排序思路冒泡排序的基本思想是：设待排序对象序列中的对象个数为最多做ml趟，i=l,2,n-2o在第i趟中顺次两两比较v[n-j-l].key和v[n・j]。key,j-1,n-2,io如果发生逆序，则交换v[n-j-l]和v[n・j]。通过一次冒泡排序，使得待排序的n个记录中的关键字最大的一个记录排在序列的最后一个位置；然后再对序列屮的前一个ml个记录进行第二次冒泡排序，使得关键字次大的记录拍到序列的第n・l位置。重复进行冒泡排序，对于具有n个记录的序列进行ml次冒泡排序后，序列的后ml个记录已按关键字从小到大地进行了排序，那么剩下的第一个
9、记录必定是关键字最小的记录，所以此时整个序列已经是一个有序排列。另外，如果进行了某次冒泡排序后，没有记录交换位置，这就表明此序列已经是一个冇序序列，此时排序也可以结束。2.2冒泡排序使用算法2.2.1冒泡排序的示例有如下初始关键字序1列为(1113914815710｝用冒泡排序进行排序初始关键字序列：1113914815710第一次冒泡排序：11913814710[15]第二次冒泡排序：911813710[1415]第三次冒泡排序：98117101131415
10、第四次冒泡排序：89710[11131415]第五次冒泡排序：879[1011131415]第六次冒泡排序：78[91011131
11、415]第七次冒泡排序：7[891011131415]最后结果序列：[7891011131415]2.2.2冒泡排序的主程序：#include#include#includevoidBubblesort()inti,j,k;{for(i=l;iR[j+l].key){R[0]=R[j]；R
