Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [冒泡排序]
[JACKSON施泰因坎普哈佛商学院]
[这是CS50。 CS50TV]
冒泡排序的排序算法是一个例子 -
也就是说,一个程序的一组中的元素进行排序
升序或降序排列。
例如,如果你想对数组进行排序的数字
[3,5,2,9],冒泡排序的正确执行,将返回
排序的数组[2,3,5,9]以升序排列。
现在,我要解释的伪代码算法是如何工作的。
>> 比方说,我们在排序列表中的5个整数 - 3,2,9,6,5。
该算法开始通过在看的前两个元素,第3和2,
和检查,如果他们是彼此的相对顺序。
它们是 - 图3是大于2。
要在升序,他们应该是周围的其他方式。
因此,我们交换他们。
现在列表看起来像这样:[2,3,9,6,5]。
>> 接下来,我们来看看第二个和第三个,3个和9。
他们彼此相对正确的顺序。
也就是说,图3是小于9,所以该算法不交换它们。
接下来,我们来看看在9日和6。他们的订单。
>> 因此,我们需要更换,因为9大于6。
最后,我们来看看在过去的两个整数,9和5。
他们离开的命令,所以他们必须交换。
在列表中的第一个完整的通过,
它看起来是这样的:[2,3,6,5,9]。
不坏。这几乎排序。
但是,我们需要在列表中,再次得到完全排序。
二是小于3,所以我们不交换。
>> 三是小于6,所以我们不交换。
六是大于5。我们交换。
六是小于9。我们不交换。
第二次通过后,它看起来像这样:[2,3,5,6,9]。完美的。
现在,让我们把它写在伪代码。
基本上,对于列表中的每个元素,我们需要看
直接将其权利和元素。
如果它们是满分为了相对于彼此的 - 也就是说,如果在左边的元素
大于一个在右边 - 我们应该交换这两个元素。
>> 我们这样做的每一个元素的列表,我们已经取得了一个通过。
现在我们需要做的直通足够的时间,以确保清单
是充分,适当的排序。
但是,有多少次,我们必须通过列表
保证我们所做的吗?
好了,最坏的情况是,如果我们有一个完全向后列表。
然后,它需要一个数传递的数目等于
n-1个元素。
如果这样做没有意义的,直观的,想一个简单的例子 - 这样的名单[1]。
>> 这是要采取一个通到正确排序。
[3,2,1] - 最坏的情况是,3个元素排序向后,
这将需要2次迭代进行排序。
一次迭代后,[2,1,3]。
第二个投资收益率排序后的数组[1,2,3]。
所以,你知道,你从来没有去通过阵列,在一般情况,
超过n-1次,其中n是在数组中的元素数。
因为,这就是所谓的冒泡排序的最大元素趋向于“泡沫”
到很快的权利。
事实上,该算法具有非常有趣的现象。
>> 经过m次迭代整个数组,
最右边的m个元素是保证
到他们正确的位置进行排序。
如果你想看到这样的自己,
我们可以尝试在一个完全向后列表[9,6,5,3,2]。
后通过整个列表,
[声音写作]
[6,9,5,3,2],[6,5,9,3,2],[6,5,3,9,2],[6,5,3,2,9]
最右边的元素是在适当的地方。
后的第二个直通,6将具有“鼓泡式'的
右数第二位。
这两个因素将在正确的地方正确的 - 第6和第9 -
经过前两道直通。
>> 那么,如何才能使用优化算法呢?
好了,一个迭代后,通过阵列
我们实际上并不需要检查一下最右边的元素
因为我们知道它的排序。
经过两次迭代,我们知道是肯定的,最右边的两个要素都到位。
所以,在一般情况下,通过充分阵列k次迭代后,
检查最后的k个元素是多余的,因为我们不知道
他们已经在正确的位置。
>> 因此,如果你的n个元素的数组排序,
在第一次迭代 - 你要排序的所有元素 - 第一n-0。
在第二次迭代中,你必须在所有的元素,但最后看 -
第一n-1。
另一种优化,以检查是否已排序的列表
在每次迭代之后。
如果它已经对数组进行排序,我们不需要做任何更多的迭代
通过列表。
如何才能做到这一点呢?
那么,如果我们不作任何掉期上一通通过的名单,
很明显,已经排序的列表,因为我们没有交换什么。
因此,我们绝对没有再次进行排序。
>> 也许你可以初始化一个标志变量,被称为“不排序”
false,然后将其更改为true,如果你要交换的任何元素
通过数组的一个迭代。
同样,一个计数器来计数多少掉期
在任何给定的迭代。
一个迭代结束时,如果你不交换任何元素,
你知道已排序的列表,你就大功告成了。
冒泡排序,像其他的排序算法,可以
调整,其中有一个排序方法中的任何元素。
>> 也就是说,给定两个元素,你有办法说,如果第一个
大于,等于或小于第二个。
例如,你可以说的字母排序
a 冒泡排序绝不是一个非常有效的快速排序算法。
最坏情况下的运行是大O的n²
因为你有n次迭代通过列表
检查所有n个元素,每个传递的N×N = N²。
运行时间是指,作为你排序的元素数量增加,
运行时间的增加,二次。
>> 但是,如果效率是你的程序并不是一个大问题
或者,如果你只是少量的元素进行排序,
您可能会发现冒泡排序有用的,因为
它是一个最简单的排序算法,以了解
和代码。
这也是一个伟大的方式来获得经验与翻译理论
算法转换成实际的功能代码。
嗯,这是给你的冒泡排序。感谢收看。
CS50.TV