? 本章介紹了一個貫穿本書的框架，后續(xù)的算法設(shè)計都是在這個框架中進行的。

? 本章通過插入排序和歸并排序兩種常見的算法來說明算法的過程及算法分析，在分析插入排序算法時，書中是用了循環(huán)不變式證明了算法的正確性，在介紹歸并排序時算法過程中引入了分治法的思想。

2.1 插入排序

? 這是我們的第一個算法（插入排序）用于求解第一章中引入的排序問題：

? 輸入：n個數(shù)的一個序列<a1, a2, ..., an>。

? 輸出：輸入序列的一個排列<a1', a2', ..., an' >，滿足a1‘<=a2'<=...<=an'

? 插入排序的基本操作是將一個記錄插入到以排序好的有序表中，從而得到一個新的記錄數(shù)增1的有序表。一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1..i-1]中插入一個A[i]后，編程含有i個記錄的有序子序列r[1..i]，直到把第n個元素插入到n-1個元素中，最終使得n個元素有序。插入排序的為代碼如下：

INSERTION_SORT(A) 1 for j=2 to A.length 2 key = A[j] 3 //Insert A[j] into the sorted sequence A[1.. j-1] 4 i = j - 1 5 while(i>0 and A[i]>key) 6 A[i+1] = A[i] 7 i = i - 1 8 A[i+1] = key</span> ? 循環(huán)不變式主要用來幫助我們理解算法的正確性。關(guān)于循環(huán)不變式，我們必須證明三條性質(zhì)：

? 初始化：循環(huán)的第一次迭代之前，它為真。

? 保持：如果循環(huán)的某次迭代之前他為真，那么下次迭代之前它仍未真。

? 終止：在循環(huán)終止時，不變式提供了一個有用的性質(zhì)，該性質(zhì)有助于證明算法是正確的。

? 插入排序的證明過程：

? 初始化：當j=2時，子數(shù)組A[1.. j-1]僅由單個元素A[1]組成，實際上就是A[1]原來的元素。而且該子數(shù)組是排序好的，這表明第一次循環(huán)迭代之前循環(huán)不變式成立。

? 保持：for循環(huán)的4-7行將A[j-1], A[j-2], A[j-3]等右移一個位置，直到找到A[j]的適當位置，第8行將A[j]插入該位置。這是子數(shù)組A[1.. j]由原來在A[1.. j]中的元素組成，但已經(jīng)按順序排列。那么對for循環(huán)的下一次迭代增加j將保持循環(huán)不變式。

? 終止：導致for循環(huán)終止的條件式j(luò)>A.length = n。在循環(huán)不變式中將j用n+1代替，我們有：子數(shù)組A[1.. n]由原來在A[1.. n]中的元素組成，但已經(jīng)按順序排序。因此算法正確。采用c語言編寫的插入排序的完整程序如下：

void insertionSort(int *arr, int length){//判斷參數(shù)是否合法if(arr == NULL || 0==length){printf("Check datas or length.\n");exit(1);}//數(shù)組下標是從0開始的，從第二個元素（對應下標1）開始向前插入for(int j=1; j<length; j++){int key = arr[j]; //記錄當前要插入的元素int i = j - 1; //前面已經(jīng)有序的元素//尋找待插入元素的位置，從小到到排序，如果是從大到小改為arr[i]<keywhile(i>=0 && arr[i]>key){arr[i+1] = arr[i];i--; //向前移動}arr[i+1] = key;} }</span>

插入排序的算法分析

? 過程INSERTION-SORT需要的時間依賴于輸入：排序1000個數(shù)排序三個數(shù)需要更長的時間。此外，依據(jù)它們已經(jīng)被排序的程度，INSERTION-SORT可能需要不同的數(shù)量時間來排序一個具有相同規(guī)模的輸入序列。插入排序算法中，若輸入的數(shù)組已經(jīng)排好序，則出現(xiàn)最佳情況。這時對每個j=2, 3, ..., n，程序中的第5行，當i = j - 1時，有A[i]<=key。此時算法的復雜度為O(n)。若輸入的數(shù)組已反向排序，即按遞減序列，則導致最壞情況。此時INSERTION-SORT算法的時間復雜度為O(n^2)。

2.2 歸并排序

?分治法的思想是：將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些問題，然后在合并這些子問題的解來建立原問題的解。

歸并排序算法完全遵循分治策略。直觀上操作如下：

?分解：把具有n個元素的序列分解成具有n/2個元素的兩個子序列。

?解決：使用歸并排序遞歸地排序兩個子序列。

?合并：合并兩個已排序的子序列則可得到n個元素的排序序列。

?歸并排序算法的關(guān)鍵操作是“合并”步驟中兩個已排序的序列。書中通過調(diào)用的一個輔助過程MERGE(A, p, q, r)來完成合并，MERGE算法的偽代碼如下(算法在實現(xiàn)的過程中是用來哨兵)：

MERGE(A, p, q, r) 1 n1 = q - p + 1 2 n2 = r - q 3 let L[1.. n1+1] and R[1.. n2+1] 4 for i=1 to n1 5 L[i] = A[p + i -1] 6 for j=1 to n2 7 R[j] = A[q + j] 8 L[n1+1] = MAX 9 R[n2+1] = MAX 10 i = 1 11 j=1 12 for k=p to r 13 if L[i]<=R[j] 14 A[k] = L[i] 15 i = i + 1 16 else 17 A[k] = R[j] 18 j = j + 1

算法采用c++ 語言完整程序為：

void Merge(int *arr, int p, int q, int r) {int n1 = q - p + 1; //第一個有序子數(shù)組元素個數(shù)int n2 = r - q; //第二個有序子數(shù)組元素個數(shù)int *Left = (int *)malloc(sizeof(int)*(n1 + 1));int *Right = (int *)malloc(sizeof(int)*(n2 + 1));//將子數(shù)組復制到臨時輔助空間for(int i=0; i<n1; i++){Left[i] = arr[p+i];}for(int j=0; j<n2; j++){Right[j] = arr[q+j+1];}//添加哨兵Left[n1] = INT_MAX;Right[n2] = INT_MAX;//從第一個元素開始合并int i = 0;int j = 0;for(int k=p; k<=r; k++){if(Left[i] <= Right[j]){arr[k] = Left[i];++i;}else{arr[k] = Right[j];++j;}}free(Left);free(Right); }

現(xiàn)在我們可以把過程MERGE作為歸并排序算法中的一個子程序來用。MERGE-SORT(A, p, r)是實現(xiàn)歸并排序的算法：

MERGE-SORT(A, p, r) 1 if p < r 2 q = (p + r) / 2 //向下取整 3 MERGE-SORT(A, p, q) 4 MERGE-SORT(A, q + 1, r) 5 MERGE(A, p, q, r)

采用C++完整程序為：

void MergeSort(int *arr, int p, int r) {if(p < r){int q = (p + r) / 2;MergeSort(arr, p , q);MergeSort(arr, q + 1, r);Merge(arr, p, q, r);}}

merge過程的運行時間是θ(n)，現(xiàn)將merge過程作為歸并排序中的一個子程序使用，merge_sort(A,p,r),對數(shù)組A[p...r]進行排序，實例分析如下圖所示：

歸并排序的算法分析

歸并排序算法包含對其自身的遞歸調(diào)用，我們可以用遞歸方程或遞歸式來描述其運行時間，歸并排序算法的最壞情況運行時間T(n)的遞歸式為：若n>1，T(n) = 2T(n / 2) +?Θ(n);若n=1，T(n)=?Θ(1)。該遞歸式可以由主定理求得T(n)的復雜度為Θ(nlgn)。

總結(jié)

以上是生活随笔為你收集整理的算法导论学习笔记 第2章 算法基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。