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

代码实现

• java