题外话:因为这个类似题解,所以我有点不敢发,犹豫不决,但为了让大家知道此题的更简单的快速排序解法,我还是把它发了

1.把第一个数和区间内随机一个数交换

2.区间小于等于10时改用插入排序

前两个大家应该都知道,我现在说第三个

题解中快速排序的方法要拿满分,思路太复杂了,我这里有一种更好理解的方法.

如果只有前两个优化,那么在大部分数据相等的情况下,它们就不能发挥作用,时间复杂度照样会退化成O(n²)

所以,可以先在输入数据时进行去重(用map,时间复杂度为线性对数),输出时按照映射的结果决定输出的次数

而且,这个优化还附带有稳定化的功能!

具体实现方法:

map<int,int> m;//记录每个数出现了几次
	int cur=0;
	m.clear();
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
     //这个if保证a数组里没有重复数据
		if(m[x]==0)//map是O(log n),循环n次,一共是O(n log n)
		{
			a[++cur]=x;
		}
		m[x]++;
	}
	quickSort(a,1,cur);//进行快速排序,O(n log n),此时已经有去重和前两个优化,所以最坏的情况下也是O(n log n)
	for(int i=1;i<=cur;i++)//cur<=n,总共是O(n log n)
	{
		int num=m[a[i]];//log(n)
		for(int j=1;j<=num;j++)
		{
			printf("%d ",a[i]);
		}
	}

我用这种方法拿到了满分,这方法还是可行的!