1 00:00:00,000 --> 00:00:03,360 >> [音乐播放] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD:好吧,所以 冒泡排序是一种算法 4 00:00:06,730 --> 00:00:08,730 你可以用它来进行排序一组元素。 5 00:00:08,730 --> 00:00:10,850 让我们来看看它是如何工作的。 6 00:00:10,850 --> 00:00:13,240 >> 这样的基本思想后面 冒泡排序是这样的。 7 00:00:13,240 --> 00:00:17,340 我们一般要走高 值元素通常到右侧, 8 00:00:17,340 --> 00:00:20,340 和一般较低值元素 到左侧,如我们所期望的。 9 00:00:20,340 --> 00:00:23,256 我们要下的东西是在 开始时,具有较高的事 10 00:00:23,256 --> 00:00:24,970 是在末端。 11 00:00:24,970 --> 00:00:26,130 >> 我们是如何做到这一点? 12 00:00:26,130 --> 00:00:28,040 那么在伪代码, 我们可以说,我们的 13 00:00:28,040 --> 00:00:30,320 设置一个交换计数器为非零值。 14 00:00:30,320 --> 00:00:32,570 我们将看到,为什么我们这样做,在第二。 15 00:00:32,570 --> 00:00:36,090 随后,我们重复以下 过程,直到交换计数为0, 16 00:00:36,090 --> 00:00:39,910 或者直到我们不掉的。 17 00:00:39,910 --> 00:00:43,170 >> 重置互换计数器 0,如果它不是已经0。 18 00:00:43,170 --> 00:00:46,420 然后看每 相邻的一对元件。 19 00:00:46,420 --> 00:00:49,550 如果这两个因素是 不是为了,交换它们, 20 00:00:49,550 --> 00:00:51,620 加1到交换柜台。 21 00:00:51,620 --> 00:00:53,870 如果你正在考虑 这个你想象它之前, 22 00:00:53,870 --> 00:00:57,471 注意到,这将移动下 值元素向左 23 00:00:57,471 --> 00:01:00,720 和更高的值元素到右侧, 有效地做我们想做的事情, 24 00:01:00,720 --> 00:01:03,940 这是将这些团体 在该方式的元件。 25 00:01:03,940 --> 00:01:07,035 让我们直观地了解本 看起来使用我们的数组 26 00:01:07,035 --> 00:01:10,504 我们用来测试 这些算法。 27 00:01:10,504 --> 00:01:13,420 我们有一个排序的数组在这里再次, 通过所有的元素表示 28 00:01:13,420 --> 00:01:14,840 是红色。 29 00:01:14,840 --> 00:01:17,970 我把我交换反 为非零值。 30 00:01:17,970 --> 00:01:20,610 我随意选择 负1--这不是0。 31 00:01:20,610 --> 00:01:23,840 我们想重复这个过程 直到交换计数器为0。 32 00:01:23,840 --> 00:01:26,540 这就是为什么我把我交换 计数器到一些非零值, 33 00:01:26,540 --> 00:01:29,400 因为否则 交换计数器将是0。 34 00:01:29,400 --> 00:01:31,610 我们甚至不会开始 算法的过程。 35 00:01:31,610 --> 00:01:33,610 如此反复,步骤are-- 复位交换计数器 36 00:01:33,610 --> 00:01:37,900 为0,再看看每个相邻 对,如果他们不按顺序, 37 00:01:37,900 --> 00:01:40,514 交换它们,并添加1 到交换柜台。 38 00:01:40,514 --> 00:01:41,680 因此,让我们开始这个过程。 39 00:01:41,680 --> 00:01:44,430 所以我们要做的第一件事就是 我们设置交换计数器为0, 40 00:01:44,430 --> 00:01:46,660 然后我们开始寻找 在每个相邻的一对。 41 00:01:46,660 --> 00:01:49,140 >> 所以,我们首先开始看5和2。 42 00:01:49,140 --> 00:01:52,410 我们看到,他们是出 订货所以我们交换它们。 43 00:01:52,410 --> 00:01:53,830 我们增加1到交换柜台。 44 00:01:53,830 --> 00:01:57,860 所以,现在我们交换计数器1, 和2和5已经被切换。 45 00:01:57,860 --> 00:01:59,370 现在,我们再次重复这个过程。 46 00:01:59,370 --> 00:02:03,540 >> 我们期待下一个相邻的一对, 5 1--他们也失灵, 47 00:02:03,540 --> 00:02:06,960 所以我们交换他们并添加 1到交换柜台。 48 00:02:06,960 --> 00:02:08,900 然后我们来看看5和3。 49 00:02:08,900 --> 00:02:13,830 他们是失灵的,所以我们交换 他们和我们添加1到交换柜台。 50 00:02:13,830 --> 00:02:15,550 然后我们来看看5和6。 51 00:02:15,550 --> 00:02:18,630 他们是为了,所以我们实际上并不 这需要时间来交换任何东西。 52 00:02:18,630 --> 00:02:20,250 然后我们来看看6和4。 53 00:02:20,250 --> 00:02:24,920 他们还坏了,所以我们交换 他们和我们添加1到交换柜台。 54 00:02:24,920 --> 00:02:26,230 >> 现在可以看到发生了什么事。 55 00:02:26,230 --> 00:02:29,514 我们已经搬到6一直到结束。 56 00:02:29,514 --> 00:02:32,180 因此,在选择排序,如果你 看到视频,我们所做的是 57 00:02:32,180 --> 00:02:35,290 我们结束了移动 建筑最小元素 58 00:02:35,290 --> 00:02:39,640 数组排序基本上是从 从左到右,最小到最大。 59 00:02:39,640 --> 00:02:43,200 在冒泡排序的情况下,如果我们 下面这个特殊的算法, 60 00:02:43,200 --> 00:02:46,720 我们实际上将要建设 从右侧的排序的数组 61 00:02:46,720 --> 00:02:49,100 到左,从最大到最小。 62 00:02:49,100 --> 00:02:53,840 我们已经有效地冒泡6, 最大值,一直到结束。 63 00:02:53,840 --> 00:02:56,165 >> 因此,我们现在可以宣布 这是排序, 64 00:02:56,165 --> 00:02:59,130 和未来iterations-- 经过阵列again-- 65 00:02:59,130 --> 00:03:01,280 我们不必考虑6了。 66 00:03:01,280 --> 00:03:03,850 我们只需要考虑 未排序的元素 67 00:03:03,850 --> 00:03:06,299 当我们正在寻找相邻的一对。 68 00:03:06,299 --> 00:03:08,340 因此,我们已完成一个 通过冒泡排序。 69 00:03:08,340 --> 00:03:11,941 所以,现在我们回到正题, 重复,直到交换计数器为0。 70 00:03:11,941 --> 00:03:13,690 那么交换计数器 是4,所以我们要 71 00:03:13,690 --> 00:03:15,410 保持再重复这个过程。 72 00:03:15,410 --> 00:03:19,180 >> 我们要重新交换计数器 为0,并期待在各相邻对。 73 00:03:19,180 --> 00:03:21,890 因此,我们开始与2 1--他们 坏了,所以我们交换他们 74 00:03:21,890 --> 00:03:23,620 我们增加1到交换柜台。 75 00:03:23,620 --> 00:03:25,490 2和3,他们在秩序。 76 00:03:25,490 --> 00:03:27,060 我们不需要做任何事情。 77 00:03:27,060 --> 00:03:28,420 3和5是在顺序。 78 00:03:28,420 --> 00:03:30,150 我们不需要做任何事情在那里。 79 00:03:30,150 --> 00:03:32,515 >> 5和4,它们是从 秩序,因此我们 80 00:03:32,515 --> 00:03:35,130 需要调换并添加 1到交换柜台。 81 00:03:35,130 --> 00:03:38,880 而现在我们已经搬到5, 下一个最大的元素, 82 00:03:38,880 --> 00:03:40,920 到未排序部分的端部。 83 00:03:40,920 --> 00:03:44,360 所以,我们现在可以称之为 排序部的一部分。 84 00:03:44,360 --> 00:03:47,180 >> 现在你在看 屏幕大概可以告诉, 85 00:03:47,180 --> 00:03:50,130 因为我可以,该阵列 排序现在。 86 00:03:50,130 --> 00:03:51,820 但是,我们不能证明呢。 87 00:03:51,820 --> 00:03:54,359 我们没有担保 ,它的排序。 88 00:03:54,359 --> 00:03:56,900 但是,这是交换 计数器将开始发挥作用。 89 00:03:56,900 --> 00:03:59,060 >> 因此,我们已经完成了一通。 90 00:03:59,060 --> 00:04:00,357 交换计数器2。 91 00:04:00,357 --> 00:04:02,190 所以,我们要重复 这一过程中再次, 92 00:04:02,190 --> 00:04:04,290 重复,直到交换计数器为0。 93 00:04:04,290 --> 00:04:05,550 重置互换计数器为0。 94 00:04:05,550 --> 00:04:06,820 因此,我们将重新设置。 95 00:04:06,820 --> 00:04:09,810 >> 现在看每一对相邻。 96 00:04:09,810 --> 00:04:11,880 这是为了,1和2。 97 00:04:11,880 --> 00:04:13,590 2和3是为了。 98 00:04:13,590 --> 00:04:15,010 3和4是为了。 99 00:04:15,010 --> 00:04:19,250 所以在这一点上,注意到我们已经完成 看着每对相邻, 100 00:04:19,250 --> 00:04:22,530 但交换柜台仍是0。 101 00:04:22,530 --> 00:04:25,520 >> 如果我们没有切换 的任何元件,则它们 102 00:04:25,520 --> 00:04:28,340 必须按顺序,由 凭借这个过程。 103 00:04:28,340 --> 00:04:32,000 于是各种各样的效率, 我们的计算机科学家喜欢, 104 00:04:32,000 --> 00:04:35,560 是我们现在可以宣布 整个数组必须 105 00:04:35,560 --> 00:04:38,160 进行排序,因为我们没有 要交换的任何元素。 106 00:04:38,160 --> 00:04:40,380 这是相当不错的。 107 00:04:40,380 --> 00:04:43,260 >> 那么什么是最坏的情况下 场景与冒泡排序? 108 00:04:43,260 --> 00:04:46,240 在最坏的情况下,阵列是 在完全相反的顺序, 109 00:04:46,240 --> 00:04:49,870 所以我们要泡每个 大元素的所有 110 00:04:49,870 --> 00:04:51,780 跨越阵列的方式。 111 00:04:51,780 --> 00:04:55,350 我们有效地也有 泡泡所有的小元素后面 112 00:04:55,350 --> 00:04:57,050 在阵列一路,太。 113 00:04:57,050 --> 00:05:01,950 因此,每个n个元件具有移动 在所有其他的n个元素。 114 00:05:01,950 --> 00:05:04,102 所以这是最坏的情况。 115 00:05:04,102 --> 00:05:05,810 在最好的情况下, 场景虽然,这是 116 00:05:05,810 --> 00:05:07,880 略有不同的选择排序。 117 00:05:07,880 --> 00:05:10,040 该阵列是已经 排序,当我们进去的。 118 00:05:10,040 --> 00:05:12,550 我们没有做任何 掉期交易在第一轮。 119 00:05:12,550 --> 00:05:14,940 所以,我们不妨来看看 在较少的元素,对不对? 120 00:05:14,940 --> 00:05:18,580 我们并不需要重复此 过处理的次数。 121 00:05:18,580 --> 00:05:19,540 >> 那么,是什么意思呢? 122 00:05:19,540 --> 00:05:22,390 那么什么是最坏的情况下 对于冒泡排序,这有什么 123 00:05:22,390 --> 00:05:25,330 在最好的情况下进行冒泡排序? 124 00:05:25,330 --> 00:05:27,770 你猜呢? 125 00:05:27,770 --> 00:05:32,420 在最坏的情况下,你必须遍历 在所有的n个元素n次。 126 00:05:32,420 --> 00:05:34,220 因此,最坏的情况下为n的平方。 127 00:05:34,220 --> 00:05:36,550 >> 如果数组是完全 虽然排序,你只 128 00:05:36,550 --> 00:05:38,580 来看看每个 的一次的元素。 129 00:05:38,580 --> 00:05:42,670 并且如果交换计数器仍为0, 你可以说这个数组排序。 130 00:05:42,670 --> 00:05:45,780 因此在最好的情况下,这是 实际上比选择好 131 00:05:45,780 --> 00:05:49,230 类别 - 这是为n的欧米茄。 132 00:05:49,230 --> 00:05:50,270 >> 我是道格·劳埃德。 133 00:05:50,270 --> 00:05:52,140 这是CS50。 134 00:05:52,140 --> 00:05:54,382