# 各种排序算法分析 原

叶大侠

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

hardyyao
11/04
0
0

2013/01/06
169
0

2012/04/10
1K
0

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

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

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