插入排序

输入:n个数的一个序列\left\langle a _ { 1 } , a _ { 2 } , \dots , a _ { n } \right\rangle
输出:输入序列的一个排序\left\langle a _ { 1 } ^ { \prime } , a _ { 2 } ^ { \prime } , \cdots , a _ { n } ^ { \prime } \right\rangle,满足a _ { 1 } ^ { \prime } \leqslant a _ { 2 } ^ { \prime } \leqslant \cdots \leqslant a _ { n } ^ { \prime }

我们可以循环这个序列中的每一个数,然后将它移动到它应该在的位置:
image.png
因为前面的数都是排好序的,所以移动整个列表后会得到拍好序的序列.

def insert_sort(A):
    # 循环序列中的每一个数
    for j in range(1,len(A)):
        key = A[j]
        i = j -1
        # 对其和前面的数进行比较,如果前面的数大则将其向后移
        while i>=0 and A[i]>key:
            A[i+1] = A[i]
            i -= 1
        # 当前面的数小时,将其插入
        A[i+1] = key
    return A

分析插入排序

现在我们来分析一下每行代码执行的次数,循环头比循环体多执行一次,假设循环头执行n次,循环体里面的语句执行n-1次.

循环体中while执行的次数取决于序列的顺序,设每次while循环执行t_j次,则while共执行\sum_{j=1}^n t_j次,最坏的情况是序列A是倒序的,此时while执行次数t_j = j,即while共执行\sum_{j=1}^n j次.这是个等差数列,其和为:

\sum_{j=1}^n j = \frac{1}{2}n(n-1)

整个算法的执行次数由n的二次项,一次项及常数项组成,所以可以表示为a n ^ { 2 } + b n + c,因此排序算法的运行时间是n的二次函数.

当n足够大时,低阶项和常数项和常数项相对不那么重要,我们只关心最高阶项,可以记插入排序的运行时间为\Theta \left( n ^ { 2 } \right)

并归排序

并归排序使用了分治法的思想:

  1. 将一个复杂的问题分成若干小问题.
  2. 逐个解决这些小问题.
  3. 合并这些小问题成原始问题.

下图是使用并归排序解决排序问题的示意图:
image.png

def merge(A,p,q,r):
    # 获取这两个数组的长度
    n1 = q - p +1
    n2 = r - q
    
    # 建立两个新数组
    L = A[p:q+1]
    R = A[q+1:r+1]
    L.append(float('inf'))
    R.append(float('inf'))
    
    #逐个比较L和R中的元素,谁小取谁
    i = 0
    j = 0
    for k in range(p,r+1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

# 递归的找中间值,将大任务分割成小任务
def merge_sort(A,p,r):
    if p < r:
        q = int((p+r)/2)
        merge_sort(A,p,q)
        merge_sort(A,q+1,r)
        merge(A,p,q,r)

def bg_sort(A):
    merge_sort(A,0,len(A)-1)

A = [5,2,4,7,1,3,2,6]
bg_sort(A)
print(A)

分析分治算法

假设T(n)是规模为n的一个问题的运行时间.若问题规模足够小,如对某个常量c,n \leq c,则直接求解需要常量时间,我们将其写作\Theta(1).假设把原问题分解成a个子问题,每个子问题的规模是原问题的1/b.(对于并归排序,ab都为2,然而,许多分值算法,a \neq b)为了求解一个规模为n/b的子问题,需要T(n/b)的时间,所以需要aT(n/b)的时间来求解a个子问题.如果分解成子问题需要时间D(n),合并子问题的解成原问题的解需要时间C(n),那么得到递归式:

T(n)=\begin{cases}
\Theta ( 1 )&若n\leq c \\
a T ( n / b ) + D ( n ) + C ( n )&其他
\end{cases}

分析并归排序算法

在并归排序算法中:
分解:分解仅仅计算中位数,所以运行时间为\Theta (1)
解决:递推的分解成2分,所以运行时间为2 T ( n / 2 )
合并:合并运行时间为\Theta (n)

在最坏的情况T(n)的运行时间递归式:

T(n)=\begin{cases}
\Theta ( 1 )&n = 1 \\
2 T ( n / 2 ) + \Theta ( n )&n > 1
\end{cases}

这个递归式的运行时间为\Theta ( n \lg n),其中\lg n表示\log_2 n,为了理解为什么T(n) = \Theta ( n \lg n),重写一下上式:

T(n)=\begin{cases}
c&n = 1 \\
2 T ( n / 2 ) + cn&n > 1
\end{cases}

为了方便起见假设n是2的幂数,T(n)可以如下展开:
image.png

总共需要合并多少次呢?设需要合并x次,则有2^x = n,可计算出需要合并\log n次,每次合并的时间为cn,最下面一层常量计算需要时间cn,则总时间为cn\log n+cn,即\Theta (n\lg n)

posted @ 2019-02-02 20:06:48
评论加载中...

发表评论