# 各种排序算法分析 原

叶大侠

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``````

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``````

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``````

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``````

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]``````

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)``````

### 叶大侠

zhagoodwell
2017/11/06
0
0

2011/06/23
1K
2

2013/01/06
169
0

2012/04/10
1K
0

2013/01/06
75
0
Java实现几种常见排序方法（下）

2012/03/09
0
0

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

Corwien
2016/06/17
41
0

2012/11/12
191
0

2013/12/25
178
0

Happy Bear
2015/11/10
0
0

10分钟前
0
0
Akka构建Reactive应用《one》

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的区别

39分钟前
0
0
nodejs 文件操作

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

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个人数字签名

NateHuang

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

4
2