本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。
本章内容
写在前面
1.冒泡排序
2.冒泡排序实战
3.冒泡排序的实现
4.冒泡排序的效率
5.二次问题
6.线性解决
7.总结
大 O记法能客观地衡量各种算法的时间复杂度,是比较算法的利器。我们也试过用它来对比二分查找和线性查找的步数差异,发现二分查找的步数为 O(log N),比线性查找的 O(N)快得多。
然而,写代码的时候并不总有这样明确的二选一,更多时候你可能就直接采用首先想到的那种算法了。不过有了大 O的话,你就可以与其他常用的算法比较,然后问自己:“我的算法跟它们相比,是快还是慢?”
如果你通过大 O 发现自己的算法比其他的要慢,你就应该退一步,好好想想怎样优化它,才能使它变成更快的那种大 O。
本章我们会写些代码来解决一个实际问题,并且会用大 O 来测量算法的性能,然后看看是否能对算法做些修改,使得性能提升。
排序算法是计算机科学中被广泛研究的一个课题。历时多年,它发展出了数十种算法,这些算法都着眼于一个问题:
如何将一个无序的数字数组整理成升序?
冒泡排序是一种很基本的排序算法,步骤如下。
(1) 指向数组中两个相邻的元素(最开始是数组的头两个元素),比较它们的大小。
(2) 如果它们的顺序错了(即左边的值大于右边),就互换位置。
如果顺序已经是正确的,那这一步就什么都不用做。
(3) 将两个指针右移一格。
重复第(1)步和第(2)步,直至指针到达数组末尾。
(4)重复第(1)至(3)步,直至从头到尾都无须再做交换,这时数组就排好序了
这里被重复的第(1)至(3)步是一个轮回,也就是说,这个算法的主要步骤被“轮回”执行直到整个数组的顺序正确。
下面来举一个完整的例子。假设要对 [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。
顺序正确,不用交换。而且剩下的元素也都排好序了,轮回结束。
因为刚才的轮回没有任何交换,可知整个数组都已排好序。
以下是用 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 内层循环由j来控制,进行的是一次轮回中,把一个数“冒”到正确的位置上。 此处的代码就是对上一小节冒泡排序实战的翻译。 冒泡排序的执行步骤可分为两种。 比较:比较两个数看哪个更大。 交换:交换两个数的位置以使它们按顺序排列。 先看看冒泡排序要进行多少次比较。 回顾之前那个 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)也被叫作二次时间。 假设我们现在要写一个函数来检查数组中是否有重复值。 首先想到的可能是这样的循环嵌套: 此函数运用了两层循环进行比较,其中 i 先指向一个数字不动,然后让 j 从开头走到最后并比较以它俩为索引处的值。如果相同就返回 true 。 我们考虑最坏情况,N个元素的数组中的每个元素都俩俩比较过,所花费的步数为 N^2。 此函数所用算法的时间复杂度为O(N^2)。 虽然 CheakDup 是我们目前唯一想到的解决方法,但在确定采用之前,应意识到它的 O(N^2 )意味着低效。当遇到低效的算法时,我们都应该花些时间思考下有没有更快的做法。特别是当数据量巨大的时候,优化不足的应用甚至可能会突然挂掉。尽管这可能已经是最佳方案,但你还是要确认一下。 以下是 CheakDup 的另一种实现,它没有嵌套循环。看看它是否会比之前的更加高效。 此次我们只用了一层循环便解决了问题。其原理为,以原数组arr中的值为新数组existingnums的索引,并通过该索引将该索引处的值改为1,也就是标记此处已被占用。 若下一次又通过新的索引找到了该位置,并且发现该位置已被标记(指0变为1)那么就意味着该索引为重复值。 同样的,最坏的情况就是无重复,因为你得跑完整个循环才能发现。可见 N 个元素就要 N 次比较。因为这里只有一个循环,数组有多少个元素,它就要迭代多少次。 因此其大 O记法是 O(N)。 我们知道 O(N)远远快于 O(N^2 ),所以采用第二种算法能极大地提升 CheakDup的效率。如果这个程序处理的数据量很大,那么性能差别是很明显的(其实第二种算法有一个缺点,不过我们在最后一章才会讲到)。 毫无疑问,熟悉大 O记法能使我们发现低效的代码,有助于我们挑选出更快的算法。然而,偶尔也会有两种算法的大 O相同,但实际上二者快慢不一的情况。下一章我们就来学习当大 O记法太过粗略的时候,如何识别两种算法的效率高低。 本章完! 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
4.冒泡排序的效率
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;
}
6.线性解决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;
}
7.总结
当前文章:运用大O来给代码提速(冒泡排序)-创新互联
URL地址:http://bjjierui.cn/article/csgeji.html