排序:1.2、冒泡排序

排序:1.2、冒泡排序,第1张

排序:1.2、冒泡排序

文章目录

前言一、冒泡排序原理二、冒泡排序源码三、示例结果四、总结


前言

在此之前,我们介绍了简单的桶排序,虽然其简易上手,容易 *** 作。但具有较为严重的空间浪费,也难以键值对一一匹配,还有就是当数值是小数,就无法处理,毕竟数组没有小数吧。哈哈哈。
这里为了进一步解决其小坑,我们介绍了一种较为简单的冒泡排序。


一、冒泡排序原理 冒泡排序主要依靠对数组的双重循环,两两比较,对数值进行排序。
如数组a[0]-a[4]值为:13.5、64、32、99.9、66
第1轮两两比较:64、32、99.9、66、13.5
第2轮两两比较:64、99.9、66、32、13.5
第3轮两两比较:99.9、66、64、32、13.5
这里虽然已经排序完毕,但还需继续比较排序。因为这边只是凑巧,如果是其它值就不一定了哦。 第4轮两两比较:99.9、66、64、32、13.5
顺利排序完毕。
这里我们可以发现,n个数值只需遍历n-1次。
第1轮遍历,两两比较n-1次,可以将最小的数值扔至最后位。
第2轮遍历,两两比较n-2次,可以将第2小的数值扔至倒数第2位。
……
第n-1轮遍历,两两比较1次,可以将倒数第2小(第2大)的数值,扔到倒数倒数第2位(第2位)。
为什么是n-1次呢?因为到了最后,只剩下最后一个,肯定就是它最大了喽。 为什么两两比较是n-i次呢?因为每一次遍历都会将比较的最小是放到该比较序列的最后一位,下一次就不需要再次进行比较了。
二、冒泡排序源码
#include 
using namespace std;

struct students
{
	string name;
	int score;
};

int main()
{
	cout << "排序的数组长度:";
	int n;
	cin >> n;
	students *a = new students[n];
	cout << "输入学生的姓名和成绩:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "第"<> a[i].name >> a[i].score;
	}

	int tempScore = 0;
	string tempName= "";
	for (int i = 0; i < n-1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j].score < a[j+1].score)
			{
				tempScore = a[j].score;
				tempName = a[j].name;
				a[j].score = a[j + 1].score;
				a[j].name = a[j + 1].name;
				a[j + 1].score = tempScore;
				a[j + 1].name = tempName;
			}
		}
	}

	cout << "排序后的学生姓名和成绩(从高到低):" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i].name << " " << a[i].score<<" ";
	}

	delete[]a;

	return 0;
}
三、示例结果

四、总结 这边我们可以很容易看出,对数值进行二重循环下的冒泡排序的时间复杂度是O(n^2),其实这就已经是很糟糕的了。所以正如Donald E. Knuth所言,“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实 之外,似乎没有什么值得推荐的。

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5719186.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存