算法导论读书笔记（1）

放本Introduction To Algorithm镇楼

I.   插入算法

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适 当位置上，直到全部插入完为止。（From BaiDu）

说明：

具体实现是从第2个元素开始（因为1个元素是有序的），将第2个元素插入到前面的1个元素中，构成两个有序的序列，然后从第3个元素开始，循环操作，直到把第n元素插入到前面n-1个元素中，最终使得n个元素是有序的。

伪代码及解释

INSERTION-SORT(A)  （From Intro to Algorithm）

1      for j← 2 to length[A] 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

注意while的继续运行的条件是A[i] > key 即当前的key小于前面排序好的式子，然后用A[i+1] = A[i]来腾出一个位置，并且用i=i-1继续往前找。终止条件是当i已经找到最前面。

图解:（图片来自百度）

  实现算法:

//Insertion_sort.cpp

#include <iostream>

void Insertion_Sort(int * a,int n){
	int key = 0;
	for(int i =1;i < n;i++){
		key = a[i];
		int j = i-1;
		while(j>0 && a[j] > key){
			a[j+1] = a[j];
			j = j - 1;
		}
		a[j+1] = key;
	}
}

int main(){
	using namespace std;
	int a[10] = {0,9,8,7,6,5,4,3,2,1};
	Insertion_Sort(a,10);
	for(int i = 0;i<10;i++)
		cout<<a[i]<<" ";
	return 0;
}

复杂度分析：

算法分析是对一个算法所需的资源进行预测，资源是指希望测度的计算时间。插入排序过程的时间与输入相关的。插入排序的最好情况是输入数组开始时候就是满足要求的排好序的，时间代价为θ(n)，最坏情况下，输入数组是按逆序排序的，时间代价为  Θ（n²）.

II.Divide & Conquer (分治策略)

分治模式在每层递归时都有三个步骤:

分解（divide）：将原问题分解成一系列子问题。

解决（conquer）：递归地解答各子问题，若子问题足够小，则直接求解。

合并（combine）：将子问题的结果合并成原问题的解。

归并排序（merge sort）算法按照分治模式，操作如下：

分解：将n个元素分解成各含n/2个元素的子序列

解决：用合并排序法对两个序列递归地排序

合并：合并两个已排序的子序列以得到排序结果

所以MergeSort算法伪代码为:

MERGE-SORT (A, p, r)

1.     IF p < r                                                             //  Check for base case 2.         THEN q = FLOOR[(p + r)/2]                  //  Divide step 3.                 MERGE (A, p, q)                              //   Conquer step. 4.                 MERGE (A, q + 1, r)                        //   Conquer step. 5.                 MERGE (A, p, q, r)                         //    Conquer step.

图示:

线性归并的步骤：

设想有2沓卡片，每一沓都是排序好的并且面朝上的从最小开始，我们将归并这些卡片成为一沓排序好的卡片。

具体：

把一大摞牌分成2分，p->q->r

q-p+1为一摞               r-q为另一沓

• 选择两沓中最上一层最小的卡片
• 移走，作为一个新的沓放起来
• 将选择的卡片面朝下放入刚刚那个新的那一摞里
• 重复上述步骤，知道两个里面都没有卡片为止

当然，这之中需要两个哨兵牌，放在最底部，设定它们的点数为无穷大，那么就可以解决当一堆牌位空时候无法继续比较的事件了。每一步周花费线性时间。

伪代码:

MERGE (A, p, q, r )

1.      n_1 ← _q − p + 1 2.      n_2 ← _r − q 3.     // Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] 4.      FOR i ← 1 TO n_1** **5.            DO L[_i] ← A[p + i − 1] 6.      FOR j ← 1 TO n_2** **7.            DO R[_j] ← A[q + j ] 8.      L[n_1 + 1] ← ∞** **9.      R[_n_2 + 1] ← ∞** **10.    _i ← 1 11.    j ← 1 12.    FOR k ← p TO r 13.         DO IF L[i ] ≤ R[ j] 14.                THEN A[k] ← L[i] 15.                        i ← i + 1 16.                ELSE A[k] ← R[j] 17.                        j ← j + 1

实现代码:

#include <iostream>
#define FININT 10000

void Merge(int *A,int p,int q,int r){

    int n1 = q-p+1;
    int n2 = r-q;
    int *left = new int[n1+1];
    int *right = new int[n1+1];
    int i,j,k;
    //将子数组复制到临时辅助空间
    for(i=0;i<n1;++i)
        left[i] = A[p+i];
    for(j=0;j<n2;++j)
        right[j] = A[q+j+1];
    //添加哨兵
    left[n1] = FININT;
    right[n2] = FININT;
    //从第一个元素开始合并
    i = 0;
    j = 0;
    //开始合并
    for(k=p;k<=r;k++)
    {
        if(left[i] < right[j])
        {
            A[k] = left[i];
            i++;
        }
        else
        {
            A[k] = right[j];
            j++;
        }
    }
}

void MergeSort(int *A,int p,int r){
	if(p < r){
		int q = (p+r)/2;
		MergeSort(A,p,q);        //分解左边
		MergeSort(A,q+1,r);      //分解右边
		Merge(A,p,q,r);          //合并
	}
}

int main(){
	using namespace std;
	int a[10] = {0,9,8,7,6,5,4,3,2,1};
	MergeSort(a,0,9);
	for(int i = 0;i<10;i++)
		cout<<a[i]<<" ";
	return 0;
}

复杂度分析:

归并排序算法分析：

算法中含有对其自身的递归调用，其运行时间可以用一个递归方程（或递归式）来表示。归并排序算法分析采用递归树进行，递归树的层数为lgn+1，每一层的时间代价是cn，整棵树的代价是cn(lgn+1)=cnlgn+cn，忽略低阶和常量c，得到结果为θ(nlg n)。

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。

空间复杂度为 O(n)

比较操作的次数介于(nlogn) / 2和nlogn - n + 1。

赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)

归并排序比较占用内存，但却是一种效率高且稳定的算法。

III.递归树

下一期：算法导论读书笔记（2）递归树 主方法  随机算法  快速排序