1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
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