文档章节

各种排序算法分析

叶大侠
 叶大侠
发布于 2012/11/25 13:15
字数 1179
阅读 259
收藏 17
点赞 0
评论 0

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

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

 

 

 

© 著作权归作者所有

共有 人打赏支持
叶大侠

叶大侠

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

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

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

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

小卒过河
2011/06/23
1K
2
各种基本算法实现小结(五)—— 排序算法

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

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

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

晨曦之光
2012/04/10
1K
0
各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(六)—— 查找算法 (均已测试通过) =================================================================== 1、简单查找 在一组无序数列中,查找特定某个数值,并返...

长平狐
2013/01/06
75
0
Java实现几种常见排序方法(下)

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。 /** 插入排序<br/> <ul> <li>从第一个元素开始,该元...

晨曦之光
2012/03/09
0
0
排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien
2016/06/17
41
0
各种排序算法及其java程序实现

各种排序算法:冒择路(入)兮(稀)快归堆,桶式排序,基数排序 冒泡排序,选择排序,插入排序,稀尔排序,快速排序,归并排序,堆排序,桶式排序,基数排序 一、冒泡排序(BubbleSort) 1. 基本思...

长平狐
2012/11/12
191
0
各种排序算法分析与比较

首先,请允许我用这样的题目来作为本博文的题目,但是目前也想不到其他好的题目,所以就先定为这个题目吧。 排序算法对于数据结构和算法课程来说都是非常重要的内容,在数据结构中,排序算法...

长平狐
2013/12/25
178
0
学习数据结构与算法,成为出色的程序员

原文出处:Happy Bear 译文出处:LCTT - icybreaker “相较于其它方式,我一直热衷于推崇围绕数据设计代码,我想这也是Git能够如此成功的一大原因[…]在我看来,区别程序员优劣的一大标准就在...

Happy Bear
2015/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

编程语言对比分析:Python与Java和JavaScript(图)

编程语言对比分析:Python与Java和JavaScript(图): 凭什么说“Python 太慢,Java 太笨拙,我讨厌 JavaScript”?[图] 编程语言生而为何? 我们人类从原始社会就是用语言表达自己,互相沟通...

原创小博客
10分钟前
0
0
Akka构建Reactive应用《one》

看到这Akka的官网,描述使用java或者scala构建响应式,并发和分布式应用更加简单,听着很高级的样子,下面的小字写着消息驱动,但是在quickstart里面又写容错事件驱动,就是这么钻牛角尖。 ...

woshixin
22分钟前
0
0
ffmpeg源码分析 (四)

io_open 承接上一篇,对于avformat_open_input的分析还差其中非常重要的一步,就是io_open,该函数用于打开FFmpeg的输入输出文件。 在init_input中有这么一句 if ((ret = s->io_open(s, &s-...

街角的小丑
24分钟前
0
0
String,StringBuffer ,StringBuilder的区别

不同点 一、基类不同 StringBuffer、StringBuilder 都继承自AbStractStringBuilder,String 直接继承自 Object 2、底层容器“不同” 虽然底层都是字符数组,但是String的是final修饰的不可变...

不开心的时候不要学习
39分钟前
0
0
nodejs 文件操作

写文件code // 加载文件模块var fs = require("fs");var content = 'Hello World, 你好世界!';//params 文件名,内容,编码,回调fs.writeFile('./hello.txt',content,'utf8',function (er......

yanhl
41分钟前
0
0
SpringBoot mybits 查询为0条数据 但是在Navicat 中可以查询到数据

1.页面请求: 数据库查询: 2018-07-16 17:56:25.054 DEBUG 17312 --- [nio-9010-exec-3] c.s.h.m.C.selectSelective : ==> Preparing: select id, card_number, customer_id, customer_nam......

kuchawyz
51分钟前
0
0
译:Self-Modifying cod 和cacheflush

date: 2014-11-26 09:53 翻译自: http://community.arm.com/groups/processors/blog/2010/02/17/caches-and-self-modifying-code Cache处在CPU核心与内存存储器之间,它给我们的感觉是,它具......

我叫半桶水
54分钟前
0
0
Artificial Intelligence Yourself

TensorFlow是谷歌基于DistBelief进行研发的第二代人工智能学习系统,其命名来源于本身的运行原理。Tensor(张量)意味着N维数组,Flow(流)意味着基于数据流图的计算,TensorFlow为张量从流...

孟飞阳
今天
0
0
press.one个人数字签名

这是我在press.one的数字签名 https://press.one/p/address/v?s=9d3d5b7ce019af357ab994775549e8f047a5b17fc9893364652fc67e4b95443b38ccb24c6655e0d252dd0154369eb9b7717c4ccf4e1835ca3596......

NateHuang
今天
1
0
Oracle 中的 SQL 分页查询原理和方法详解

本文分析并介绍 Oracle 中的分页查找的方法。 Oracle 中的表,除了我们建表时设计的各个字段,其实还有两个字段(此处只介绍2个),分别是 ROWID(行标示符)和 ROWNUM(行号),即使我们使用...

举个_栗子
今天
4
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部