@zqbinggong 2018-03-06T13:36:37.000000Z 字数 1505 阅读 371

# chap2 算法基础

插入排序 分治模式 归并排序 算法导论

## 内容

1. 插入排序：适用于输入规模较小的情况，运行时间$\Theta \left ( n^{2} \right )$
2. 分治模式：将原问题分解成子问题，解决子问题，合并子问题的解得到原问题的解，本质上来讲，由于减少了了重复运算而使速度变快
3. 归并排序：遵从分治模式，将原序列分解成n/2的子序列，并递归的排序子序列，运行时间$\Theta \left ( n\lg n \right )$
4. 注意，由于常数项以及系数的关系，当n较小时，插入排序的速度可能更快
5. 其他算法（出现在习题中): 选择排序，冒泡排序,逆序对

## 伪代码

1.Insertion Sort(A) ----- $\Theta \left ( n^{2} \right )$

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


2.Merge Sort(A,p,r) ------$\Theta \left ( n\lg n \right )$

if p < r
q = (p+r)/2 #向下取整
Merge Sort(A,p,q)
Merge Sort(A,q+1,r)
Merge(A,p,q,r)


Merge(A,p,q,r) ----- $\Theta \left ( n \right )$

n1 = q-p+1
n2 = r-q
let L[1...n1+1] and R[1...n2+1] be bew arrays
for i = 1 to n1
L[i] = A[p+i-1]
for j = 1 to n2
R[j] = A[q+j]
L[n1+1] = R[n2+1] = 00  #setinel cards
i = j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i += 1
else
A[k] = R[j]
j += 1


3.其他,

3.1Selection Sort(A) ----- $\Theta \left ( n^{2} \right )$

n = A.length
for i = 1 to n
smallest = i
for j = i+1 to n
if A[j] <= A[smallest]
smallest = j
exchange A[i] with A[smallest]


3.2 Bubble Sort(A) ----- $\Theta \left ( n^{2} \right )$

n = A.length
for i = 1 to n-1
for j = n downto i+1
if A[j] < A[j-1]
exchange A[j] with A[j-1]


3.3 Count Inversions ------$\Theta \left ( n\lg n \right )$

inversions = 0
if p < r
q = (p+r)/2 #向下取整
inversions = inversions + Count Inversions(A,p,q)
inversions = inversions + Count Inversions(A,q+1,r)
inversions = inversions + Merge Inversions(A,p,q,r)


Merge Inversions(A,p,q,r) ----- $\Theta \left ( n \right )$

n1 = q-p+1
n2 = r-q
let L[1...n1+1] and R[1...n2+1] be bew arrays
for i = 1 to n1
L[i] = A[p+i-1]
for j = 1 to n2
R[j] = A[q+j]
L[n1+1] = R[n2+1] = 00  #setinel cards
i = j = 1
inversion = 0
for k = p to r
if L[i] > R[j]
inversions = inversions + n1-i+1
A[k] = R[j]
j += 1
else
A[k] = L[i]
i += 1
return inversion


## 代码实现  • 私有
• 公开
• 删除