C语言-冒泡法与选择法区别

本当迷

2021 年 05 月 27 日

1286 次浏览

暂无评论

581字数

学习语言

### 冒泡法

定义：冒泡排序的英文是bubblesort，它是一种基础的交换排序

原理：每次比较两个相邻的元素，将较大的元素交换至右端 (升序排序)

思路：相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变

案例分析：

1. 初始的无序数列 {5,8,6,3,9,2,1,7}，希望对其升序排序
2. 按照思路分析：

![3bb7cf853f3a6791f506d21616b61340.png](https://www.bdmcom.cn/usr/uploads/2021/05/2103896143.png)

在经过第一轮交换后，最大的数 9 冒泡到了最右边

![23e9411b5503a0e4802dd74e2010644a.png](https://www.bdmcom.cn/usr/uploads/2021/05/2846654608.png)

到此为止，所有元素都是有序的了，这就是冒泡排序的整体思路。

代码实现：

```cpp
#include<stdio.h>
int main ()
{
	int a[8] = {5, 8, 6, 3, 9, 2, 1};
	int i, j, temp;
	for (i=0; i<7; i++)
	{
		for (j=0; j<7-i; j++)
		{
			if (a[j+1] < a[j])
			{
				temp = a[j+1];
				a[j+1] = a[j];
				a[j] = temp;
			}
		}
	}
	for (i=0; i<8; i++)
	{
			printf ("%d",a[i]);

}
	return 0;
}
```

### 选择法：

![](https://www.bdmcom.cn/usr/uploads/2021/05/1204273119.jpg)

![](https://www.bdmcom.cn/usr/uploads/2021/05/24480578.jpg)

思路：遍历数组中未排序的部分，取出最小值，和未排序的第一个交换位置，然后重复此操作

代码实现：

```cpp
#include<stdio.h>
int main ()
{
	int a[7] = {13, 38, 65, 97, 76, 49, 27};
	int i, j, temp;
	for (i=0; i<6; i++)
	{
		for (j=i + 1; j<7; j++)
		{
			if (a[i] > a[j])
			{
				temp = a[j];
				a[j] = a[i];
				a[i] = temp;
			}
		}
	}
	for (i=0; i<7; i++)
	{
			printf ("%d ",a[i]);

}
	return 0;
}
```

### 总结：

**冒泡法**

*优点：*比较简单，空间复杂度较低，是稳定的；

*缺点：*时间复杂度太高，效率慢；

**选择法**

*优点：*一轮比较只需要换一次位置；

*缺点：*效率慢（相对于冒泡法效率高），不稳定（举个例子5，8，5，2，9   我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。

最后修改：2021 年 08 月 23 日