蓝桥杯基础练习（十三）数列排序 C语言

Dear 丶 2022-03-22 04:52 451阅读 0赞

# 数列排序 C语言 #

**问题描述**  
　　给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200

**输入格式**  
　　第一行为一个整数n。  
　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。

**输出格式**  
　　输出一行，按从小到大的顺序输出排序后的数列。

**样例输入**  
5  
8 3 6 4 9

**样例输出**  
3 4 6 8 9

这道题就是简单的排序问题啦~ 用蛮力法搞定就行啦~ （终于不是上一道那种对笔者来说超级难的题了，感动）

说到蛮力法，蛮力法中有关数列排序的主要是**选择排序** 和 **冒泡排序**两种。 （笔者打开老师的PPT，一本正经地说道。）

所以笔者就打算将这两种方法都用一下，巩固巩固。

首先是选择排序。

选择排序，就是将数列分为有序区和无序区，初始阶段，有序区为空，然后每次都从无序区里找到一个最小的值放到有序区中。

理论上大概是这样， 代码如下：

#include <stdio.h>
    
    int main() { 
    	int n,i,j,min,temp;
    	int a[200];
    	
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	} 
    	
    	for(i=0;i<n-1;i++)  //由上面的概念可知，有序区每次都加一，即无序区中需要排列的数字每次都少一个，所以用i<n-1
    	{ 
    		min=i;    //每次都假设数列中无序区的第一个数字为最小值
    		for(j=i+1;j<n;j++) //找到最小值
    		{ 
    			if(a[j]<a[min])
    			{ 
    				min=j;
    			}
    		}
    		
    		if(min!=i)  //如果最小值与假设的不一样，则将最小值与第一个数字交换位置
    		{ 
    			temp=a[i];
    			a[i]=a[min];
    			a[min]=temp;
    		}
    	}
    	
    	for(i=0;i<n;i++)
    	{ 
    		printf("%d ",a[i]);
    	}
    	return 0;
    }

读者最好自己写一组数列再看概念及代码，应该更容易看懂一些哦~

而冒泡排序呢，就很简单了~

它的基本思想是：  
1、和选择排序一样，分为有序区和无序区，但这里需要注意的是，选择排序有序区在左边，而冒泡排序的有序区在右边（无序区略）

2、enmmm，也和选择排序一样，初始时，有序区为空，无序区为整个数列。

3、第一次“冒泡”相邻元素依次两两比较，将较大者/较小者交换到后面，成为有序区的**第一个元素**。

代码如下：

#include <stdio.h>
    
    int main() { 
    	int n,i,j,temp;
    	int a[200];
    	
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	} 
    	
    	for(i=0;i<n-1;i++)
    	{ 
    		for(j=0;j<n-1-i;j++)
    		{ 
    			if(a[j]>a[j+1])
    			{ 
    				temp=a[j];
    				a[j]=a[j+1];
    				a[j+1]=temp;
    			}
    		} 
    	}
    	
    	for(i=0;i<n;i++)
    	{ 
    		printf("%d ",a[i]);
    	}
    	return 0;
    }

这个很简单的，我就不解释啦~~

这里要说一点，笔者看了一下老师的PPT，才发现以上这段只是冒泡排序的一种算法，其实后面还有一种比较复杂的，代码如下：

#include <stdio.h>
    
    int main() { 
    	int n,i,j,temp,bound;
    	int a[200];
    	
    	scanf("%d",&n);
    	
    	for(i=0;i<n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	} 
    	
    	int exchange=n-1;
    	
    	while(exchange!=0)  //当序列有序时，exchange=0
    	{ 
    		bound=exchange;
    		exchange=0;
    		for(j=0;j<bound;j++)
    		{ 
    			if(a[j]>a[j+1])
    			{ 
    				temp=a[j];
    				a[j]=a[j+1];
    				a[j+1]=temp;
    				exchange=j;
    			}
    		}
    	}
    	
    	for(i=0;i<n;i++)
    	{ 
    		printf("%d ",a[i]);
    	}
    	return 0;
    }

这个详细解释笔者也解释不来，同样，读者只需要列一段数列看着代码“运行”一遍就一目了然了。

这里主要添加了exchange变量，来判断一次冒泡后序列是否是有序序列，如果序列在while中数字位置经过变换，则需要继续执行一遍循环。

最后，笔者对这三种方法的有略进行了比较，从每种算法的**最优/最差比较次数** 以及 **最优/最差交换次数**上看：

选择排序：  
![在这里插入图片描述][20190126002001605.png]  
冒泡算法1：  
![在这里插入图片描述][20190126002209644.png]冒泡算法2：  
![在这里插入图片描述][20190126002252740.png]过程自己算啊，应该不会太困难的~~，所以，由上面数据可知，根据数列无序程度的不同，选择和冒泡。。。算是各有优劣吧。

而冒泡的两种算法，第二种算法是第一种的升级版，所以应该是第二种比较好。

但是，评测系统给出的比较笔者真的是…有点无法理解啊！  
直接上图：  
![在这里插入图片描述][20190126002708186.png]  
从上至下依次是：冒泡1，冒泡2，选择

没错，居然是冒泡算法1好一点？？？

也许是评测系统用的那10个例子的锅吧？可惜笔者不是vip，没法查看系统另外的9个输入了什么鬼…

总结完毕~ 撒花 ~~

[20190126002001605.png]: /images/20220322/590825da89f342d8983a20b730da03fa.png
[20190126002209644.png]: /images/20220322/9381fc54d24e42e9bb71066acdc9d399.png
[20190126002252740.png]: /images/20220322/1390480ce709485192ffe5dd8b217acf.png
[20190126002708186.png]: /images/20220322/4e2ed960382244feb159abc0038d93f7.png