进行四次交换后：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
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 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 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 页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析与设计和C++中不同排序算法的分析(2)在线全文阅读。
相关推荐：