- 浏览: 190217 次
- 性别:
- 来自: 长沙
文章分类
最新评论
-
在世界的中心呼喚愛:
思路很好
连连看全局消除算法 -
tianaozhu:
请问,我修改了词库和源文件怎么就不好用了, 我源文件是: My ...
自己动手开发翻译软件(Java版) -
Arlrn:
博主你好,最近在学习排序算法,看了你的博客,你的直接插入排序, ...
各种排序算法的实现及其比较 -
sharong:
有一个明显错误,很显然冒泡排序的时间复杂度是O(n^2)
各种排序算法的实现及其比较 -
julydave:
希尔排序不太对吧。。
各种排序算法的实现及其比较
排序算法是笔试和面试中最喜欢考到的内容,今晚花了好几个小时的时间把之前接触过的排序算法都重新实现了一遍。
主要是作为复习用。当然也希望能够给大家帮上点忙。
对各种排序算法比较熟悉的朋友可以直接跳过。
常用的内部排序算法主要分为五类:插入、交换、选择、归并、基数排序。
文章的最后可能还会稍微分析一下外部排序。。。内/外部排序的区别就是 外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,在排序过程中需要多次的内/外存之间的交换。
下面一个一个分析。
(注意,本篇中讲的 lg(n) 都是以2为底的)
一、插入排序
下面讲到的这些插入排序的时间复杂度,除希尔排序是O(n的3/2次方)外,其它的都是O(n平方)。另一方面,除希尔排序外,其它的排序都是稳定的。(稳定是指相同的两个数在排序之后它们的相对位置不变。)
1、直接插入排序。
这是最简单的排序方法,它的基本基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增加1的有序表。
#include<iostream> using namespace std; int main() { int src[] = {49,38,65,97,76,13,27,49}; int i,j,cnt = sizeof(src)/4; int guard = src[0]; //设置一个哨兵,用来记录当前值 for(i = 1; i < cnt; i ++) { if(src[i] < src[i-1]) { guard = src[i]; src[i] = src[i-1]; for(j = i - 2; src[j]>guard; j --) src[j+1] = src[j]; src[j+1] = guard; } } for(i = 0; i < cnt; i ++) cout<<src[i]<<endl; //getchar(); return 0; }
2、折半插入排序
这种插入排序是上一种排序的改进,就是在查找的时候不用一个一个对比,因为前面已经有序,所以可以用折半法。
#include<iostream> using namespace std; int main() { int src[] = {49,38,65,97,76,13,27,49}; int i,j,low,high,mid,cnt = sizeof(src)/4; int guard = src[0]; for(i = 1; i < cnt; i ++) { if(src[i] < src[i-1]) { guard = src[i]; low = 0, high = i - 1; while(low <= high) { mid = (low+high)/2; if(guard < src[mid]) high = mid - 1; else low = mid+1; } for(j = i - 1; j >= high +1; j --) src[j+1] = src[j]; //后移 src[j+1] = guard; } } for(i = 0; i < cnt; i ++) cout<<src[i]<<endl; //getchar(); return 0; }
3、2-路插入排序
先读入前面两个数,大的放队首,小的放队尾,并分别用final和first作为指针指向它们,两个都向中间延伸,first向右增长,final向左减小。
如对 int src[] = {49,38,65,97,76,13,27,49_} 进行排序(这里为了区分两个49,
我给第二个49加了一个下划线。。。)
第一步得:
final | first | ||||||
49 | x | x | x | x | x | x | 38 |
放入第三个数时,和队首first和队尾final分别进行比较,如果比first大则放它右边,并用first指向它。如果比final小,则放final的左边,并用final指向它。如果大小final,小于first,则插入到当前的first或final的位置。
第二步得:
final | first | ||||||
49 | 65 | x | x | x | x | x | 38 |
第三步:
final | first | ||||||
49 | 65 | 97 | x | x | x | x | 38 |
第四步:
final | first | ||||||
49 | 65 | 76 | 97 | x | x | x | 38 |
第五步:
final | first | ||||||
49 | 65 | 76 | 97 | x | x | 13 | 38 |
第六步:
final | first | ||||||
49 | 65 | 76 | 97 | x | 13 | 27 | 38 |
第七步:
final | first | ||||||
49 | 49_ | 65 | 76 | 97 | 13 | 27 | 38 |
这样做的好处是可以减少移动的次数。。。具体的程序实现留给读者去实现。。。
4、希尔排序
又称为 缩小增量排序,它的基本思想是,先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本”有序时,再对全体记录进行一次直接插入排序。
以 int src[] = {49,38,65,97,76,13,27,49_,55,4} 为例,共有10个数,
我们先以10/2=5为跨度,进行第一趟排序。
第一趟:
49和13比较,38和27比较,65和49_比较,97和55比较,76和4比较,得:
13,27,49_,55,4,49,38,65,97,76 (从这里可以看出,希尔排序是不稳定的,当然下结论前还要看最后的结果。)
第二趟,我们以5-2=3为跨度,进行排序,可得:
13,4,49_,38,27,49,55,65,97,76 (到这时一看,有序多了!)
第三趟,心3-2=1为跨度,进行排序,得:
4,13,27,38,49_,49,55,65,76,97
当跨度减小到1时,就算是排序结束了。由结果可以断定,希尔排序是不稳定的排序。
#include<iostream> using namespace std; int main() { int src[] = {49,38,65,97,76,13,27,49,55,4}; //大家可试一试奇数个的情况 int i,j,tmp,cnt = sizeof(src)/4,dk = (cnt+1)/2,c=1; while(dk > 0) { cout<<c++<<endl; for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; for(i = dk; i < cnt; i ++) { if(src[i] < src[i-dk]) { tmp = src[i]; src[i] = src[i-dk]; src[i-dk] = tmp; } } dk = dk - 2 == 0 ? 1:dk-2; } cout<<c<<endl; for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; getchar(); return 0; }
二、交换排序
1、冒泡排序
很简单,就是相邻的两个数,两两相互比较,其特点是:每比较一次就可以得出最小/大的一个数 放到队首或队尾。它的时间复杂度也比较大:O(nlgn),冒泡排序算法是稳定的排序方式。
#include<iostream> using namespace std; int main() { int src[] = {49,38,65,97,76,13,27,49}; int i,j,cnt = sizeof(src)/4; for(i = 0; i < cnt; i ++) for(j = cnt-1; j > i; j --) if(src[j] < src[j-1]) swap(src[j],src[j-1]); //输出 for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; getchar(); return 0; }
2、快速排序
快速排序的时间复杂度达到O(nlgn),被公认为最快的排序方法之一。在所有同数量级(O(nlgn))的排序当中,其平均性能最好。它其实是冒泡排序的改进,当一列数据基本有序的时候,快速排序将为蜕化为冒泡排序,时间复杂度为O(n平方)。基本思想是 取一个数作为中间数,比它小的都排左边,比它大的都排右边(如果是从大到小排序的话,就反过来),再对每一边用同样的思路进行递归求解。快速排序是不稳定的排序方式。
#include<iostream> using namespace std; void quickSort(int *src, int low,int high) { if(src == NULL) return ; int i,j,pivot; if(low < high) { pivot = src[low]; i = low,j = high; while(i < j) { while(i<j && src[j] >= pivot) j--; src[i] = src[j]; while(i<j && src[i] <= pivot) i++; src[j] = src[i]; } src[i] = pivot; quickSort(src,low,i-1); quickSort(src,i+1,high); } } int main() { int src[] = {49,38,65,97,76,13,27,49}; int i,low,high,cnt = sizeof(src)/4; quickSort(src,0,cnt-1); //输出 for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; getchar(); return 0; }
三、选择排序
1、简单选择排序
思路很简单,就是每次选出最小/大的数,和前面的第i个数交换。时间复杂度也是 O(n平方),是不稳定的排序方式,因为在交换的过程中,相同的两个数,前者有可能被交换到后面去,举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。
#include<iostream> using namespace std; int main() { int src[] = {49,38,65,97,76,13,27,49}; int i,j,cnt = sizeof(src)/4,min ,index; for(i = 0; i < cnt; i ++) { min = INT_MAX,index = -1; for(j = i; j < cnt; j ++) { if(min > src[j]) { min = src[j]; index = j; } } if(index != i) { src[index] = src[i]; src[i] = min; } } //输出 for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; getchar(); return 0; }
2、堆排序
先用给定的数构造一棵完全二叉树,然后从下标为cnt/2(cnt指给定的数的个数)开始一个一个和它的孩子结点比较,小的就往上挪,最后得到一个小顶堆,取出堆顶,并把最后一个数放入堆顶,进行同样的操作,直到所有的数都已取完为止。我们可以用一个数组来顺序地表示这棵树,左孩子可以通过2*n来找到,右孩子可以通过2*n+1来找到。 下面给一个例子:
int src[] = {49,38,65,97,76,13,27,49};
堆排序的时间复杂度是O(nlgn),也是最快的排序方法之一,在最坏的情况下,其时间复杂度还是O(nlgn),相对于快速排序来说,这是堆排序的最大优点。此外,堆排序仅需要一个记录大小供交换用的辅助存储空间。堆排序也是不稳定的排序。
#include<iostream> using namespace std; void heapAdjust(int *src, int s,int m) { //从s开始进行一次调整,其中m指向需要进行排序的数据中最大的下标 if(src == NULL) return; int i,rc = src[s]; for(i = 2*s+1; i <= m; i = 2*i+1) //一层一层往下走 { if(i<m && src[i] < src[i+1]) i++; //让i指向最大的那个孩子 if(rc >= src[i]) break; src[s] = src[i]; s = i; } src[s] = rc; } int main() { int src[] = {49,38,65,97,76,13,27,49,1}; int i,j,cnt = sizeof(src)/4; //先构建一个小顶堆 for(i = cnt/2-1; i >-1; i --) heapAdjust(src,i,cnt-1); //每次取出顶部最大的那个数放后面,再进行一次顶点调整 for(i = cnt-1; i > 0; i --) { swap(src[0],src[i]); heapAdjust(src,0,i-1); } //输出 for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; getchar(); return 0; }
四、归并排序
归并的意思就是两个或两个以上的有序表组合成一个新的有序表。整个归并排序需要进行【lgn取上限】次,总的时间复杂度为O(nlgn)。与快速排序相比,归并排序的最大特点是:它是一种稳定的排序方法。
如上图,这是一种2-路归并排序,通常用递归方法来实现,递归的形式的算法在形式上较简洁,但实用性很差。
#include<iostream> using namespace std; void merge(int* src,int i,int m,int n) { //开辟一个临时的空间来存放归并后的结果 int *des = (int*)malloc(sizeof(int)*n); int k = i,mm = m++,low = i; //把数组的两部分,一个一个地放入临时数组中,小的先放 while(i <= mm && m <= n) if(src[i] <= src[m]) des[k++] = src[i++]; else des[k++] = src[m++]; //把剩余的放入数组 while(i <= mm) des[k++] = src[i++]; while(m <= n) des[k++] = src[m++]; //把结果拷贝回原数组 for(k = low; k <= n; k++) src[k] = des[k]; } void mergeSort(int* src, int s, int t) { if(src == NULL) return ; int m; if(s < t) { m = (s+t)/2; //取中间值 mergeSort(src,s,m); //递归地将src[s..m]归并为有序的des[s..m] mergeSort(src,m+1,t); //递归地将src[m+1..t]归并为有序的des[m+1..t] merge(src,s,m,t); } } int main() { int src[] = {49,38,65,97,76,13,27,49}; int i,j,cnt = sizeof(src)/4; mergeSort(src,0,cnt-1); //输出 for(i = 0; i < cnt; i ++) cout<<src[i]<<" "; cout<<endl; getchar(); return 0; }
五、基数排序
所谓的基数排序 其实就是一种多关键字的排序,最经典的例子就是英语字典的编排,先按第一个字母排列,分成26堆,再按第二个字母排列,……以此类推。。。更复杂的基本排序作者本人也没有研究过,有兴趣的朋友可以去网上找相关的资料。
六、各种内部排序的比较
1、时间复杂度达到O(nlgn) 的排序算法有:快速排序、堆排序、归并排序。
2、上面前四大类排序中,不稳定的排序有:希尔排序、快速排序、堆排序、简单的选择排序。
稳定的排序有:插入排序(除希尔外)、冒泡排序、归并排序。
3、从平均时间性能而言,快速排序最佳,其所需要的时间最少,但快速排序在最坏的情况下,时间性能还不如堆排序和归并排序。
七、外部排序
外部排序指的是大文件的排序,面试的时候,面试官喜欢问,给你一个非常非常大的文件(比如1T),一行一个数(或者一个单词),内存最多只有8G,硬盘足够大,CPU很高级……然后要你给这个文件里面的数据排序。你要怎么办?
这其实就要用到外部排序。就是说要借助外存储器进行多次的内/外存数据的交换,因为内存不足以加载所有的数据,所以只能一部分一部分地加载。
所以外部排序的思想就是:分两个独立的阶段。
首先,可按内存的大小,将外存上含n个记录的文件分成若干长度为 x 的子文件或段,依次读入内存,并利用有效的内部排序方法对它们进行排序,并将排序后得到的有序子文件 重新写入外存,通常称这些有序的子文件为归并段或顺串。然后,对这些归并段进行逐趟归并,使归并段逐渐由小到大,直至得到整个有序文件为止。
因此现在的问题就转化为如何归并两个大文件。这个读者朋友们想一下就明白了。就是把这两个文件按内存的大小,一部分一部分从小到大加载出来并,再写回外存。
当然归并的方法有很多种,作者本人也没怎么去研究。。。
说明:本篇日志欢迎转载,但请标明出处:http://lingyibin.iteye.com/blog/1043886
评论
好地!
发表评论
-
连连看全局消除算法
2012-03-08 01:48 4273好久没写技术博客了。I ... -
一个简单的字符组合算法
2011-07-27 13:18 1179有个朋友问了我这个问 ... -
STL在ACM中的应用
2011-04-09 01:41 2295STL 提供三种类型的组件:容器、迭代器和算法,它们都支持泛型 ... -
完全背包问题
2011-03-29 23:01 1644看这篇日志之前,请先阅读我的上一篇日志,关于0/1背包 ... -
0/1背包问题的动态规划详解
2011-03-29 22:57 1478动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题 ... -
最长上升子序列问题的几种解法
2011-03-29 22:55 2491拿POJ 2533来说。 Sample Input 7 ... -
用BFS找最短路,并打印路径
2010-12-23 02:19 6076我想大部分读者都用Floyd或者Dijstra算法,甚至dfs ... -
插入排序的另一种写法
2010-12-14 01:39 1142一般的插入排序方法想必大家都写过,基础好的几分钟就可以写出来了 ... -
北大ACM题库习题分类与简介
2010-12-06 13:57 1714acm.pku.edu.cn转自:http://www.stu ... -
POJ1753-位操作
2010-11-03 01:30 1079Flip Game Time Limit ...
相关推荐
C语言中常见排序算法:冒泡排序法、选择排序法、插入排序法、快速排序法、希尔排序法、堆排序法等6种算法及其实现。
各种内部排序方法及其比较实验报告
这里提供了冒泡排序,插入排序,递归排序,基数排序,快速排序,选择排序,希尔排序这几种排序算法。里面有大量的注释,可以理解实现思路
软件技术基础 数据结构 排序算法 查找算法
3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就无需比较flag之后的序列,即只要比较到flag就可以结束此次冒泡过程。当flag=0时,...
快速排序 归并排序 希尔排序掌握常用的排序方法,并掌握用高级语言实现排序算法的方法; 深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用; 了解各种方法的排序过程及其依据的原则,并掌握各种排序方法...
用java实现了几种常见的排序算法 并对它们的性能进行了详细的分析和比较
排序算法是计算机科学中最基本且常见的算法之一。排序的目标是将一组数据按照升序或降序的方式进行排列。在实际编程中,选择适当的排序算法对于提高程序性能和效率至关重要...下面简要介绍几种常见的排序算法及其实现。
java实现各种排序算法及其速度对比(附详细代码)(csdn)————程序
http://blog.csdn.net/holmofy/article/details/70245895 文章的实现代码
基于java语言,通过实验,详细对比了几种常见的排序算法的性能
八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序,归并排序,基数排序在内的八种排序算法,同时对各种算法的基本特征做出了详细分析: - 算法基本思想 - 算法的...
自己刚刚开始学习排序算法,第一个排序算法:冒泡排序。以及在学习过程中做的一些笔记。
调试实现快速排序算法。 1.掌握快速排序算法思想,及其适用条件。 2.编写与实验内容相关的程序,要求具有演示功能。
一种双向冒泡排序算法的C语言实现及其效率分析.pdf
【C语言】排序及查找算法及其实现.ppt
## 九种内部排序算法的Java实现及其性能测试 ### 9种内部排序算法性能比较 第九种为java.util.Arrays.sort(改进的快速排序方法) 1. 100000的随机数据集 ![](http://7xlkoc.com1.z0.glb.clouddn.com/sort1.jpg) ...
java, 排序算法及其改进
实现一组经典的排序算法,通过实验数据的设计,考察不同规模和分布(正 序序列、反序序列和随机序列)的数据对排序算法运行时间影响的规律,验证理 论分析结果的正确性。 实验要求: 1. 实现以下三组排序方法中的...