算法分析与设计和C++中不同排序算法的分析

不同排序算法的分析

摘要：计算机是一种现代化的信息处理工具，他对信息进行处理并提供所需结果，描述的解题过程。对于给定的问题，有可能设计出多个算法，但不同的算法质量会不一样。衡量算法的主要因素是算法执行所耗费的时间和所需的存储空间，以及算法适用范围等。排序算法，是计算机编程中的一个常见问题。我们经常用到排序算法，下面就介绍合并排序、冒泡排序、快速与排序、直接选择排序、希尔排序等这几种排序的基本概念、基本的排序思想、使用算法、排序的性能分析、排序适用的范围。通过这些知识来了解各个排序算法。

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 #include #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 #include #include void Bubblesort() int i,j,k; {

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 页

进行四次交换后：11 10 18 16 3 1 47 39 41 i j

进行五次交换后：11 10 18 16 1 3 47 39 41 i j

完成一趟排序： 11 10 18 16 1 3 19 47 i j 1)以28作为基准，第一趟排序后

序列如下：{11 10 18 16 1 3} 19 { 47 39 2)分别以11和47作为基准，排序后

序列如下：{3 10 1} 11 {16 18 } 19 {41 39} 3）分别以3、16、41作为基准，排序后

序列如下：1 3 10 11 16 18 19 39 41 最后排序结果是：[1 3 10 11 16 18 19 39 3.2.3快速排序的主程序 #include #include #include

void ks_Sort(int a[],int sta,int end)

//快速排序算法

{ if(sta==end) return;

int mid = midden(a,sta,end); ks_Sort(a,sta,mid); ks_Sort(a,mid+1,end);

}

void outToScreen(int a[],int len) {

int i = 0; 第 6 页 共 11 页

39 41

41} 47 47 41 47] }

while(i

cout<

cout<

3.3快速排序性能分析

根据上述快速排序的使用算法可得知，总的比较次数为O(nlog2n)，所以快速排序的平均时间复杂度为O(nlog2n),空间复杂度为O(n)。

3.4快速排序适用范围

当辅助空间次大的时候、n很大的时候、需要排序的序列的复杂度为O(nlogn)或者需要排序的序列是无序的时候可以使用快速排序。

4直接选择排序

4.1直接选择排序思想

直接选择排序思想是：首先在一组对象v[i] ~v[n-1]中选择具有最小关键码的对象，若它不是这组对象中的第一个对象，则将它与这组对象中的第一对像对调，然后在这组对象中剔除这个具有最小关键码的对象，在剩下的对象v[i+1] ~v[n-1]中重复执行上述步骤，直到剩余对象只有一个为止。

4.2直接选择排序使用算法

4.2.1 直接选择排序示例

有如下数据{19 10 18 39 47 3 1 16 11 4} 对其进行直接选择排序（有序区间用[??]表示，无序区间用{??}表示）。

初始关键字序列： {19 10 18 39 47 3 1 16 11 4} 进行第一次排序后：[1] {10 18 39 47 3 19 16 11 4} 进行第二次排序后：[1 3] {18 39 47 10 19 16 11 4} 进行第三次排序后：[1 3 4 ] {39 47 10 19 16 11 18} 进行第四次排序后：[1 3 4 10] {47 39 19 16 11 18}

第 7 页 共 11 页

进行第五次排序后：[1 3 4 10 11] {39 19 16 47 18} 进行第六次排序后：[1 3 4 10 11 16] {19 39 47 18} 进行第七次排序后：[1 3 4 10 11 16 18] {39 47 19} 进行第八次排序后：[1 3 4 10 11 16 18 19] {39 47} 进行第九次排序后：[1 3 4 10 11 16 18 19 39] {47] 最后结果： [1 3 4 10 11 16 18 19 39 47] 4.2.2直接选择排序的程序 #include #include #include void Selectsort() {

for(i=1;i

for(j=i+1;j<=n;j++)

if(R[j].key

{

R[0]=R[i];R[i]=R[h];R[h]=R[0]; } } }

4.3直接选择排序性能分析

根据直接选择排序算法示例分别，找到关键码最小的记录需要进行n-1次比较，找出关键码次小的记录需要比较n-2次，??，找到第i个记录需比较n-i次，因此，总的比较次数为：（n-1）+（n-2）+??+2+1=n(n-1)/2 ≈n2/2,所以直接选择排序的时间复杂度为O(n2)，辅助空间为O(1)，直接选择排序是不稳定的排序方法。

4.4直接选择排序适用范围

当n的值较小（n<50）时，若因为直接移动的记录少于直接插入，选择直接选择

第 8 页 共 11 页

排序较好。

5希尔排序

5.1希尔排序的思想

希尔排序的思想是：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序时”，再对全体记录进行一次直接插入排序。

5.2希尔排序的使用算法

5.2.1希尔排序的具体做法

希尔排序的具体做法是：设待排序对象序列有n个对象，首先去一个整数gap

5.2.2希尔排序的具体示例

对下列的序列{15 25 36 88 76 45 54 46 32 70}进行希尔排序，间隔值序列取5,3,1。

初始关键字： 15 25 36 88 76 45 54 46 32 70 gsp=5 {15 45} {25 54} {36 46} {88 32} {76 70} 第一趟排序结果: 45 54 46 32 70 15 25 36 88 76 gap=5 {45 32 25 76} {54 70 36} {46 15 88} 第二趟排序结果： 45 70 15 25 54 46 32 36 88 76 gap=3

第三趟排序结果： 15 25 32 36 45 46 54 70 76 88 gap=1

第 9 页 共 11 页

5.2.3希尔排序的主程序 #include #include #include void ShellSort() {

gap=n/2;//初次增量取序列元素个数n的一半为步长 while(gap>0)

{

for(i=gap+1;i<=n;i++)

{

j=i-gap;

while(j>0) {

I if(r[j]>r[j+gap]) {

x=r[j];r[j]=r[j+gap];r[j+gap]=x;

j=j-gap;

}//对子序列作直接插入排序 else

{ j=0; }

}

}

gap=gap/2;

}//每次减半，直至步长为1 }

5.3希尔排序的性能分析

希尔排序的速度一般要比直接插入排序快，希尔排序是一个较复杂的问题，因为它的时间复杂度是依赖与所取增量序列，一般认为是O(nlog2n)2,辅助空间为O(1)， 希尔排序是一种不稳定的排序。

第 10 页 共 11 页

5.4希尔排序的适用范围

当需要排列的序列的数据量较小，并且需要重复排序可以用希尔排序。

总结

经过几天的查资料学习，总结去写这个结课论文，起初不知道从何写起，都是一些算法，如何分析？后面看到老师给的提示，就有了思路，根据算法的排序思想、使用算法、排序的复杂度、适用范围去分析每一个排序就可以。在做这次作业的过程中发现了很多的问题，知道要写的东西，却不能很准确的描述，需要借助书才能将自己想表达的东西表述清楚。知识学得不够扎实，只知其一不知其二，有些东西无法进行。就像一些排序里的算法分析，适用范围都不知道如何的写，需要查书，查些资料，将其进行归纳总结才能成为自己的。每一个排序算法的时间复杂度或者空间复杂度都是很简单的，只要能够弄懂一个排序算法的时间复杂度或者空间复杂度，其他的就一反三都可以出来。每个算法的都是能理解思想，用数字可以将它们排序，可是要编一个程序将这些数字放入程序去执行，还是有很大的困难。思想虽理解，却无法用程序实现，还需要去更深入的学习编程的知识，才能将其应用。我明白仅仅通过课堂教学或自学获取理论知识是远远不够的，还必须加强实践，亲自上机输入、编辑、检查、修改、调试和运行各种典型算法，才更深入的理解这些算法。

第 11 页 共 11 页

5.4希尔排序的适用范围

当需要排列的序列的数据量较小，并且需要重复排序可以用希尔排序。

总结

经过几天的查资料学习，总结去写这个结课论文，起初不知道从何写起，都是一些算法，如何分析？后面看到老师给的提示，就有了思路，根据算法的排序思想、使用算法、排序的复杂度、适用范围去分析每一个排序就可以。在做这次作业的过程中发现了很多的问题，知道要写的东西，却不能很准确的描述，需要借助书才能将自己想表达的东西表述清楚。知识学得不够扎实，只知其一不知其二，有些东西无法进行。就像一些排序里的算法分析，适用范围都不知道如何的写，需要查书，查些资料，将其进行归纳总结才能成为自己的。每一个排序算法的时间复杂度或者空间复杂度都是很简单的，只要能够弄懂一个排序算法的时间复杂度或者空间复杂度，其他的就一反三都可以出来。每个算法的都是能理解思想，用数字可以将它们排序，可是要编一个程序将这些数字放入程序去执行，还是有很大的困难。思想虽理解，却无法用程序实现，还需要去更深入的学习编程的知识，才能将其应用。我明白仅仅通过课堂教学或自学获取理论知识是远远不够的，还必须加强实践，亲自上机输入、编辑、检查、修改、调试和运行各种典型算法，才更深入的理解这些算法。

第 11 页 共 11 页

本文来源：https://www.bwwdw.com/article/yq73.html