每日刷题 Day22

题一：直接插入排序

#include<iostream>
#include<vector> 
using namespace std;

vector<int> InsertSort(vector<int> str){
	int temp;  //用于暂存待插入元素 
	int j;
	for(int i=1;i<str.size();i++){	//因为将第一个元素看作有序区，所以从第二个元素开始 
		temp=str[i];
		j=i-1;   //标记有序区的最后一个元素 
		while(temp<str[j]){  //倒着和有序区的元素进行比较，若待插入元素小于比较元素，则将有序区元素向后移动 
			str[j+1]=str[j];	//直至找到插入位置 
			j--; 
		} 
		str[j+1]=temp;//将待插入元素插入 
	}
	return str;
}
int main(){
	/*插入排序：插入排序的序列分为两部分，有序区和无序区，每进行一趟，就将无序区里的一个元素插入有序区中 
		初始时，将第一个元素看为初始有序区，从第二个记录一次插入到有序序列中，直至将第n个记录插入 
	*/ 
	vector<int> str;
	int num;
	cin>>num;
	int temp;
	for(int i=0;i<num;i++){
		cin>>temp;
		str.push_back(temp); //创建数组
	}
	str=InsertSort(str);
	for(int i=0;i<str.size();i++){
		cout<<str[i]<<" ";
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

题二：冒泡排序

#include<iostream>
#include<vector> 
using namespace std;

/*
冒泡排序：（实现从小到大排序）
进行一趟排序时，将相邻的两个元素进行比较，将比较小的数放在前面，比较大的数放在后面。直到数组最后一个元素
每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值
*/
vector<int> BubbleSort(vector<int> str){
	int i=0;//用来标记是第几趟排序
	int visit=1; //用来标记每趟排序中是否有交换元素,若有元素交换,则visit=1;若无,则visit=0 
	while(visit!=0){
		visit=0;	//进入循环前将其置0 
		for(int j=1;j<=str.size()-i-1;j++){  //每趟遍历len-i-1个元素 
			if(str[j-1]>str[j]){		//交换相邻元素，小的在前，大的在后
				int temp=str[j-1];
				str[j-1]=str[j];
				str[j]=temp;
				visit=1; //表示有元素交换
			}
		}
		i++;
	}
	return str;
} 
int main(){
	vector<int> str;
	int num;
	cin>>num;
	int temp;
	for(int i=0;i<num;i++){ //构建数组 
		cin>>temp;
		str.push_back(temp);
	}
	str=BubbleSort(str);
	for(int i=0;i<str.size();i++){
		cout<<str[i]<<" ";
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

题三：简单选择排序

#include<iostream>
#include<vector> 
using namespace std;
/*
简单选择排序：
将数据分为有序区和无序区，初始时，有序区为空
选择无序区的最小元素，加入有序区的末尾 
*/
vector<int> SelectSort(vector<int> str){
	int min=0; //用来保存最小元素的下标 
	for(int i=0;i<str.size();i++){
		min=i;
		for(int j=i+1;j<str.size();j++){	//寻找最小元素 
			if(str[j]<str[min])
			min=j;
		}
		if(min!=i){
			int temp=str[i];
			str[i]=str[min];
			str[min]=temp;
		} 
	}
	return str;
} 
int main(){
	vector<int> str;
	int num;
	cin>>num;
	int temp;
	for(int i=0;i<num;i++){ //构建数组 
		cin>>temp;
		str.push_back(temp);
	}
	str=SelectSort(str);
	for(int i=0;i<str.size();i++){
		cout<<str[i]<<" ";
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39