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

chap2 算法基础

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

内容

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

伪代码

1.Insertion Sort(A) -----

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

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

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

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

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

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

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

代码实现

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注