文档章节

各种排序算法分析

叶大侠
 叶大侠
发布于 2012/11/25 13:15
字数 1179
阅读 262
收藏 17

1、插入排序

for i = 2:n,
      for (k = i; k > 1 and a[k] < a[k-1]; k--) 
        swap a[k,k-1]
              → invariant: a[1..i] is sorted
    end

最差效率: O(n2) 倒序的时候 如把abcd排成dcba

最好效率:O(n) 顺序的时候.

额外空间O(1),需要一个额外的空间.

排序稳定性:属于稳定的排序算法.(两个元素相等时排序前后相对位置不变)

因此,该算法如果能使用在预知串是基本有序的情况下是非常有潜力的.在合并排序和希尔排序中就结合了这个特点,提高算法效率.

2、选择排序

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

无论是什么情况,其效率都保持在O(n2).

额外空间O(1),需要一个额外的交换空间.

排序稳定性:属于不稳定的排序算法.

出名是有理由的,尽管在效率上不怎么好看,但是留意一下,它产生的swap最多时也就是n-1次.在这一点上优于其他排序的,因此,在交换的动作比较耗时的情况下,该算法还是有用武之地的.

3、冒泡排序

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

效率也是O(n2).

额外空间O(1).

稳定排序

没想到有什么地方好用的...估计是名字好记,所以才出名的.(如果你有好的想法,请一定要告诉我)

4、希尔排序

h = 1
while h < n, h = 3*h + 1 //构造一个增量序列,
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]//一般化的插入排序,表示增量为h的插入排序 
    → invariant: each h-sub-array is sorted
end

效率和(增量序列/源排序序列)有关.(这里为O(n3/2),具体怎么算出来的我也没搞清楚,有机会会补上来),在基本有序的情况下能达到O(n·lg(n))。

额外空间O(1)

虽然是基于插入排序的,但是是非稳定的排序

相比上面三种排序,在平均效率上有一定地提高,但总的来说还是属于比较低效的算法.

5、归并排序

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

 效率:属于即使在最坏情况下也不会低于O(nlogn)的高效排序。具体过程见http://my.oschina.net/daxia/blog/91577

 额外空间:O(n),该算法的最不好的地方就是它的额外空间比较大。

 稳定排序,在底层使用的是插入排序,然后在归并过程也没有改变相同元素顺序.

6、快速排序

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

如其名:快速排序,虽然在最坏的情况下它可能会退化到O(n2),但是在大多随机情况下它的速度都逼近O(nlogn),因此,它是一个O(nlogn)的排序算法.

额外空间O(1).

不稳定排序

快速排序在处理内层循环时的效率非常高,使得在处理随机排列的数组时,速度要比合并排序和堆排序快.另外除了二路的平均分区,还有更加高效的三路平均分区-》http://www.sorting-algorithms.com/quick-sort-3-way

7、堆排序

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

效率:O(nlogn)

一个额外空间O(1)

不稳定排序

有针对随机文件的计时实验指出,堆排序比快速排序运行的慢,但是和合并排序还是有竞争力的.

 

参考和动画演示: http://www.sorting-algorithms.com

参考书籍:《算法设计与分析基础》和《数据结构》严蔚敏/吴伟明 版

 

 

 

© 著作权归作者所有

共有 人打赏支持
叶大侠

叶大侠

粉丝 59
博文 44
码字总数 67312
作品 5
广州
程序员
私信 提问
内部排序算法的实现与比较-数据结构课程设计

内部排序算法的实现与比较 1) 问题描述 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移...

zhagoodwell
2017/11/06
0
0
排序算法 Sleep Sort

排序算法好像是程序员学习编程最多的算法,也可能是算法研究者们最喜欢研究的算法了。排序有很多很多的算法,比如,冒泡,插入,选择,堆,快速,归并等等(你可以看看本站以前的那些文章:可...

小卒过河
2011/06/23
1K
2
排序(上):冒泡排序、插入排序和选择排序

如何分析一个排序算法? 分析一个排序算法的三要素:排序算法的执行效率、排序算法的内存消耗以及排序算法的稳定性。 排序算法的执行效率 对于排序算法执行效率的分析,一般是从以下三个方面...

hardyyao
11/04
0
0
各种基本算法实现小结(五)—— 排序算法

各种基本算法实现小结(五)—— 排序算法 (均已测试通过) 选择排序 |简单选择排序 |堆排序 |归并排序 交换排序 |冒泡排序 |快速排序 插入排序 |直接插入排序 |折半排序 |希尔排序 分配排序...

长平狐
2013/01/06
169
0
使用C语言去掉字符串集合重复元素

有一种最直接的方法可以去掉一个集合中重复的元素,这种方法据说就是“交给下面去做”,然而有时候,你自己动手去做一下也是不错的。如果交给下面去做,最直接的选择就是使用map,在java中,...

晨曦之光
2012/04/10
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

Win10:默认的图片打开应用,打开图片时速度明显很慢的解决办法

首先,我们随便地打开一张图片。然后,点击右上角的三个小点,最后点击弹出菜单最下面的“设置”。如下图: 在“设置”中找到下面的“人物”,把它关掉就好了。 原来,默认情况下,Win 10的图...

LivingInFHL
44分钟前
2
0
js代码激发onchange事件,兼容谷歌火狐IE

var el = document.getElementsByName('role')[0]; el.value = '3'; var evt = document.createEvent("HTMLEvents"); evt.initEvent("change", false, true); el.dispatchEvent(evt);......

我退而结网
59分钟前
3
0
mysql客户端报错:libmysqlclient_16 not defined in file libmysqlclient.so.16

报错情况: 安装完mydumper之后(上一篇文章),登陆Mysql客户端报错:version libmysqlclient_16 not defined in file libmysqlclient.so.16 with link time reference 同样:mysql的其他客...

machogyb
今天
1
0
MySQL 数据库中间件 安装部署测试全过程

1、环境准备 1.1、操作系统环境 [root@MyCat conf]# uname -aLinux MyCat 2.6.32-431.el6.x86_64 #1 SMP Sun Nov 10 22:19:54 EST 2013 x86_64 x86_64 x86_64 GNU/Linux 1.2、关闭SELIN......

PeakFang-BOK
今天
6
0
Linux Mysql 安装

https://www.cnblogs.com/xinjing-jingxin/p/8025805.html

流氓兔-
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部