C34-10.6选择排序

原题链接：38471.note1

1943

2025-10-06 18:06:16

发布于：江苏

19阅读

0回复

0点赞

一、上节课作业部分

#1. 车厢重组

    #include <iostream>
using namespace std;

int a[10010], cnt;

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	//外层：表示比较趟数 
	for (int i=1; i<=n-1; i++){
		//内层： 
		for (int j=1; j<=n-i; j++){
			if (a[j] > a[j+1]){
				swap (a[j], a[j+1]);
				cnt++; 
			}
		}
	} 
	
	cout << cnt;
	
	
	return 0;
}

/*
[冒泡排序]

#if 0
输入：
5
7 6 5 3 2
原数组：7 6 5 3 2
第一轮：6 5 3 2 7  比较4次
第二轮：5 3 2 6 7  比较3次
第三轮：3 2 5 6 7  比较2次
第四轮：2 3 5 6 7  比较1次

输出
2 3 5 6 7  

n个数 
假设i表示趟数 
轮数（趟数）: n-1 
每一趟比较几次 n-i

一共比较多少次：
1+2+3+4+ .... + n-1(等差数列)

二、一次选择排序

#include <bits/stdc++.h>
using namespace std;

int a[105], n;

int main(){
	cin >> n;
	for (int i=1; i<=n; i++) cin>>a[i];
	
	//打擂台找最小值
	int minx = 1;	//下标 
	for (int i=2; i<=n; i++){
//		如果 当前值 比 擂主 小
//		那么 更新擂主 为 当前值
		if (a[i] < a[minx]){
			minx = i;	//记录最小值下标 
		} 
	} 
	swap(a[minx], a[1]); 
	
	for (int i=1; i<=n; i++) cout << a[i] <<' ';
	
	
	return 0;
}

/*
[一趟选择]
题目描述
输入 n，再输入 n 个数，
将这 n 个数经过一趟选择将最小值和第 1 个元素交换。

提示
【数据范围】（0 < n ≤ 100）

输入格式
输入有 2 行，第 1 行输入 n，第 2 行输入 n 个整数。

输出格式
输出经过一趟选择后的 n 个整数，数字间用一个空格隔开。

样例组
输入#1
5
6 3 2 7 5
2 3 6 7 5
2 3 6 7 5
2 3 5 7 6
2 3 5 6 7
输出#1
2 3 6 7 5
*/