本题要求将给定的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;
}
冒泡排序与选择排序的区别
冒泡排序:通过重复遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已经排序完成。
选择排序:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。