C++ · 冒泡排序与选择排序

九月份的第一篇文章

好久没更新了，想起上一次更新还是在上一次，那今天咱们来聊一聊C++中的冒泡排序与选择排序

冒泡排序

排序原理与思想

依次比较相邻的两个数，把大的放前面，小的放后面。即首先比较第1个数和第2个数，大数放前,小数放后。然后比较第2个数和第3个数…直到比较最后两个数。第一趟结束，最大的数一定排在最后。

重复上过程,仍从第1个数开始,到最后第2个数，然后…
由于在排序过程中总是小数往前，大数往后，相当于气泡上升，所以称作冒泡排序。

程序实现

循环实现，双层嵌套循环控制每一个数字并排序，可以用if语句实现判断，然后使用swap函数将两个数调换位置，并且要加一个flag变量，它的作用是：排完序后，直接跳出循环
代码实现：

#include 
using namespace std;

int main ()
{
	int n,ch[1005],flag=0; //n表示要排序的数字数量，ch是数字列表，flag如上所述
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ch[i]; //输入每一项
	}
	/*
	  ...其余代码区(1处)
	*/
	for(int i=1;i<=n;i++){
		cout<<ch[i]<<" "; //输出
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输入和输出搞定了。接下来，我们实现排序程序

for(int i=1;i<=n;i++){
	flag=0; //flag为0时，表示未排序，反之，flag为1时，表示已排序
	for(int j=1;j<=n-1;j++){
		if(ch[j]>ch[j+1]){ //判断
			flag=1; //已排序标记
			swap(ch[j],ch[j+1]); //swap函数调换位置
			/*int temp=ch[j];
			ch[j]=ch[j+1];
			ch[j+1]=temp;*/
		}
	}
	if(flag==0){ //如果已排序，跳出循环
		break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

直接将这块代码加入到1处代码区即可运行
完整代码如下：

#include 
using namespace std;

int main ()
{
	int n,ch[1005]={0},flag=0; //ch数组归零
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ch[i];
	}
	for(int i=1;i<=n;i++){
		flag=0;
		for(int j=1;j<=n-1;j++){
			if(ch[j]>ch[j+1]){
				flag=1;
				swap(ch[j],ch[j+1]);
				/*int temp=ch[j];
				ch[j]=ch[j+1];
				ch[j+1]=temp;*/
			}
		}
		if(flag==0){
			break;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ch[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

当然，你也可以把数组ch的类型改成double型，让程序可以为小数排序
代码如下：

#include 
using namespace std;

int main ()
{
	int n,flag=0;
	double ch[1005]={0.0}; //数组归零
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ch[i];
	}
	for(int i=1;i<=n;i++){
		flag=0;
		for(int j=1;j<=n-1;j++){
			if(ch[j]>ch[j+1]){
				flag=1;
				swap(ch[j],ch[j+1]);
				/*int temp=ch[j];
				ch[j]=ch[j+1];
				ch[j+1]=temp;*/
			}
		}
		if(flag==0){
			break;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ch[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

---

题外话：swap函数的用法

swap函数可以交换数组中两个下标不同的值，需要注意语法
交换数组中两个下标不同的值：

#include 
using namespace std;

int main ()
{
	int a[5];
	for(int i=0;i<5;i++){
		cin>>a[i];
	}
	swap(a[0],a[1]); //交换数组a中第一项与第二项的值
	for(int i=0;i<5;i++){
		cout<<a[i]<<" ";
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

请注意，swap函数与sort函数一样，都是没有返回值的函数，因此，我们必须要写输出才能将数组中的数据显示出来

---

选择排序

排序原理与思想

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。
示例：
初始 列表 [49 38 65 97 76 13 27 49]
第一趟排序后 13［38 65 97 76 49 27 49］
第二趟排序后 13 27［65 97 76 49 38 49］
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76 97

程序实现

采用“打擂台”的思想，找出数组中的最大值或最小值，调换位置，这一轮排序结束。
如果还有同学不知道怎样找出最大值或最小值，可以看看我的这篇文章：C++找最大/最小值

代码实现：

#include 
using namespace std;

int main () {
	int n,ch[1005];
	cin>>n;

	for(int i=1;i<=n;i++) {
		cin>>ch[i];
	}
	/*
	  ...其余代码区(2处)
	*/
	for(int i=1;i<=n;i++){
		cout<<ch[i]<<" ";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我们来写排序的代码，将以下代码复制到2处代码区即可：

for(int i=1;i<=n-1;i++){
	int minn=99999,k;
	for(int j=i;j<=n;j++){
		if(ch[j]<minn){
			minn=ch[j]; //最小值
			k=j; //序号
		}
	}
	swap(ch[i],ch[k]); //调换顺序
	/*
	int tmp=a[i];
	a[i]=a[k];
	a[k]=tmp;
	*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整代码：

#include 
using namespace std;

int main () {
	int n,ch[1005];
	cin>>n;

	for(int i=1;i<=n;i++) {
		cin>>ch[i];
	}
	for(int i=1;i<=n-1;i++){
		int minn=99999,k;
		for(int j=i;j<=n;j++){
			if(ch[j]<minn){
				minn=ch[j];
				k=j;
			}
		}
		swap(ch[i],ch[k]);
		/*
		int tmp=a[i];
		a[i]=a[k];
		a[k]=tmp;
		*/
	}
	for(int i=1;i<=n;i++){
		cout<<ch[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

你也可以对程序稍作修改，使其可以用最大值排序或者从大往小排序，这里就不加赘述啦

---

好的，那这就是本期的全部内容，如果你喜欢我的文章，记得点赞加关注哦，咱们下期再见！