当前位置：首页 > news >正文

【经典算法学习-排序篇】冒泡排序

news 来源：原创 2024/5/5 20:29:39

一、冒泡排序

1.基本概念和介绍

冒泡排序的基本思想：依次比较相邻的两个是否逆序对，若逆序就交换。

冒牌排序

冒泡排序的思想理解起来非常简单：以n个数为例，从第1个数开始，依次比较，即第1个和第2个比，若第1个数比第2个数大，就交换两数。以此类推，直到第n-1个数和第n个做比较。

像这样，把最大的数排在最后，即将最大的数像冒泡一样逐步冒到相应的位置。就这样，一个n个数排序的问题就转换为了n-1个数的排序问题。如此进行n-1此后，队列变为了有序队列。

我们可以使用一幅动图来解释：

2.冒泡排序

e.g.1: 输入n个数，将这n个数按照从小到大排序。

输入

输入一个数字n和一个长度为n的序列，通常将这n个数直接放进数组中。

输出

输出一个新序列，满足按照从小到大的顺序排序。

算法说明

冒泡排序的基本大致流程如下：

读入数据，将数据存放到a数组中;
比较相邻的两个数据，如果前面的数据大于后面的数据，就将两数交换;
对数组的第1个到底n个数进行一次遍历以后，最大的数就冒到了数组第n个位置;
n = n - 1，如果n不为1，就重复步骤②和步骤③，否则排序完成。

3.代码实现

#include <iostream>

using namespace std;

int main()
{
	int a[1024],n;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n; i ++)
	{
		for(int j = 0; j < n - i - 1; j ++)
		{
			if(a[j] > a[j+1])
			{
				swap(a[j], a[j+1]);
			}
		}
	}
	for(int i = 0; i < n; i ++) {
		cout << a[i] << " ";
	}
	return 0;
}

4.时间复杂度分析

最优情况

最优情况莫过于是正向有序，只需要进行一趟排序，即比较n-1次就可以了。此时，一共交换了0次，时间复杂度为 $O(n)$ .

最差情况

最差情况恰好和最优情况相反，在序列为逆向有序时，进行n-1趟排序，比较n-1次，交换n-1次，时间复杂度也就因为有两层循环而变成 $O(n^{2})$ 了.

平均情况

综合上述两种情况，可以得到冒泡排序的时间复杂度为：

$\frac{O(n) + O(n^2)}{2} = \frac{O(n + n^2)}{2} = O(n^2)$

5.代码优化

对于有些数据，我们不难发现，不一定要n-1才能排完。

例如一组数据"1 5 2 3 4 6"，我们发现只需要一趟排序就可以将整组序列排完了。

于是，我们可以设置一个bool类型的变量，记录本次循环是否有进行交换，如果没有就可以直接跳出循环了。

#include <iostream>

using namespace std;

int main()
{
	int a[1024],n;
	bool flag;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n; i ++)
	{
		flag = true;
		for(int j = 0; j < n - i - 1; j ++)
		{
			if(a[j] > a[j+1])
			{
				swap(a[j], a[j+1]);
			}
			flag = false;
		}
		if(flag == true)
		{
			break; // 没有进行交换，直接跳出循环 
		}
	}
	for(int i = 0; i < n; i ++) 
	{
		cout << a[i] << " ";
	}
	return 0;
}