1
00:00:00,000 --> 00:00:02,826
>> [音樂播放]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> 道格·勞埃德：所以插入排序是另一種
算法，我們可以用它來一個數組排序。

4
00:00:09,370 --> 00:00:12,350
這種算法背後的想法
是建立你排序的數組

5
00:00:12,350 --> 00:00:19,670
到位，換擋元件出
因為你走的路，以騰出空間。

6
00:00:19,670 --> 00:00:22,240
這是稍有不同
從選擇排序或冒泡

7
00:00:22,240 --> 00:00:25,460
排序，例如，其中
我們調整了位置，

8
00:00:25,460 --> 00:00:26,910
我們正在做掉期交易。

9
00:00:26,910 --> 00:00:29,760
>> 在這種情況下，我們實際上正在
做的是滑動元件

10
00:00:29,760 --> 00:00:31,390
過，閃開。

11
00:00:31,390 --> 00:00:34,030
請問這個算法
在偽代碼工作？

12
00:00:34,030 --> 00:00:37,646
那麼就讓我們武斷地說，
該陣列的第一個元素是排序。

13
00:00:37,646 --> 00:00:38,770
我們正在建設到位。

14
00:00:38,770 --> 00:00:42,660
>> 我們會在一個時間去一個因素，
構建它，所以第一件事，我們看到

15
00:00:42,660 --> 00:00:43,890
是一個元件陣列。

16
00:00:43,890 --> 00:00:47,720
根據定義，一個一
元件陣列排序。

17
00:00:47,720 --> 00:00:50,850
>> 然後，我們會重複這個過程until--
我們會重複以下過程

18
00:00:50,850 --> 00:00:52,900
直到所有的元素進行排序。

19
00:00:52,900 --> 00:00:57,770
看看下一個未排序的元素，
將其插入到排序部，

20
00:00:57,770 --> 00:01:01,209
通過移位所需數量的
元素的出路。

21
00:01:01,209 --> 00:01:03,750
希望這個可視化
將幫助您看看到底是什麼

22
00:01:03,750 --> 00:01:05,980
與插入排序怎麼回事。

23
00:01:05,980 --> 00:01:08,010
>> 如此反复，這是我們的
整個排序的數組，

24
00:01:08,010 --> 00:01:10,970
所有元素的表示為紅色。

25
00:01:10,970 --> 00:01:13,320
而讓我們跟隨
步驟我們的偽代碼。

26
00:01:13,320 --> 00:01:16,970
我們做的第一件事，就是我們所說的
該陣列的第一個元素，排序。

27
00:01:16,970 --> 00:01:20,920
所以，我們只是會說
五，你現在來分類的。

28
00:01:20,920 --> 00:01:24,570
>> 然後我們來看下
陣列的未分類的元素

29
00:01:24,570 --> 00:01:27,610
我們要插入
進入排序的部分，

30
00:01:27,610 --> 00:01:29,750
通過移動元素了。

31
00:01:29,750 --> 00:01:33,470
所以2是下一個未排序
數組的元素。

32
00:01:33,470 --> 00:01:36,250
顯然，前所屬
五，所以我們是怎麼做

33
00:01:36,250 --> 00:01:41,580
是那種舉行兩場預留第二，
移5以上，然後插入兩個

34
00:01:41,580 --> 00:01:43,210
前五位，哪裡應該去。

35
00:01:43,210 --> 00:01:45,280
現在，我們可以說，二是排序。

36
00:01:45,280 --> 00:01:48,400
>> 因此，大家可以看到，我們只是到目前為止
看著陣列的兩個元素。

37
00:01:48,400 --> 00:01:50,600
我們還沒有看的
休息可言，但我們已經

38
00:01:50,600 --> 00:01:54,582
得到了這兩個因素排序
變速機構的方式。

39
00:01:54,582 --> 00:01:56,410
>> 因此，我們再次重複這個過程。

40
00:01:56,410 --> 00:01:58,850
看看接下來的無序
元素，這是之一。

41
00:01:58,850 --> 00:02:04,010
我們認為，預留第二，
轉變所做的一切，並把一隻

42
00:02:04,010 --> 00:02:05,570
它應該去。

43
00:02:05,570 --> 00:02:08,110
>> 同樣，還是，我們只是不斷
看了一，二，五。

44
00:02:08,110 --> 00:02:12,480
我們不知道還有什麼是未來，
但我們已經分類的這三個要素。

45
00:02:12,480 --> 00:02:16,030
>> 接下來排序的元素
三，因此我們將其放在一邊。

46
00:02:16,030 --> 00:02:18,200
我們將通過轉移我們
需要向其中，這個時間

47
00:02:18,200 --> 00:02:21,820
是不是一切如前
兩種情況下，它只是五。

48
00:02:21,820 --> 00:02:25,440
然後，我們將堅持三，
兩者之間的和五個。

49
00:02:25,440 --> 00:02:27,849
>> 六是下一個未排序
元件到陣列。

50
00:02:27,849 --> 00:02:31,140
而事實上6大於5，所以
我們甚至不需要做任何交換。

51
00:02:31,140 --> 00:02:35,710
我們可以直接釘六個直角三角形上
排序部分的端部。

52
00:02:35,710 --> 00:02:38,270
>> 最後，四是
最後一個未排序的元素。

53
00:02:38,270 --> 00:02:42,060
因此，我們將其放在一邊，轉移了
元素我們需要轉移過來，

54
00:02:42,060 --> 00:02:43,780
然後放四個它屬於的地方。

55
00:02:43,780 --> 00:02:46,400
而現在看，我們已經排序
的所有元素。

56
00:02:46,400 --> 00:02:48,150
與插入通知
排序，我們沒有

57
00:02:48,150 --> 00:02:50,240
去來回跨越陣列。

58
00:02:50,240 --> 00:02:54,720
我們只去了整個陣列
有一次，我們轉向事物

59
00:02:54,720 --> 00:02:59,870
那我們就已經遇到，為了
以騰出空間給新的元素。

60
00:02:59,870 --> 00:03:02,820
>> 那麼什麼是最壞的情況下
場景與插入排序？

61
00:03:02,820 --> 00:03:05,090
在最壞的情況下，該
陣列是相反的順序。

62
00:03:05,090 --> 00:03:11,180
你必須改為每個n個元素
最多n個位置，每一次我們

63
00:03:11,180 --> 00:03:12,880
使插入。

64
00:03:12,880 --> 00:03:15,720
這是一個很大的轉變。

65
00:03:15,720 --> 00:03:18,014
>> 在最好的情況下，
數組是完全排序。

66
00:03:18,014 --> 00:03:20,680
而有點像發生了什麼
與在實施例5和6，

67
00:03:20,680 --> 00:03:23,779
在這裡，我們可以只把它釘住
無需做任何轉換，

68
00:03:23,779 --> 00:03:24,820
我們會基本上做到這一點。

69
00:03:24,820 --> 00:03:27,560
>> 如果你想像我們
數組是一至六，

70
00:03:27,560 --> 00:03:29,900
我們會通過開始
聲明一個排序。

71
00:03:29,900 --> 00:03:33,300
二來一前一後，所以我們可以只
說好，還有一個和兩個排序。

72
00:03:33,300 --> 00:03:36,190
三，三生經過兩次的話，OK，
一個，兩個和三個排序。

73
00:03:36,190 --> 00:03:39,590
>> 我們沒有做任何掉期，我們
只是移動這一獨斷專行

74
00:03:39,590 --> 00:03:42,460
之間的排序，排序的，因為我們去。

75
00:03:42,460 --> 00:03:46,646
盡可能有效地在我們的例子中那樣，
轉彎元素的藍色，因為我們繼續。

76
00:03:46,646 --> 00:03:48,270
那麼什麼是最壞的情況下運行時，又如何呢？

77
00:03:48,270 --> 00:03:51,854
請記住，如果我們要轉向各
n個元素可能是N個位置，

78
00:03:51,854 --> 00:03:54,020
希望這給你
一個想法，最壞的情況下

79
00:03:54,020 --> 00:03:57,770
運行時間為n的大澳方。

80
00:03:57,770 --> 00:04:00,220
>> 如果數組是完全
排序，所有我們需要做的

81
00:04:00,220 --> 00:04:04,480
是看每一個元素
一次，然後我們就大功告成了。

82
00:04:04,480 --> 00:04:08,440
因此，在最好的情況下，它是n個歐米茄。

83
00:04:08,440 --> 00:04:09,490
>> 我是道格·勞埃德。

84
00:04:09,490 --> 00:04:11,760
這是CS50。

85
00:04:11,760 --> 00:04:13,119