注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

常见的排序算法  

2015-06-08 16:38:05|  分类: 常用算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1.冒泡排序

算法原理:消除相邻元素不符合顺序的pair,每一次相邻之间的元素比较,如果前一个大于后一个元素则交换,所以第一趟扫描会将最大的元素放在序列尾,第二趟将第二大元素放在倒数第二的位置,直到最后完成排序,该算法是稳定排序

常见的排序算法 - HT - HT·生活

 

冒泡排序过程

改进:冒泡过程需要将所有的交换完成后才能确定是否排序完成,但是程序中间可能到了某一趟的时候已经完成排序了。所以在中间加一个flag,如果某一趟扫描没有交换出现,则排序完成,直接break,加快了排序进程。

分析:时间平均复杂度O(n^2),最坏复杂度O(n^2),空间复杂度O(1),稳定排序。

2.选择排序

算法原理:每一次扫描将最小的元素放在序列的起始位置,扫描过程不发生交换,只记录最小值下标,一趟扫描完成之后再进行交换,扫描n次后,就完成了排序。该算法是不稳定排序,如[5 5 3],第一次的时候,3和第一个5进行交换,导致第二个5挪到第一个前面,从而破环了稳定性。算法过程如下:

选择排序的过程

分析:时间平均复杂度O(n^2),最坏复杂度O(n^2),空间复杂度O(1),不稳定排序。一般情况下,选择排序过程交换次数比冒泡少,所以在n较小的情况下,选择排序比冒泡稍微快一些。

3.插入排序

算法原理:向一个有序的数列中插入新的数据,使新的数列保持有序,也是比较排序的一种。

 

常规插入排序的过程

改进:二分查找,shell排序。

分析:时间平均复杂度O(n^2),最坏复杂度O(n^2),空间复杂度O(1),稳定排序。

4.shell排序

算法原理:上面讲的插入排序是shell排序的一种特殊情况,shell排序是一种带有gap的插入排序,每次抽取一定间隔d的数,进行插入排序,间隔d需要不断减小直到1。这种排序方式比常规的插入排序有很大改进,到了gap为1的时候基本上已经是有序的了,减少了插入排序中的大量交换、移动。

Shell排序过程

分析:时间平均复杂度O(nlogn),最坏复杂度O(n^s,1<s<2),空间复杂度O(1),不稳定排序。

 5.快速排序

算法原理:快排过程用到了分治的思想,首先选取一个轴元素pivot在q位置,然后数组化为A[p…q-1]和A[q+1…r]分别进行排序,大于pivot的在右边,小于pivot的在左边,然后合并。

快速排序的伪代码

    伪代码最主要的就是一个划分过程,在划分过程中3->6完成的工作是把比x也就是pivot小的数放到左边去,这里每次都选择A[r]作为pivot,最后把A[r]放到pivot应该在位置,并且返回新的pivot的index。

分析:时间平均复杂度O(nlogn),最坏复杂度O(n^2),空间复杂度O(nlogn),不稳定排序。它的复杂和他的划分过程密切相关,划分越平均复杂度就越接近nlogn。

6.归并排序

算法原理:归并排序是一种典型的分治排序方式,每次排序需要将数据分成2份或者多份,然后递归进入到下一层,直到最后集合中只剩一个元素或者两个元素,一旦下层排序完成,上一层就可以进行merge,完成排序过程。

归并过程 归并伪代码

 

分析:时间平均复杂度O(nlogn),最坏复杂度O(nlogn),空间复杂度O(1),稳定排序。

7.堆排序

算法原理:堆排序其实就是基于维护最大堆性质的排序方式,该排序方式包含两个过程,一个是构建最大堆,第二个过程是维护堆顶性质(排序)过程。建立最大堆的过程可以在线性时间O(n)内完成。

第二个过程,每次弹出堆顶,将堆的最后一个元素删掉,并放到堆顶,接着维护最大堆的性质,需要的操作是logn,而总共需要弹出n次堆顶,所以时间复杂度就是nlogn。

 

 

分析:时间平均复杂度O(nlogn),最坏复杂度O(nlogn),空间复杂度O(1),不稳定排序。

  8.计数排序

算法原理:前面的6种排序方式全部属于比较排序,而比较排序在理论上得到证明,算法复杂度的下限是nlogn,这里的后面的特殊的排序不需要进行比较,所以可以达到线性复杂度的排序效果。计数排序需要一个额外的空间来维护原有数列中数字在整个序列中的位置,或者说小于这个数的所有数字的个数。

计数排序的伪代码

排序过程

 

A是元数组,C[i]表示A中比i小的数字的个数。A从最后一个数字3,它的在C中位置为6,那么,就应该放在第7位,所以3放在第7位,同时C[3]位置应该-1,因为这个位置已经拿了一个出来了。后面的依次这样操作。数组中需要维护一个特定的C的空间大小,需要排列的数字的范围就是0~k。

分析:时间平均复杂度O(n),最坏复杂度O(n),空间复杂度O(k),稳定排序。

  9.基数排序

算法原理:基数排序一般是以计数排序为基础的,它是一种按位排序的方式。假设这里用的子排序过程是计数排序,基数排序就是先排个位数,再排十位,再排高位,所有的都排列完成够,数列就变成有序的了。假设这里总共有d位,而k=10,因为数字是0~9,当然也可以是0-99。排序过程的复杂度就是d个O(n+k),所以基数排序的复杂度就是O(d(n+k))。

基数排序过程

分析:时间平均复杂度O(d(n+k)),最坏复杂度O(d(n+k)),空间复杂度O(k),稳定排序。

10.桶排序

算法原理:桶排序假设数据服从均匀分布,对于计数排序,它是假定数据分布再0-k区间。桶排序过程将0-1区间的序列划分成n个大小相同的桶,然后让序列中的数字均匀分布到这n个桶里面。理论情况下,每个桶里面刚好一个,所以自动就有序了。如果很不幸,有的桶里面多于一个元素,就需要进行桶内排序,但是还是已经证明了,再满足某种情况下,桶排序仍然能在线性时间内完成。所以复杂度是O(n)。

分析:时间平均复杂度O(n),最坏复杂度O(n),空间复杂度O(2n),稳定排序。桶排序适合对很少重复的记录排序

 

 

综合

 

排序法

平均时间

最差情形

稳定度

额外空间

备注

冒泡

O(n2)

O(n2)

稳定

O(1)

n小时较好

选择

O(n2)

O(n2)

不稳定

O(1)

n小时较好

插入

O(n2)

O(n2)

稳定

O(1)

大部分已排序时较好

计数

O(n+k)

O(n+k)

稳定

O(n)

数据分布在小区间

基数

O(d(n+k))

O(d(n+k))

稳定

O(n)

 

Shell

O(nlogn)

O(ns) 1<s<2

不稳定

O(1)

s是所选分组

快速

O(nlogn)

O(n2)

不稳定

O(nlogn)

n大时较好

归并

O(nlogn)

O(nlogn)

稳定

O(1)

n大时较好

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

桶排

O(n)

O(n)

O(n)

适合不重复的数据

 

 

参考

网上看到一个很棒的专栏,比我写的还详细很多,可以看看

http://blog.csdn.net/touch_2011/article/details/6767673

  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017