1. 插入排序

我們的第一個(gè)算法，求解排序問(wèn)題。

輸入：

n個(gè)數(shù)的一個(gè)序列<>

輸出:

輸入序列的一個(gè)排列 <>,滿足

我們也將希望排序的數(shù)稱為關(guān)鍵詞

我們首先介紹插入排序，對(duì)于少量元素這是一個(gè)有效的算法。工作方式類似于撲克牌的排序，從桌子上拿走一張牌，并插入手牌中正確的位置，使得手牌總是排序好的。從桌子上拿的牌也是牌堆中的第一張牌。

python算法描述

def insertionSort(A):
    n = len(A)
    for j in range(1,n):
        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

循環(huán)不變式與算法的正確性

該圖表面對(duì)該算法的工作流程。下標(biāo)j指出準(zhǔn)備要插入手中的當(dāng)前牌，而的子數(shù)組構(gòu)成了已排好序的牌，剩余的數(shù)組對(duì)應(yīng)于仍在桌子上的牌堆。我們把所具有的性質(zhì)稱為循環(huán)不變式。即每次循環(huán)都有這種性質(zhì)。

運(yùn)行圖解

循環(huán)不變式主要用于幫助我們理解算法的正確性。
關(guān)于循環(huán)不變式，我們必須證明三條性質(zhì)：

1. 初始化：循環(huán)的第一次迭代之前，它為真
2. 保持 ：如果循環(huán)的某次迭代之前它為真，那么下次迭代之前仍為真
3. 終止 ： 在循環(huán)終止時(shí)，不變式為我們提供一個(gè)有用的性質(zhì)，該性質(zhì)有助于證明算法是正確的。

一二兩條類似于數(shù)學(xué)歸納法，即相當(dāng)于基本情況和歸納步，若證明成功，即循環(huán)的每次迭代前循環(huán)不變式都為真。

第三條意味著我們將用循環(huán)不變式來(lái)證明正確性，通常，我們和導(dǎo)致循環(huán)終止的條件一起使用循環(huán)不變式。

下面我們來(lái)看看，對(duì)于插入排序證明這些性質(zhì)成立。

1. 初始化

在第一循環(huán)()之前，循環(huán)不變式成立，因?yàn)樽訑?shù)組僅有單個(gè)元素構(gòu)成。

2. 保持

我們給個(gè)非形式化的證明：
for循環(huán)中將等向右移動(dòng)一個(gè)位置，直到找到適當(dāng)?shù)奈恢?。而后?img class="math-inline" src="https://math.jianshu.com/math?formula=A%5Bj%5D" alt="A[j]" mathimg="1">插入該位置，這時(shí)子元素仍由原來(lái)的元素構(gòu)成，但已有序。以此，每次對(duì)j增加構(gòu)成的新子數(shù)組均有序。

3. 終止

導(dǎo)致for循環(huán)終止的條件是,因此將j不斷加一時(shí)，必有j=n+1,在循環(huán)不變式表述中將j用n+1代替，那么子數(shù)組由的元素組成，但已排序，因此算法正確。

2.分析算法

分析算法的意味著預(yù)測(cè)算法需要的資源，我們最想度量的是時(shí)間。
為了分析算法，我們需要有一個(gè)實(shí)現(xiàn)技術(shù)的模型，包括描述所有資源及其代價(jià)的模型。我們使用一中假定的通用單處理器計(jì)算模型——隨機(jī)訪問(wèn)機(jī)(RAM)。在RAM中，指令一條接一條執(zhí)行，沒(méi)有并發(fā)操作。

我們要注意不能濫用RAM模型，RAM模型只能完成基本操作，基本觀點(diǎn)是，計(jì)算機(jī)如何設(shè)計(jì)，RAM就如何設(shè)計(jì)。

RAM中的數(shù)據(jù)類型有整型和浮點(diǎn)型，我們大部分情況下不關(guān)注精度，除非某些特殊應(yīng)用。

在真實(shí)的計(jì)算機(jī)中還包含一些特殊指令，我們盡量避免這些指令。例如計(jì)算，當(dāng)k較小時(shí)，我們當(dāng)作常量時(shí)間計(jì)算。

我們?cè)赗AM模型中并不試圖對(duì)內(nèi)存層次進(jìn)行建模。有些情況下會(huì)考慮內(nèi)存層次的影響，但是大部分情況下不會(huì)。

插入排序算法的分析

插入排序算法需要的時(shí)間依賴于輸入和被排序的程度。一般來(lái)說(shuō)，算法的時(shí)間與輸入的規(guī)模同步增長(zhǎng)，所以通常把一個(gè)程序的運(yùn)行時(shí)間描述成其輸入規(guī)模的函數(shù)。

輸入規(guī)模的概念依賴于研究的問(wèn)題，如排序問(wèn)題中，是輸入的項(xiàng)數(shù)n，整數(shù)相乘時(shí)，是整數(shù)的位數(shù)。對(duì)于圖，則使用頂點(diǎn)數(shù)和邊數(shù)來(lái)描述。

一個(gè)算法在特定輸入上的運(yùn)行時(shí)間是指執(zhí)行指令的操作次數(shù)。我們可以假定

如圖所示，我們首先看看插入排序每條語(yǔ)句執(zhí)行的次數(shù)和時(shí)間。注：while/for 等循環(huán)退出時(shí)會(huì)多執(zhí)行一次

插入排序.jpg

該算法的運(yùn)行時(shí)間是每條語(yǔ)句的運(yùn)行時(shí)間之和

我們對(duì)運(yùn)行時(shí)間求和，得到

運(yùn)行時(shí)間求和.jpg

當(dāng)是最好情況下，即數(shù)組已經(jīng)排好序時(shí)，可以觀察到第6行，第七行不會(huì)被執(zhí)行，因此求和公式可更改為

最好情況求和.jpg

當(dāng)輸入已經(jīng)反向排序時(shí)，將導(dǎo)致最壞情況。我們必須將和中的每個(gè)元素相比較，因此得到求和公式

最壞情況.jpg

最壞情況與平均情況分析

在本書的其他部分，我們往往集中于最壞情況運(yùn)行時(shí)間分析，原因有三

1. 最壞情況運(yùn)行時(shí)間給出了上界，知道了這個(gè)上界就能確保算法絕不需要更長(zhǎng)的時(shí)間。
2. 對(duì)某些算法，最壞情況經(jīng)常出現(xiàn)。
3. 平均情況往往和最壞情況大致一樣差

在某些特定情況下，我們會(huì)對(duì)算法的平均情況感興趣，我們將看到概率分析技術(shù)被用于各種算法。平均情況分析范圍有限，對(duì)于特定的問(wèn)題，難以辨別什么才是平均情況。我們假設(shè)各種輸入具有相同的可能性，實(shí)際上該假設(shè)可能并不成立。

增長(zhǎng)量級(jí)

我們真正感興趣的是運(yùn)行時(shí)間的增長(zhǎng)率或增長(zhǎng)量級(jí)，所以我們只考慮公式中最重要的項(xiàng)。

3. 設(shè)計(jì)算法

我們可以選擇使用的算法設(shè)計(jì)技術(shù)有很多，插入排序使用了增量方法，本節(jié)我們將討論分治法，分治法的優(yōu)點(diǎn)之一是，通過(guò)一些特殊技術(shù)往往很容易確定其運(yùn)行時(shí)間。

1. 分治

分治法思想：將原問(wèn)題分解為幾個(gè)規(guī)模較小但類似原問(wèn)題的子問(wèn)題，遞歸地求解子問(wèn)題，再合并這些子問(wèn)題的解來(lái)得到原問(wèn)題的解。

分治模式在每層遞歸時(shí)通常都有三個(gè)步驟

• 分解原問(wèn)題為若干子問(wèn)題，子問(wèn)題為原問(wèn)題的規(guī)模較小的實(shí)例
• 解決這些子問(wèn)題，遞歸求解各子問(wèn)題
• 合并這些子問(wèn)題得到原問(wèn)題的解。

歸并排序算法完全遵循該模式，將n個(gè)元素分解為n/2個(gè)元素，使用歸并排序遞歸解決子數(shù)列，合并已排序的子數(shù)列得到答案。

歸并排序的關(guān)鍵步驟是合并已排序好的子數(shù)列，如兩個(gè)已排序好的數(shù)列，合并完成這兩個(gè)子數(shù)組得到新數(shù)組

合并操作需要的時(shí)間，我們不斷比較兩個(gè)子數(shù)組，選取較小的元素放入新數(shù)組
中完成合并。

使用python代碼描述合并過(guò)程：

inf = float("inf")
def merge(A,p,q,r):
    L = A[p:q+1]#左邊的數(shù)組暫存
    R = A[q+1:r+1]#右邊的數(shù)組暫存
    L.append(inf)#插入哨兵
    R.append(inf)
    i = 0
    j = 0
    for k in range(p,r+1):#將數(shù)組合并到A中
        if L[i]<R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1

循環(huán)不變式為：

在for循環(huán)的每次迭代時(shí)，子數(shù)組按從小到大的順序包含和中的個(gè)最小元素，進(jìn)而，和是各自所在數(shù)組中未被復(fù)制回?cái)?shù)組A的最小元素。
注:數(shù)組下標(biāo)從1開(kāi)始，n1,n2分別為L(zhǎng)和R的長(zhǎng)度

接下來(lái)我們證明這個(gè)循環(huán)不變式:
初始化:

在循環(huán)的第一次迭代之前，有,因此為空，包含個(gè)最小元素，此時(shí)，和是各自所在數(shù)組中未被復(fù)制回?cái)?shù)組A的最小元素

保持：

為了理解每次迭代都維持循環(huán)不變式，我們先假設(shè)，此時(shí)是未被復(fù)制回?cái)?shù)組A的最小元素。因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=A%5Bp..k-1%5D" alt="A[p..k-1]" mathimg="1">包含k-p個(gè)最小元素，所以將復(fù)制到A[k]之后，子數(shù)組將包含個(gè)最小元素，更新k值和i值后，即維持了原來(lái)的不等式成立。

終止:

終止時(shí),根據(jù)循環(huán)不變式就是且按照從小大大順序包含L和R中的k-p個(gè)最小元素。
完整的歸并排序python代碼:

inf = float("inf")
def merge(A,p,q,r):
    L = A[p:q+1]
    R = A[q+1:r+1]
    L.append(inf)
    R.append(inf)
    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 mergeSort(A,lo,hi):
    if lo==hi:
        return
    mid = (lo+hi)//2
    mergeSort(A,lo,mid)
    mergeSort(A,mid+1,hi)
    merge(A,lo,mid,hi)

歸并排序圖示：

歸并.jpg

2. 分析分治算法

我們可以用遞歸方程或遞歸式來(lái)描述遞歸分治算法的運(yùn)行時(shí)間。
分治算法運(yùn)行時(shí)間的遞歸式來(lái)自于基本模式的三個(gè)步驟，假設(shè)是規(guī)模為n的一個(gè)問(wèn)題的運(yùn)行時(shí)間。
當(dāng)問(wèn)題規(guī)模足夠小時(shí)，則將運(yùn)行時(shí)間寫作。假設(shè)吧原問(wèn)題分解成個(gè)子問(wèn)題，每個(gè)子問(wèn)題的規(guī)模是原問(wèn)題的，求解個(gè)子問(wèn)題就需要的時(shí)間。
如果分解成子問(wèn)題需要時(shí)間，合并時(shí)間為，那么得到遞歸式

遞歸式.jpg

歸并排序算法的分析

為了簡(jiǎn)化分析，假定原問(wèn)題的規(guī)模是2的n次冪
分解：分解為規(guī)模為的子問(wèn)題，需要常量的時(shí)間，
解決 ：遞歸地求解兩個(gè)規(guī)模為的子問(wèn)題，將貢獻(xiàn)的運(yùn)行時(shí)間。
合并：合并需要的時(shí)間。
因此得到遞歸式

歸并遞歸式.jpg

通過(guò)之后主定理的學(xué)習(xí)，我們會(huì)了解到該算法的時(shí)間復(fù)雜度為