Felomeng算法导论（第二版）学习笔记Chapter2（使用C#实现）
第二章 Getting Started
插入排序（Insertion Sort）C#实现:
int i,j,key;
for( j = 1; j < numbers.Length; j ++)
{
key = Convert.ToInt32(numbers[j]);
i = j - 1;
while (i >= 0 && Convert.ToInt32(numbers[i]) > key)
{
numbers[i + 1] = numbers[i];
--i;
}
numbers[i + 1] = key.ToString();
}
循环不变性（Loop invariant）三要素：
初始化：第一次循环前“有序性”是成立的；
保持：“有序性”，如果在一次循环前为真，那么在下次循环前仍然为真
结束：当循环结束时，“有序性”仍然成立，从而证明算法是正确的。
上面时间复杂度最坏情况为T(n)= θ(n*n)
平均情况（average-case）和最坏情况（worst-case）
一般采取最坏情况，原因：
1. 最坏情况的运行时间（running time）是程序可能的最长时间，不会与人们的预期冲突（只会小于预期）。
2. 最坏情况在很多情况下经常出现。
3. 平均情况往往和最坏情况差不多糟糕。
合并排序算法（merge sort），使用各个击破方法（divide-and-conquer approach）
主过程：
int[] A = new int[numbers.Length];
for (int i = 0; i < numbers.Length; i++)
{
A[i] = Convert.ToInt32(numbers[i]);
}
A = Merge(A, 0, A.Length - 1);
合并算法：
private int[] Merge(int[] A,int p, int q, int r)
{
int n1, n2;
n1 = q - p + 1;
n2 = r - q;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];
int i, j;
for (i = 0; i < n1; i++)
{
L[i] = A[i + p];
}
for (j = 0; j < n2; j++)
{
R[j] = A[j + q + 1];
}
L[n1] = int.MaxValue;
R[n2] = int.MaxValue;
i = 0;
j = 0;
for (int k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
return A;
}
private int[] Merge(int[] A,int p, int r)
{
int q = 0;
if (p < r)
{
q = (p + r) / 2;
A = Merge(A, p, q);
A = Merge(A, q + 1, r);
A = Merge(A, p, q, r);
}
return A;
}
合并排序算法分析：
可以看到，每一步消耗掉的时间都是cn。为什么呢？因为每步都有 方个运算，每个运算中消耗的时间是cn/(2^i )，这是因为每个运算中只有n/(2^i)个数进行排序，而排序需要的时间和排序的数字数线性相关。所以最后每步消耗时间c * n/(2^i)cn。
总共进行了lgn次运算，lgn表示底数为2的n的对数。假设总共进行了i+1（第一步是 ）步运算，最后一步n/ (2^i)=1，所以i = lgn。
于是根据乘法原理（高中数学），最后总共用时(lgn+1)*cn=cn*lgn +cn，因为cn远比cn*lgn增长率小，所以时间复杂度T(n)=θ(n*lgn)
为了说明这个算法的时间复杂度，书中给了限定条件：假设要解决的问题的数字数是2的乘方倍，其实不加这些条件限制，最后的结论也是一样的。（书里说后面章节会介绍清楚）