PTA-C语言题库-选择排序（选择排序、冒泡排序+解法+解析）

本题要求将给定的n个整数从大到小排序后输出。

输入格式：

输入第一行给出一个不超过10的正整数n。第二行给出n个整数，其间以空格分隔。

输出格式：

在一行中输出从大到小有序的数列，相邻数字间有一个空格，行末不得有多余空格。

输入样例：

4
5 1 7 6

输出样例：

7 6 5 1

冒泡排序解法：

#include<stdio.h>
int main(){
	int arr[10];
    int i,j,n,temp;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    for(i=0;i<n-1;i++){//每一次都从i开始向后比较，把i和j中较大的数赋值给i位，继续向后比较，遇到更大的同样处理，之后i+1，继续向后比较
    	for(j=i+1;j<n;j++){
    		if(arr[i]<arr[j]){
    			temp=arr[j];
    			arr[j]=arr[i];
    			arr[i]=temp;
			}
		}
	}
	for(i=0;i<n-1;i++){
        printf("%d ",arr[i]);
    }
    printf("%d",arr[n-1]);
	return 0;
}

这是最简单的写法，思路解析已经标在代码关键处。

简单举一个例子示范一下

输入4，再输入5 1 7 6

输入之后进入循环，arr[i]=arr[0]=5，然后开始内层的j循环，arr[j]=arr[1]=1，不符合if语句，j++，j=2时候arr[2]=7，符合if语句，与arr[0]互换，此时数字顺序变成了7 1 5 6

接下来继续内层j循环，依旧不符合，直到遍历完内层。i++，arr[i]=arr[1]=1，内层从j=2开始arr[j]=arr[2]=5，符合if语句，与arr[1]互换，数字顺序变成7 5 1 6

之后继续内层，遇到j=3时，arr[3]大于arr[1]，再次互换，数字顺序变为7 6 1 5

最后i++，同样运行一遍，数字变成7 6 5 1

最后输出即可。

经过分析，这个代码一共需要运算（1+2+3+……+n-1）次循环

显然，冒泡排序在这种情况下效率有些低

---

选择排序解法

#include<stdio.h>
 
int main() {
    int arr[20] = {0};
    int i, j, n, temp;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (i = 0; i < n - 1; i++) {
        int max_idx = i; // 假设未排序部分的最大元素索引是i
        for (j = i + 1; j < n; j++) {
            if (arr[j] > arr[max_idx]) {
                max_idx = j; // 更新最大元素的索引
            }
        }
        if (max_idx != i) { // 如果最大元素的索引不是i，则需要交换
            temp = arr[i];
            arr[i] = arr[max_idx];
            arr[max_idx] = temp;
 
        }
    }
 
    for (i = 0; i < n - 1; i++) {
        printf("%d ", arr[i]);
    }
    printf("%d", arr[n - 1]);
    return 0;
}

---

冒泡排序与选择排序的区别

冒泡排序：通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。
选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。