不同排序算法的分析
摘要：计算机是一种现代化的信息处理工具，他对信息进行处理并提供所需结果，描述的解题过程。对于给定的问题，有可能设计出多个算法，但不同的算法质量会不一样。衡量算法的主要因素是算法执行所耗费的时间和所需的存储空间，以及算法适用范围等。排序算法，是计算机编程中的一个常见问题。我们经常用到排序算法，下面就介绍合并排序、冒泡排序、快速与排序、直接选择排序、希尔排序等这几种排序的基本概念、基本的排序思想、使用算法、排序的性能分析、排序适用的范围。通过这些知识来了解各个排序算法。
1合并排序
1.1合并排序思路
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治发（Divide and Conquer）的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。
1.2合并排序使用算法
1.2.1合并排序的示例
将如下的两个A1{3,4,7,9}和A2{1,2,6,10}进行合并排序 将A1中的3和A2中的1比较后放入第一个位置：1 将A1中3和A2中2比较后放入第二个位置：1 2 将A1中3和A2中6比较后放入第三个位置：1 2 3 将A1中4和A2中6比较后放入第四个位置：1 2 3 4 将A1中7和A2中6比较后放入第五个位置：1 2 3 4 6 将A1中7和A2中10比较后放入第六个位置：1 2 3 4 6 7 将A1中9和A2中10比较后放入第七个位置：1 2 3 4 6 7 9 最后结果：1 2 3 4 5 6 7 9 10
第 1 页 共 11 页
1.2.1合并排序主的程序 #include
void heb_Sort(int a[],int sta,int end) { } } if(i<=mid) while(i<=mid)
b[k++] = a[i++]; else if(j<=end) while(j<=end)
b[k++] = a[j++]; k = 0;
for(int m = sta;m<=end;m++) {
a[m] = b[k++]; }
if(sta==end) return ;
int mid = (sta+end)/2; heb_Sort(a,sta,mid); heb_Sort(a,mid+1,end); int b[LEN]; int i,j,k;
i = sta,j = mid+1;k = 0; while(i<=mid&&j<=end) {
if(a[i]>a[j]) b[k++] = a[j++]; b[k++] = a[i++]; else
//合并排序算法
第 2 页 共 11 页
1.3合并排序性能分析
合并排序复杂度分析：合并排序时间复杂性为O(nlogn) ，合并排序空间复杂度O(n)。
1.4合并排序使用范围
当需要排序的序列的n很大，可以将其划分为小的序列，将可以用合并排序进
行排序。
2冒泡排序
2.1冒泡排序思路
冒泡排序的基本思想是：设待排序对象序列中的对象个数为最多做n-1趟，i=1，2，???n-2。在第i趟中顺次两两比较v[n-j-1].key和v[n-j]。key，j-1，n-2???，i。如果发生逆序，则交换v[n-j-1]和v[n-j]。
通过一次冒泡排序，使得待排序的n个记录中的关键字最大的一个记录排在序列的最后一个位置；然后再对序列中的前一个n-1个记录进行第二次冒泡排序，使得关键字次大的记录拍到序列的第n-1位置。重复进行冒泡排序，对于具有n个记录的序列进行n-1次冒泡排序后，序列的后n-1个记录已按关键字从小到大地进行了排序，那么剩下的第一个记录必定是关键字最小的记录，所以此时整个序列已经是一个有序排列。
另外，如果进行了某次冒泡排序后，没有记录交换位置，这就表明此序列已经是一个有序序列，此时排序也可以结束。
2.2冒泡排序使用算法
2.2.1冒泡排序的示例
有如下初始关键字序列为{11 13 9 14 8 15 7 10}用冒泡排序进行排序 初始关键字序列：11 13 9 14 8 15 7 10 第一次冒泡排序：11 9 13 8 14 7 10 [15] 第二次冒泡排序：9 11 8 13 7 10 [14 15] 第三次冒泡排序：9 8 11 7 10 [13 14 15] 第四次冒泡排序：8 9 7 10 [11 13 14 15] 第五次冒泡排序：8 7 9 [10 11 13 14 15] 第六次冒泡排序：7 8 [9 10 11 13 14 15]
第 3 页 共 11 页
第七次冒泡排序：7 [8 9 10 11 13 14 15] 最后结果序列： [7 8 9 10 11 13 14 15] 2.2.2冒泡排序的主程序： #include
for(i=1;i for(j=1;j<=n-i;j++) if(R[j].key>R[j+1].key) { R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; } } } 2.3冒泡排序的性能分析 根据上述冒泡排序的示例可得知，冒泡算法的执行时间与序列的初始状态有很大的关系。若在序列中，记录已经是有序排列，则比较次数为n-1，交换次数为0；反之，如果原始序列中，记录是“反序”排列的，则总的比较次数为n(n-1)/2,总的移动次数为3n(n-1)/2.所以猫婆婆排序算法的时间复杂度为O(n2)。冒泡排序是稳定的。 2.4冒泡排序适用范围 当需要排序的序列为小列表或者需要的排序基本有序的时候可以使用冒泡排序。 3快速排序 3.1快速排序思路 快速排序对冒泡排序的一种改进。它的基本思想是：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。再待排序的n个记录中采取一个 第 4 页 共 11 页 记录（通常取第一个记录），把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字小的放置位置在前一部分，所有比他大的放置在最后一部分，并把该记录排在这两部分的中间，这个过程成为一趟快速排序。之后对所分的两部分粉别重复上述过程，直至每部分内只有一个记录为止。简而言之，每趟使表的一个元素入终位，将表一分为二，对子表递归方式继续这种划分，直直至划分的子表长为1。 3.2快速排序使用算法 3.2.1快速排序的具体做法 快速排序的具体做法是：设两个指示器i和j，它们的初始值分别为指向无序区中的第一个和最后一个记录。假设无序去中的记录为r[m]，r [m+1]，?? r [h]，则i的初值为m，j的初值为h，首先将r[m]移至变量x中作为基准，令j自h起向左扫描至r[j]＜Ｘ，将r[j]移至ｉ所指的位置上，然后令ｉ自ｉ＋１起向右扫描至r[i]＞ｘ,将r[i]移至j所在的位置上，然后j自j+1起向左扫描至r[j] 3.2.2快速排序的示例 例如，有下列数据{19 10 18 39 47 3 1 16 11 41}对其进行快速排序。 初始关键字： 19 10 18 39 47 3 1 16 11 41 （以19作为基准） i j 进行一次交换后：11 10 18 39 47 3 1 16 41 i j 进行二次交换后：11 10 18 47 3 1 16 39 41 i j 进行三次交换后：11 10 18 16 47 3 1 39 41 i j 第 5 页 共 11 页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计和C++中不同排序算法的分析在线全文阅读。
相关推荐：