运用大O来给代码提速(冒泡排序)

举报
花想云 发表于 2023/05/31 23:33:14 2023/05/31
【摘要】 大 O记法能客观地衡量各种算法的时间复杂度,是比较算法的利器。我们也试过用它来对比二分查找和线性查找的步数差异,发现二分查找的步数为 O(log N),比线性查找的 O(N)快得多。然而,写代码的时候并不总有这样明确的二选一,更多时候你可能就直接采用首先想到的那种算法了。不过有了大 O的话,你就可以与其他常用的算法比较,然后问自己:“我的算法跟它们相比,是快还是慢?”如果你通过大 O 发现自己的算

 

本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。  

本章内容

写在前面

1.冒泡排序

2.冒泡排序实战

3.冒泡排序的实现

4.冒泡排序的效率

5.二次问题

6.线性解决

7.总结


写在前面

大 O记法能客观地衡量各种算法的时间复杂度,是比较算法的利器。我们也试过用它来对比二分查找和线性查找的步数差异,发现二分查找的步数为 O(log N),比线性查找的 O(N)快得多。

然而,写代码的时候并不总有这样明确的二选一,更多时候你可能就直接采用首先想到的那种算法了。不过有了大 O的话,你就可以与其他常用的算法比较,然后问自己:“我的算法跟它们相比,是快还是慢?”

如果你通过大 O 发现自己的算法比其他的要慢,你就应该退一步,好好想想怎样优化它,才能使它变成更快的那种大 O。

本章我们会写些代码来解决一个实际问题,并且会用大 O 来测量算法的性能,然后看看是否能对算法做些修改,使得性能提升。


1.冒泡排序

排序算法是计算机科学中被广泛研究的一个课题。历时多年,它发展出了数十种算法,这些算法都着眼于一个问题:

如何将一个无序的数字数组整理成升序?

冒泡排序是一种很基本的排序算法,步骤如下。

(1) 指向数组中两个相邻的元素(最开始是数组的头两个元素),比较它们的大小。

(2) 如果它们的顺序错了(即左边的值大于右边),就互换位置。 

如果顺序已经是正确的,那这一步就什么都不用做。

(3) 将两个指针右移一格。

重复第(1)步和第(2)步,直至指针到达数组末尾。 

(4)重复第(1)至(3)步,直至从头到尾都无须再做交换,这时数组就排好序了

这里被重复的第(1)至(3)步是一个轮回,也就是说,这个算法的主要步骤被“轮回”执行直到整个数组的顺序正确。


2.冒泡排序实战

下面来举一个完整的例子。假设要对 [4, 2, 7, 1, 3] 进行排序,产生一个升序的数组。

开始第 1次轮回。

数组一开始如下图所示。

第 1步:首先,比较 4和 2。如图可见它们的顺序是错的

第 2步:交换它们的位置。 

第 3步:比较 4和 7。

它们的顺序正确,所以不用做什么交换。 

第 4步:比较 7和 1。

第 5步:顺序错误,于是进行交换。

第 6步:比较 7和 3。

第 7步:顺序错误,于是进行交换。

因为我们一直把较大的元素换到右边,所以现在最右侧的 7正处于其正确位置上。这也正是此种算法名为冒泡排序的原因:每一次轮回过后,未排序的值中最大的那个都会“冒”到正确的位置上。 

因为刚才那次轮回做了不止一次的交换,所以得继续轮回。

下面来第 2次轮回。

此时 7已经在正确的位置上了。

第 8步:从比较 2和 4开始。

它们已经按顺序排好了,所以直接进行下一步。

第 9步:比较 4和 1。

第 10步:它们的顺序错误,于是交换。

第 11步:比较 4和 3。

第 12步:顺序错误,进行交换。

因为 7 已经在上一次轮回里排好了,所以无须比较 4 和 7。此外,4 移到了正确的位置,本次轮
回结束。 因为这次轮回也做了不止一次的交换,所以得继续轮回。

下面来第 3次轮回。

第 13步:比较 2和 1。

第 14步:顺序错误,进行交换。

第 15步:比较 2和 3。

顺序正确,不用交换。 

这时 3也“冒”到其正确位置了。因为这次轮回做了不止一次的交换,所以还要继续。

于是开始第 4次轮回。

第 16步:比较 1和 2。

顺序正确,不用交换。而且剩下的元素也都排好序了,轮回结束。

因为刚才的轮回没有任何交换,可知整个数组都已排好序。


3.冒泡排序的实现

以下是用 C语言写的冒泡排序。

void BubbleSort(int arr[], int n) //n为数组的大小
{
	for (int i = 0; i < n-1; i++)//n个数字,把n-1个排好,剩下一个自然在正确的位置
	{
		for (int j = 0; j < n - 1 - i; j++)//每一个轮回之后,末端的数字已经到了正确的位置上,不需要比较
		{
			//比较相邻数字
			//升序为 >,降序为 <
			if (arr[j] > arr[j + 1])
			{
				//交换两个数字的位置
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

解释:
这里的实现用了两层循环。最外层的循环用i来控制,表示的是一个轮回。

i<n-1,其含义为有n个数,只需要走n-1个轮回。因为,我们把n-1个数排好之后,剩下的那个数自然在正确的位置上了。

内层循环由j来控制,进行的是一次轮回中,把一个数“冒”到正确的位置上。

此处的代码就是对上一小节冒泡排序实战的翻译。


4.冒泡排序的效率

冒泡排序的执行步骤可分为两种。

比较:比较两个数看哪个更大。

交换:交换两个数的位置以使它们按顺序排列。

先看看冒泡排序要进行多少次比较。

回顾之前那个 5个元素的数组,你会发现在第 1次轮回我们为 4对元素进行了 4次比较。

到了第 2次轮回,则只做了 3次比较。这是因为第 1次轮回已经确定了最后一个格子的元素,所以不用再比较最后两个元素了。

第 3次轮回,只比较 2次;第 4次,只比较 1次。

算起来就是:4 + 3 + 2 + 1 = 10 次比较。

推广到 N个元素,需要

(N - 1) + (N - 2) + (N - 3) + … + 1 次比较。

分析过比较之后,再来看看交换。

如果数组不只是随机打乱,而是完全反序,在这种最坏的情况下,每次比较过后都得进行一次交换。因此N个元素需要(N - 1) + (N - 2) + (N - 3) + … + 1 次交换。

那么总共花费的步数为:比较数*交换数,即

[ (N - 1) + (N - 2) + (N - 3) + … + 1 ] * 2

运用数学知识计算可得结果为 N^2/2-N+1/2,保留最高次为N^2

因此描述冒泡排序效率的大 O记法,是 O(N^2)

O(N^2)算法是比较低效的,随着数据量变多,其步数也剧增,如下图所示。

最后一点:O(N^2)也被叫作二次时间


5.二次问题

假设我们现在要写一个函数来检查数组中是否有重复值。

首先想到的可能是这样的循环嵌套:

bool CheakDUP(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
            //有重复值返回true
			if (i != j && arr[i] == arr[j])
			{
				return true;
			}
		}
	}
    //没有返回false
	return false;
}

此函数运用了两层循环进行比较,其中 i 先指向一个数字不动,然后让 j 从开头走到最后并比较以它俩为索引处的值。如果相同就返回 true 。

我们考虑最坏情况,N个元素的数组中的每个元素都俩俩比较过,所花费的步数为 N^2。

此函数所用算法的时间复杂度为O(N^2)

虽然 CheakDup 是我们目前唯一想到的解决方法,但在确定采用之前,应意识到它的 O(N^2 )意味着低效。当遇到低效的算法时,我们都应该花些时间思考下有没有更快的做法。特别是当数据量巨大的时候,优化不足的应用甚至可能会突然挂掉。尽管这可能已经是最佳方案,但你还是要确认一下。


6.线性解决

以下是 CheakDup 的另一种实现,它没有嵌套循环。看看它是否会比之前的更加高效。

bool CheakDUP(int arr[], int n, int MAX)
{
	int existingnums[MAX] = { 0 };//MAX为数组中最大的值;将数组初始化为0
	for (int i = 0; i < n; i++)
	{
		if (existingnums[arr[i]] == 0)//如果该位置为0,则说明此处此索引所对应的数字并未重复
		{
			existingnums[arr[i]] = 1; //将0改为1做为标记
		}
		else  //若该索引处的值不为0,则说明之前已被标记。即意味着有重复值
		{
			return true;
		}
	}
	return false;
}

此次我们只用了一层循环便解决了问题。其原理为,以原数组arr中的值为新数组existingnums的索引,并通过该索引将该索引处的值改为1,也就是标记此处已被占用。

若下一次又通过新的索引找到了该位置,并且发现该位置已被标记(指0变为1)那么就意味着该索引为重复值。

同样的,最坏的情况就是无重复,因为你得跑完整个循环才能发现。可见 N 个元素就要 N 次比较。因为这里只有一个循环,数组有多少个元素,它就要迭代多少次。

因此其大 O记法是 O(N)

我们知道 O(N)远远快于 O(N^2 ),所以采用第二种算法能极大地提升 CheakDup的效率。如果这个程序处理的数据量很大,那么性能差别是很明显的(其实第二种算法有一个缺点,不过我们在最后一章才会讲到)。


7.总结

毫无疑问,熟悉大 O记法能使我们发现低效的代码,有助于我们挑选出更快的算法。然而,偶尔也会有两种算法的大 O相同,但实际上二者快慢不一的情况。下一章我们就来学习当大 O记法太过粗略的时候,如何识别两种算法的效率高低。

本章完! 


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。