C51-冒泡排序

零、作业练习

#include<iostream>
using namespace std;
int main(){
	int t;
	cin >> t;
	while (t--){
		int n, sum = 0;
		cin >> n;
		while (n){
			sum += n%10;
			n /= 10; 
		}
		if (sum%2==1) cout<<"YES\n";
		else cout<<"NO\n"; 
	} 
	

	return 0;
}

一、埃氏筛法

//埃氏筛法 
#include<iostream>
using namespace std;

const int N = 1e6+5; 	//科学计数法
bool st[N] = {1,1}; 			//0表示质数， 1表示合数 

//质数的倍数一定是合数 
void aip() {
	for (int i=2; i<=N; i++){
		if (st[i] == 0){
			for (int j=i+i; j<=N; j+=i) {
				st[j] = 1;	//质数的倍数一定是合数  
			}
		}
	} 
}

int main(){
	aip(); 
	int t, n;
	cin >> t;
	while (t--){
		cin >> n;
		for (int i=n-1; i>1; i--){
			if (st[i]==0){
				cout << i << endl;
				break; 
			} 
		}
	} 

	return 0;
}

二、冒泡排序

两两比较相邻的两个数字，进行交换。时间复杂度为O(n*n)
排序过程

#include<iostream>
using namespace std;

int a[1005], n;

int main(){
	cin >> n;
	for (int i=1; i<=n; i++) cin>>a[i]; 
	
	//bubble sort
	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]);
		}
	} 
	
	for (int i=1; i<=n; i++) cout<<a[i]<<' ';
	cout<<endl;

	return 0;
}

#if 0
5
34 2 12 7 25


n=5
需要比较 4 趟 
第1趟： 2 12 7 25 34	//比较了4次
第2趟： 2 7 12 25 34	//比较了3次 
第3趟： 2 7 12 25 34	//比较了2次 
第4趟： 2 7 12 25 34	//比较了1次 


n个数
比较n-1趟
n-1, n-2 n-3 .... 1
1+2+3+4+...+n-1
(1+n-1)*(n-1)/2


#endif 

三、作业练习

4.1AC课后题单【U2-7 循环嵌套1】 中， 任选6道题目。
作业连接