西安交大计算机考研软件工程编程题库（十）

鄙人今年备考，主要目的在于记录学习历程，望道友们勿喷~
希望能做到每日一题~
开始炼丹~

上篇链接：西安交大计算机考研软件工程编程题库（九）
下篇链接：西安交大计算机考研软件工程编程题库（十一）

文章目录

西安交大计算机考研软件工程编程题库（十）
一、题目
二、解答
总结

一、题目

用冒泡排序法或选择排序法对20个数据进行排序后输出，并给出现在每个元素所对应的原来的次序。

二、解答

1.分析

分析一波，本题的要求十分明确，输入数据，用选择或者冒泡排序法对其进行排序操作，因为是预备考研，所以打算都写一下。简单概括一下两个算法的实现方式

冒泡排序已经多次在文章中出现了（以升序为例），其原理一句话概括一下就是每次将当前最大（or最小）的元素通过不断地交换放到尾部（or首部）；
而选择排序（以升序为例）所做的是通过不断地比较，每次从数组中选择出最小的元素，放到对应的位置（第一次选出第一小的数放到首尾，第二次选出第二小的数放到第二个位置，以此类推。）
二者的时间复杂度皆为O(n²)，且两种排序每结束一趟循环皆可以实现将一个元素放到其指定的位置上，但选择排序不稳定（例5,2,5,3,1这几个数在第一轮1和5会换位，由此第二个5就跑到了第一个5 的前面），而冒泡排序则可以做到稳定（同样是上面的例子，只要确保交换位置的条件是前者>后者时才交换，就可使算法稳定）。
啰嗦了一些，实现一下。

Ps：不出意外鄙人的此系列文章都会用C实现，其他语言的道友见谅~。

2.代码实现

代码如下：

#include<stdio.h>
int main(){
	int i = 0, j = 0;  //用于循环
	int result[21];   //用于存放结果
	
	//输入数据
	printf("请输入20个数：\n");
	for(i = 1; i < 21; i++) scanf("%d", &result[i]);
	printf("初始数据如下：\n");
	for(i = 1; i < 21; i++) printf("%d\t", result[i]);
	
	//冒泡排序
	for(i = 1; i < 21; i++){
	    for(j = i+1; j < 21; j++){
	        if(result[i] > result[j]){
	            result[0] = result[i];
	            result[i] = result[j];
	            result[j] = result[0];
	        }
	    }
	}
	
	/*道友自行解封
	//选择排序
	int min = 0; //标记当前最小元素位置
	for(i = 1; i < 21; i++){
	    min = i;
	    for(j = i; j < 21; j++){
	        if(result[min] > result[j]){
	            min = j;
	        }
	    }
	    if(min != i){
	        result[0] = result[min];
	        result[min] = result[i];
	        result[i] = result[0];
	    }
	}
	*/
	
	//输出结果
	printf("\n排序后结果如下：\n");
	for(i = 1; i < 21; i++) printf("%d\t", result[i]);
	return 0;
}