数据结构排序

直接插入排序：算法流程

对待排序序列中的每个元素，按大小插入到答案序列中

答案序列数组

开始时： [ ] [ 3,5,4,6,7]

第一步插入3，答案序列是空，直接放入

[3] [5,4,6,7]

第二步插入5，应该插入在3的后面

[3,5] [4,6,7]

第三步插入4，应该插入在3后面，5的前面

[3,4,5] [6,7]

对于a[i],应该插入到答案数组的第一个大于等于a[i]的位置，插入完成后即排序完成

时间复杂度：

考虑两个极端情况：

1.待排序数组是非递减的，也就是每次插入只需插入到最后一个位置，有n个数插入，插入a[i]时顺序查找插入位置的遍历长度i-1,时间复杂度是每个元素查找长度之和

2.待排序数组是非递增的，也就是每次插入需要插入到答案数组的第一个位置，此时查找长度为0，但需要将答案数组向后移动一个位置，对于插入a[i]时，移动次数应该是之前已经插入到序列的所有数，也就是需要移动i-1个元素，那么时间复杂度同上是

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[100005],ans[100005];

int main()
{
 	cin>>n;
 	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 	ans[1]=a[1];
 	for(int i=2;i<=n;i++)
 	{
 		//在插入i时，ans数组元素数应该是i-1
 		int pos;
 		for(pos=1;pos<=i-1&&ans[pos]=pos+1;j--) ans[j]=ans[j-1];
		}
		ans[pos]=a[i];
		for(int j=1;j<=i;j++) printf("%d ",ans[j]);
		for(int j=i+1;j<=n;j++) printf("%d ",a[j]);
		cout< 
二分查找插入排序 
对直接插入排序有一个地方可以优化，那就是在答案数组中寻找插入位置，因为答案数组一定是有序的，所以可以二分查找第一个大于等于a[i]的位置 
二分函数：lower_bound(l,r,k)，在指针l与r之间的区域[l,r)（注意是左闭右开）寻找第一个大于等于k的位置，返回指针，如果查找失败，返回r指针。这个函数定义在头文件#include内 
那么在长n的a序列中查找大于等于k的第一个位置的下标就是： 
lower_bound(a,a+n,k)-a 
时间复杂度： 
同样考虑两种极端情况： 
1.待排序数组是非递减的，那么不需要迁移，需要查找插入位置，二分查找时间复杂度,所以总时间复杂度是 
2.待排序数组是非递增的，那么不需要查找位置，需要迁移，时间复杂度同上是 
所以总时间复杂度大约是到 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[100005],ans[100005];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	ans[1]=a[1];//第一个数直接插入到空答案序列即可
	for(int i=2;i<=n;i++)
	{
		//在插入i时，ans数组元素数应该是i-1
		int pos=lower_bound(ans+1,ans+1+i-1,a[i])-ans;
		if(pos!=i)//如果找到的位置不是右指针所指的下标，那么需要迁移找到的位置之后的所有元素，即把[pos,i-1]区间后移一位
		{
			for(int j=i;j>=pos+1;j--) ans[j]=ans[j-1];//迁移
		}
		ans[pos]=a[i];
		for(int j=1;j<=i;j++) printf("%d ",ans[j]);
		for(int j=i+1;j<=n;j++) printf("%d ",a[j]);
		cout< 
希尔排序： 
算法流程： 
初始化一个增量d=n/2,在数组中查找所有距离为d的有序对，如果不满足排序规则就交换，需要注意的是，在交换完i与i+d位置后，因为i位置更新了，所以需要重新考虑i-d这个位置(如果存在)，这个步骤是建议递归处理的 
时间复杂度： 
大约是，具体为到 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[100005];

void swap_(int i,int j)
{
	swap(a[i],a[j]);//swap(a,b)函数，定义在#include,交换a,b两数的值
	if(2*i-j>=1&&a[2*i-j]>a[i]) swap_(2*i-j,i);//完成这次交换后，看一下i-d是否存在，并且不满足前小后大，是的话就递归交换
	//因为调用这个函数的时候是swap_(i,i+d)，所以(函数内)j-i==(主函数)d，所以i-d=i-(j-i)=2*i-j
}

int main()
{
 	cin>>n;
 	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 	for(int d=n>>1;d;d>>=1)//初始化d为n/2,也就是n右移一位，每次循环都是d=d/2，也就是d>>=1
 	{
 		for(int i=1;i<=n-d;i++)//查找所有距离为d的有序对
 		{
 			if(a[i]>a[i+d]) swap_(i,i+d);//如果不满足排序规则，即a[i]<=a[j](i 
冒泡排序 
算法流程： 
反复遍历数组，遇到不符合排序规则的相邻有序对就交换 
那么到底需要遍历多少遍呢？ 
考虑一个极端(最坏)情况，有一个序列中最小的数出现在了序列最右边，那么从最右到最左需要交换n-1次，由于每一次遍历中右边的数最多往左交换一个，因此我们只要遍历n-1次，就一定能完全排序数组 
那我们是不是一定要遍历n-1次呢？答案是不需要的，因为只要在某一次遍历中没有发生交换，数组就一定排好序了，n-1次只是能保证一定排好序的最小次数而已。 
时间复杂度： 
在一定能排序的前提下讨论：遍历n-1次，那么操作次数就是 
如果序列已经排好序，那么只需遍历一次就可以结束，操作数=   
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[100005];

bool sort()
{
	bool flag=true;//默认值是true,就是假设没有数要交换,如果发生了交换,就成为false
	for(int i=1;ia[i+1])
		{
			swap(a[i],a[i+1]);
			flag=0;
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	cout<>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n-1;i++) if(sort()) return 0;
 	return 0;
}
 
快速排序： 
算法流程： 
在待排序的数组中选取一个标准值pivot,将小于pivot的所有值放在pivot的左边，大于pivot的值放在右边，假设pivot最后在k位置，我们只需要同样的方法排序k的左右两边数组就可以了 
在一般的实现里，一般选用待排序数组的最左边的值作为pivot，在下面的实现也是如此 
时间复杂度： 
考虑两个pivot最后放置位置的极端情况： 
1.如果pivot出现在序列两端，那么每次都只递归排序剩下的元素，每次排序需要序列长度的操作数，所以总操作数为 
由于我们选择的时排序前的最左边数，最后出现在序列两端意味着pivot是最值，所以，当选取到的pivot是最值时，得到最差时间复杂度，经典例子是对有序序列快速排序 
2.如果pivot出现在正中间，那么意味着每次二分序列，并且每次二分完指针移动的距离都是序列长度，所以时间复杂度 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[100005];

void q_sort(int l,int r)
{
	int lastl=l,lastr=r,pivot=a[l];//lastl,lastr用来保存最初的l,r,有什么用到递归的时候就会明白。pivot就是标准值
	while(l=pivot&&llastl) q_sort(lastl,l-1);//如果pivot左边的区间长度大于1，那么就递归排序左边的，下面的同理
	if(lastr>r+1) q_sort(r+1,lastr);//lastl,lastr的作用就是保存开始的边界，以便递归
}

int main()
{
 	cin>>n;
 	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 	q_sort(1,n);
 	return 0;
}
 
选择排序： 
算法流程： 
查找第i小的数，放在第i位 
由于算法是这样，那么第i小的数只会出现在[i,n] (这句话是对在排序i位置的时候而言的，因为比他小的数一定都在之前被选择走了） 
oj好像不用打印最后一次的结果，所以在打印前记得判断一下 
时间复杂度： 
排序i位置时，需要遍历[i,n]查找最小值，所以操作次数大约为，时间复杂度为 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n,a[100005];

int main()
{
 	cin>>n;
 	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
 	for(int i=1;i<=n;i++)//查找第i位放的数，也就是第i小的数
 	{
 		int minv=0x3fffffff,minp;//用minv记录最小值,minp记录最小值的位置
 		//需要一对变量的原因是我们最后关心的不仅是值，还有位置
 		for(int j=i;j<=n;j++)//遍历区间[i,n]找最小值
 		{
 			if(a[j]

数据结构排序

C/C++/C#相关栏目本月热门文章