本文共 2395 字，大约阅读时间需要 7 分钟。
最近准备花时间把算法导论详细的看一遍，强化一下算法和数据结构的基础，将一些总结性的东西写到博客上去。
一.插入排序
算法思想：如果一个数组A，从A[1–n-1]都是有序的，然后我们将A[n]插入到A[1–n-1]的某个合适的位置上去那么就可以保证A[1–n]都是有序的。这就是插入排序的思想；具体实现的时候我们将数组的第一个元素看出有序，然后从第二个元素开始按照上面的步骤进行插入操作，直到插入最后一个元素，然后整个数组都是有序的了。
时间复杂度分析：代码中有两重for循环，很容易看出时间复杂度是n^2。
更多细节见代码及注释。
代码如下：
#include #include #include using namespace std;///插入排序:实现从大到小的排序void Insert_sort(int a[] ,int n){ for(int i=2;i<=n;i++) { int key=a[i]; ///当前待插入的元素 int j=i-1; ///a[1--i-1]已经有序，将a[i]插入其中 while(j>0&&a[j] 0&&a[j] >a[i]; Insert_sort1(a,n); cout<<"排序以后的数组："<
二.合并排序
算法思想：合并排序是一种典型的基于分治算法的排序方法。一般分治算法在每一层递归中都有以下几个步骤：
分解：将当前问题分解为几个之问题
求解：对每个之问题递归求解，如果问题规模足够小则直接求解
合并：将子问题的解合并成原问题的解。
对应到合并排序中如下：
分解：如果要对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。
代码如下：
#include #include #include using namespace std;#define INF 0x3f3f3f3f#define n 10///合并排序:实现从小到大的排序void Merge(int a[],int p,int q,int r){ ///合并函数 int n1=q-p+1; ///左区间长度 int n2=r-q; // ///复制左右两个区间的值到数组 int 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]; ///合并的基本思想是每次从left和right中选一个最小的放回原数组 ///的相应位置 ///下面对将两个区间合并回原数组的操作提供两种方法/* ///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++; else a[k]=right[j],j++; }*/ ///2.不设立监视哨通过left和right数组的下标控制循环，当left或right数组为空之后， ///再将另一个数组剩下的值合并到原数组的相应位置。 int i=1,j=1; int k=p; while(i<=n1&&j<=n2) { if(left[i] =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个整数: "< >a[i]; Merge_sort(a,1,5); cout<<"排序以后的数组："<
转载地址：http://ikrfb.baihongyu.com/