算法导论学习之插入排序+合并排序
最近准备花时间把算法导论详细的看一遍,强化一下算法和数据结构的基础,将一些总结性的东西写到博客上去。
一.插入排序
算法思想:如果一个数组A,从A[1–n-1]都是有序的,然后我们将A[n]插入到A[1–n-1]的某个合适的位置上去那么就可以保证A[1–n]都是有序的。这就是插入排序的思想;具体实现的时候我们将数组的第一个元素看出有序,然后从第二个元素开始按照上面的步骤进行插入操作,直到插入最后一个元素,然后整个数组都是有序的了。
时间复杂度分析:代码中有两重for循环,很容易看出时间复杂度是n^2。
更多细节见代码及注释。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
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]<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。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
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]<right[j])
a[k++]=left[i++];
else
a[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;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。