最近准备花时间把算法导论详细的看一遍，强化一下算法和数据结构的基础，将一些总结性的东西写到博客上去。
一.插入排序 算法思想：如果一个数组A，从A[1–n-1]都是有序的，然后我们将A[n]插入到A[1–n-1]的某个合适的位置上去那么就可以保证A[1–n]都是有序的。这就是插入排序的思想；具体实现的时候我们将数组的第一个元素看出有序，然后从第二个元素开始按照上面的步骤进行插入操作，，直到插入最后一个元素，然后整个数组都是有序的了。
时间复杂度分析：代码中有两重for循环，很容易看出时间复杂度是n^2。 更多细节见代码及注释。 代码如下：
;///插入排序:实现从大到小的排序void Insert_sort(int a[] ,int n){for(int i=2;i<=n;i++){(j>0&&a[j]<key) ///寻找插入位置，并同时实现元素后移{a[j+1]=a[j];j–;}a[j+1]=key; ///插入元素}}///插入排序递归实现 void Insert(int a[],int n) {int j=n-1;int key=a[n];while(j>0&&a[j]<key){a[j+1]=a[j];j–;}a[j+1]=key; }void Insert_sort1(int a[],int n){if(n==1) ///只有一个元素时默认为有序的return ;Insert_sort1(a,n-1); ///对1–n-1递归进行插入排序Insert(a,n); ///1–n-1有序之后,讲a[n]插入}int main(){int n=5,a[10];cout<<“请输入5个整数: “<<endl;for(int i=1;i<=n;i++)cin>>a[i];Insert_sort1(a,n);cout<<“排序以后的数组：”<<endl;for(int i=1;i<=n;i++)cout<<a[i]<<” “;cout<<endl; return 0;}
二.合并排序 算法思想：合并排序是一种典型的基于分治算法的排序方法。一般分治算法在每一层递归中都有以下几个步骤： 分解：将当前问题分解为几个之问题 求解：对每个之问题递归求解，如果问题规模足够小则直接求解 合并：将子问题的解合并成原问题的解。 对应到合并排序中如下： 分解：如果要对A[p,r]进行排序，则分解为A[p,(p+r)/2]和A[(p+r)/2+1,r]进行排序。 求解：对A[p,(p+r)/2]和A[(p+r)/2+1,r]继续上面的递归求解，如果p==r(只有一个元素)则直接返回。 合并： 合并有序的A[p,(p+r)/2]和有序的A[(p+r)/2+1,r]得到有序的A[p,r]。 从中可以看出合并是其中的关键步骤，合并函数Merge实现将两个有序的序列合并成一个有序的序列。更多的细节见代码。
时间复杂度分析：归并排序是一个递归过程，采用递归式分析可得时间复杂度为nlgn。
代码如下：
namespace std;合并排序:实现从小到大的排序void Merge(int a[],int p,int q,int r){ n2=r-q; left[n],right[n];for(int i=p;i<=q;i++)left[i-p+1]=a[i];for(int i=q+1;i<=r;i++)right[i-q]=a[i];下面对将两个区间合并回原数组的操作提供两种方法/*///1.在left和right数组的最后一位加一个值为无穷大的监视哨///并通过控制for循环的次数，使得监视哨不会被放回原数组left[n1+1]=INF;right[n2+1]=INF;int i=1,j=1;for(int k=p;k<=r;k++){if(left[i]<=right[j])a[k]=left[i],i++;elsea[k]=right[j],j++;}*/i=1,j=1;int k=p;while(i<=n1&&j<=n2){if(left[i]<right[j])a[k++]=left[i++];elsea[k++]=right[j++];}///收尾处理for(int d=i;d<=n1;d++)a[k++]=left[d];for(int d=j;d<=n2;d++)a[k++]=right[d];}void Merge_sort(int a[],int p,int r){if(p>=r) ///p==r时说明只剩一个元素，默认为有序return ;Merge_sort(a,p,(p+r)/2); ///对数组的左半部分进行合并排序Merge_sort(a,(p+r)/2+1,r); ///对数组的右半部分进行合并排序Merge(a,p,(p+r)/2,r); ///数组的左右两部分都是有序的，则合并这两个部分。}int main(){int a[n];cout<<“请输入5个整数: “<<endl;for(int i=1;i<=5;i++)cin>>a[i];Merge_sort(a,1,5);cout<<“排序以后的数组：”<<endl;for(int i=1;i<=5;i++)cout<<a[i]<<” “;cout<<endl; return 0;}
远离城市的喧嚣，寻找一份宁静，
