yhcast

# 1. 选择排序

• 第一个元素下标为1
• 最后一个元素下标为A.length
• n = A.length

• 最优：θ(n^2)
• 最差：θ(n^2)

``````SELECTION_SORT(A)
for i=1 to A.length - 1
indexForMin = i
for j=i+1 to A.length
if A[j] < A[indexForMin]
indexForMin = j
swap A[i] with A[indexForMin]
``````

# 2. 插入排序

• 第一个元素下标为1
• 最后一个元素下标为A.length

• 最优：θ(n)
• 最差：θ(n^2)

``````INSERTION_SORT(A)
for i=2 to A.length
key = A[i]
j = i - 1
while j > 0 and A[j] > key
A[j+1] = A[j]
j--
A[j+1] = key
``````

# 3. 希尔排序(Shell Sort)

• 第一个元素下标为1
• 最后一个元素下标为A.length
• floor()表示向下取整
• n = A.length

• 最优：θ(n)
• 最差：θ(n^2)

``````SHELL_SORT(A)
for (gap = floor(n/2); gap > 0; gap = floor(gap/2))
for (i = gap+1; i <= n; i++)
key = A[i]
j = i - gap
while(j > 0 and A[j] > key)
A[j+gap] = A[j]
j -= gap
A[j+gap] = key
``````

# 4. 冒泡排序

• 第一个元素下标为1
• 最后一个元素下标为A.length

• 最优：θ(n) 或 θ(n^2) 取决于具体算法
• 最差：θ(n^2)

``````BUBBLE_SORT(A)
for i = 1 to A.length - 1
for j = A.length to i + 1
if A[j] < A[j-1]
swap A[j] with A[j-1]

or

BUBBLE_SORT(A)
sorted = false
while !sorted and unsorted_head < A.length
sorted = true
for i = A.length down to unsorted_head + 1
if A[i] < A[i-1]
sorted = false
swap A[i] with A[i-1]
``````

# 5. 鸡尾酒排序

• 第一个元素下标为1
• 最后一个元素下标为A.length

• 最优：θ(n)
• 最差：θ(n^2)

``````COCKTAIL_SORT(A)
sorted = false
begin = 0
end = A.length - 1
while !sorted
sorted = true
++begin
for i = begin to end    // 从左往右比较
if A[i] > A[i+1]
sorted = false
swap A[i] with A[i+1]
if sorted    // 如果排序完成，退出while循环
break while loop
sorted = true
--end
for i = end down to begin    // 从右往左比较
if A[i] > A[i+1]
sorted = false
swap A[i] with A[i+1]
``````

# 6. 归并排序

• 第一个元素下标为1
• 最后一个元素下标为A.length
• 3个整数p, q, r，其中 p <= q < r
• floor()表示向下取整

``````MERGE_SORT(A, p ,r)
if p < r
q = floor((p + r) / 2)
MERGE_SORT(A, p ,q)
MERGE_SORT(A, q+1, r)
MERGE(A, p, q, r)

MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1 ... n1] and R[1 ... n2] be new arrays
for i=1 to n1
L[i] = A[p+i-1]
for j=1 to n2
R[j] = A[q+j]
i = 1
j = 1
for k=p to r
if (j > n2) or (i <= n1 and L[i] < R[j])
A[k] = L[i]
i += 1
else
A[k] = R[j]
j += 1
``````

# 7. 快速排序

• 第一个元素下标为1
• 最后一个元素下标为A.length
• 默认主元(pivot)为数组的第一个元素

``````QUICK_SORT(A, first, last)
if last > first
pivotIndex = PARTITION(A, first, last)
QUICK_SORT(A, first, pivotIndex-1)
QUICK_SORT(A, pivotIndex+1, last)

PARTITION(A, first, last)
pivot = A[first]
lowIndex = first + 1
highIndex = last
while highIndex > lowIndex
while lowIndex <= highIndex and A[lowIndex] <= pivot
lowIndex++
while lowIndex <= highIndex and A[highIndex] > pivot
highIndex--
if highIndex > lowIndex
swap A[lowIndex] with A[highIndex]
while highIndex > first and A[highIndex] >= pivot
highIndex--
if pivot > A[highIndex]
A[first] = A[highIndex]
A[highIndex] = pivot
return highIndex
else
return first
``````

### yhcast

CheN_exe
2014/01/26
0
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础，在BAT的初面中，会涉及到比较多的java基础知识，所以比较重要，下面我介绍的书籍内容是由浅到深。 1.Thinking in java：这本书被称为Java的三大圣经之一，虽然书比...

android自学
07/25
0
0

pointerException
2015/07/29
0
0

Author: bakari 　　Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书，爱自然是因为它精简凝练的算法呈现，读来让人欲罢不能；至于恨，是因为它在进行算法分析的时候所体现的数学思想...

chambai
2015/09/11
0
0
Android 面试文档分享

2017/11/10
0
0

Idea

command + E : 打开最近编辑过的文件 command + shift + O : 打开指定文件 command + O : 打开指定类 shift+command+delete 打开上一次编辑过的地方 option + command + t 代码块包含 option...

xpttxsok
37分钟前
2
0
FTP 协议 1.0

Explorer0
47分钟前
2
0
Android 通过DrawableInflater加载自定义Drawable

IamOkay
59分钟前
3
0

yizhichao

1
0