蓝桥杯算法提高-快速排序-题解(C语言代码)快排/冒泡两种解法！

1528 阅读 4 评论 0 点赞

这题是我昨天月赛做的一题，比赛的时候规规矩矩用的快速排序
代码如下：
```c

#include<stdio.h>
int QKPass(int r[],int left,int right)
{
	int x=r[left];
	int low=left;
	int high=right;
	while(low<high)
	{
		while(low<high&&r[high]>=x)
			high--;
		if(low<high)
		{
			r[low]=r[high];
			low++;
		}
		while(low<high&&r[low]<x)
		{
			low++;
		}
		if(low<high)
		{
			r[high]=r[low];
			high--;
		}
	}
	r[low]=x;
	return low;
}
void QKsort(int r[],int low,int high)
{
	if(low<high)
	{
		int pos=QKPass(r,low,high);
		QKsort(r,low,pos-1);
		QKsort(r,pos+1,high);
	}
}
int main()
{
	int a[19],x;
	int i=0;
	do{
		scanf("%d",&a[i]);
		x=i;
		i++;
	}while(a[x]!=0);
	QKsort(a,0,i-2);
	for(int j=0;j<i-1;j++)
	{
		printf("%d ",a[j]);
	}
	return 0;
}
```
遗憾的是：该程序只能通过83%，不信你现在可以试一下
经过一番努力，发现将

```c
do{
		scanf("%d",&a[i]);
		x=i;
		i++;
	}while(a[x]!=0);
```
修改成
```c
while(i<10)
    {
    	scanf("%d",&a[i]);
    	if(a[i]==0)
    		break;
    	else
    	{
    		i++;
    		x++;
    	}
    }
或者
do{
		scanf("%d",&a[i]);
		x=i;
		i++;
	}while(a[x]!=0&&i!=11);//为什么不是10呢？因为当执行while里面语句的时候，此时i表示的数组的长度，长度不能大于10，自然而言不能等于11。
```
然后又能通过了，感到非常憋屈，就因为没有限定条件不允许超过十个吗？；所以最后快排的完整代码是
	
```c
#include<stdio.h>
int QKPass(int r[],int left,int right)
{
	int x=r[left];
	int low=left;
	int high=right;
	while(low<high)
	{
		while(low<high&&r[high]>=x)
			high--;
		if(low<high)
		{
			r[low]=r[high];
			low++;
		}
		while(low<high&&r[low]<x)
		{
			low++;
		}
		if(low<high)
		{
			r[high]=r[low];
			high--;
		}
		
	}
	r[low]=x;
	return low;
}
void QKsort(int r[],int low,int high)
{
	if(low<high)
	{
		int pos=QKPass(r,low,high);
		QKsort(r,low,pos-1);
		QKsort(r,pos+1,high);
	}
}
int main()
{
	int a[19],x;
	int i=0;
	while(i<10)
    {
    	scanf("%d",&a[i]);
    	if(a[i]==0)
    		break;
    	else
    	{
    		i++;
    		x++;
    	}
    }
	QKsort(a,0,i-1);
	for(int j=0;j<i ;j++)
	{
		printf("%d ",a[j]);
	}
	return 0;
}

```
今天来找题解，看到一个冒泡排序居然还通过了，我心态炸了
```c
#include<stdio.h> 
int main()
{
    int a[10],x=0,flat=1;//这里的x用来记录数组最后一个非零元素的下表 
    int i=0,j=0;
    while(i<10)
    {
    	scanf("%d",&a[i]);
    	if(a[i]==0)
    		break;
    	else
    	{
    		i++;
    		x++;
    	}
    }
     for(i=0;i<x ;i++)//长度为x的数组冒泡排序只需要 做x-1次循环
    {
        flat=0;//用于判断一次循环有没有交换过顺序
        for(j=0;j<x-1-i;j++)
        {
            if(a[j]>a[j+1])//做从小大到的排序，将最大的排到最后面，像这样依次进行
            {
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                flat=1;
            }
        }
        if(!flat) //没有交换过直接退出循环
            break;
    }
    for(i=0;i<x;i++)
    {
        printf("%d ",a[i]);
    }
}
```
需要说明的是，第二个程序里面flat在这个程序里面无关紧要，因为处理数据不是特别多，但是在那么数据比较多并且排列的数据 有从小到大的趋势的时候，大大减少了程序的负担。

0.0分

12 人评分

本文分类：题解列表
浏览次数：1528 次浏览
发布日期：2020-03-01 11:08:45
本文链接：https://blog.dotcpp.com/a/67275

上一篇 > 蓝桥杯算法提高-JOE的算数-题解(C++代码)快速幂算法
下一篇 > 汽水瓶-题解(C++代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 4 条评论

爱熬夜的菜鸟2333 3年前回复TA

@TheOne 感觉系统判定有时候不严谨

出家人 4年前回复TA

五星好评！
因为输入问题系统检测一直错误17%，看完一改直接AC

TheOne 4年前回复TA

后面的冒泡我是看了别人的才知道冒泡在这题可以使用，但是代码不全相同。
最后说一点，这是我第一次在这个网站认认真真分析的程序，希望浏览过的人可以留下脚印（批评或者建议啥的都可以）！
共同进步！
(另外一条评论看起来不方便，又不能删除，就又写了一条，哈哈哈）

TheOne 4年前回复TA

后面的冒泡我是看了别人的才知道冒泡在这题可以使用，但是代码不全相同。最后说一点，这是我第一次在这个网站认认真真分析的程序，希望浏览过的人可以留下脚印（批评或者建议啥的都可以）！共同进步！

蓝桥杯算法提高-快速排序-题解(C语言代码)快排/冒泡 两种解法！

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

蓝桥杯算法提高-快速排序-题解(C语言代码)快排/冒泡两种解法！

评论列表共有 4 条评论

发表评论取消回复