算法导论（一）--排序

插入排序归并排序

插入排序

算法： 插入排序类似于我们打扑克时，每抓一张牌，就按顺序插入到手中已有的有序的牌中。 代码如下：

//对a[0]~a[n-1]排序 void insert_sort(int *a,int n) { for(int i=1;i<n;i++) { int tmp=a[i]; int j=i-1; while(tmp<a[j] && j>=0) { a[j+1]=a[j]; j--; } a[j+1]=tmp; } }

对于数组a，tmp左边的这段始终是已排好序的。

举例： a={8,2,4,9,3,6}，n=6，经历n-1个循环之后，a依次变成了： 2,8,4,9,3,6 2,4,8,9,3,6 2,4,8,9,3,6 2,3,4,8,9,6 2,3,4,6,8,9

分析： 现在来分析一下算法的运行时间： 如果数组a本身已经是排好序的了，那么插入排序要做的工作就非常少了，因为它们已经各就各位了。最坏的是逆序的情形，算法必须做大量的工作。

渐近分析的基本思路：忽略那些依赖于机器的常量以及不是去检查实际的运行时间，而是关注运行时间的增长。

渐近符号： Θ：对某个公式，弃去它的低阶项，并忽略前面的常数因子（因为n->∞时，低阶项和常数因子都不会影响Θ(n³) > Θ(n²)的结果）

用T(n)表示输入规模为n时的最长运行时间，$T(n)={\sum }_{i=1}^{n-1}\Theta (i)=\Theta (n^2)$ （为什么呢？外循环中i从1～n-1，我们把每次循环的工作汇总；内循环在j每次取新值时只做固定量的工作，从0～i-1，所以是Θ(i)的量的工作；然后相当于对连续整数求和，说到底是1+2+3+…+n，这是一种算数级数。）

归并排序

算法： 归并排序的思想就是，如果能把整个输入拆成已经有序（比如升序）的两个序列，把他们归并一下就可以得到一个有序的序列。怎么保证分成的两个序列是有序的呢？通过不断地划分这个序列直到最小粒度， 也就是只有一个数的时候，它一定是有序的， 然后一层一层向上归并，得到最终的有序序列。 归并的过程就不用多说了，就是用两个指针指向两个序列的开始，不断地选两个中较小的，选中的就指针往后移一个，直到某个序列遍历完。 粘上代码:

void merge(int* arr,int p,int q,int r) { int n1 = q - p +1; int n2 = r - q; int L[n1+1], R[n2+1]; int i, j, k; for(i = 0; i < n1; i++) L[i] = arr[p+i]; for(j = 0; j < n2; j++) R[j] = arr[q+j+1]; L[n1] = R[n2] = (unsigned)(~0) >> 1; i = j =0; for(k = 0; k < r - p +1; k++) { if(L[i] <= R[j]) { arr[p+k] = L[i]; i++; } else { arr[p+k] = R[j]; j++; } } } void merge_sort(int *arr,int p,int r) { if(r > p) { int q = (p + r) / 2; merge_sort(arr, p, q); merge_sort(arr, q + 1, r); merge(arr, p, q, r); } }

分析： 我们分析一下整体的复杂度。首先归并的过程的复杂度是Θ(n)。如果序列只有一个元素，复杂度是Θ(1)，否则后面两个递归是2T(n/2)。也就是说： $$T(n)=\{\begin{array}{ll}\Theta (1)& n=1\\ 2T(n/2)+\Theta (n)& n>1\end{array}$$ Θ(1) 比Θ(n) 低阶，对递归没有影响，可以直接舍去。我们可以用构造递归树法求这个复杂度，为Θ(nlogn)。 考虑渐进的情况下，要比插入排序好。