1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Sắp xếp chèn]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Đại học Harvard]

3
00:00:04,240 --> 00:00:07,290
[Đây là CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Chúng ta hãy xem xét sắp xếp chèn, một thuật toán cho một danh sách các số và phân loại chúng.

5
00:00:13,060 --> 00:00:18,300
Một thuật toán, hãy nhớ, chỉ đơn giản là một thủ tục bước từng bước để hoàn thành một nhiệm vụ.

6
00:00:18,300 --> 00:00:23,640
Ý tưởng cơ bản đằng sau sắp xếp chèn, là để phân chia danh sách của chúng tôi thành hai phần,

7
00:00:23,640 --> 00:00:26,580
một phần được sắp xếp và một phần được phân loại.

8
00:00:26,580 --> 00:00:29,290
>> Tại mỗi bước của thuật toán, một số được chuyển

9
00:00:29,290 --> 00:00:32,439
từ phần phân loại phần được sắp xếp

10
00:00:32,439 --> 00:00:35,680
cho đến khi toàn bộ danh sách được sắp xếp.

11
00:00:35,680 --> 00:00:43,340
Dưới đây là danh sách sáu số phân loại 23, 42, 4, 16, 8, và 15.

12
00:00:43,340 --> 00:00:47,680
Kể từ khi những con số này không phải tất cả theo thứ tự tăng dần, họ đang được phân loại.

13
00:00:47,680 --> 00:00:53,890
Vì chúng tôi đã không bắt đầu sắp xếp chưa, chúng tôi sẽ xem xét tất cả sáu yếu tố phần phân loại của chúng tôi.

14
00:00:53,890 --> 00:00:59,270
>> Khi chúng tôi bắt đầu phân loại, chúng tôi sẽ đưa các con số được sắp xếp bên trái trong số này.

15
00:00:59,270 --> 00:01:03,600
Vì vậy, hãy bắt đầu với 23 phần tử đầu tiên trong danh sách của chúng tôi.

16
00:01:03,600 --> 00:01:06,930
Chúng tôi không có bất kỳ yếu tố trong phần sắp xếp của chúng tôi,

17
00:01:06,930 --> 00:01:12,460
vì vậy chúng ta chỉ đơn giản là xem xét 23 là sự khởi đầu và kết thúc phần sắp xếp của chúng tôi.

18
00:01:12,460 --> 00:01:16,510
Bây giờ, phần sắp xếp của chúng tôi có một số, 23,

19
00:01:16,510 --> 00:01:20,260
và phần phân loại của chúng tôi có năm con số này.

20
00:01:20,260 --> 00:01:27,320
Bây giờ chúng ta hãy chèn vào số tiếp theo trong phần phân loại của chúng tôi, 42 tuổi, thành phần được sắp xếp.

21
00:01:27,320 --> 00:01:35,930
>> Để làm như vậy, chúng tôi sẽ cần phải so sánh 42 đến số 23 - yếu tố duy nhất trong phần sắp xếp của chúng tôi cho đến nay.

22
00:01:35,930 --> 00:01:41,980
Bốn mươi hai là lớn hơn 23, vì vậy chúng tôi chỉ đơn giản là có thể phụ thêm 42 đến cuối cùng

23
00:01:41,980 --> 00:01:45,420
của phần sắp xếp danh sách. Great!

24
00:01:45,420 --> 00:01:51,850
Bây giờ là phần của chúng tôi được sắp xếp có hai yếu tố, và phần phân loại của chúng tôi có bốn yếu tố.

25
00:01:51,850 --> 00:01:57,200
Vì vậy, hãy di chuyển cho 4 phần tử tiếp theo trong phần phân loại.

26
00:01:57,200 --> 00:02:00,230
Vì vậy, nơi này nên được đặt trong phần được sắp xếp?

27
00:02:00,230 --> 00:02:04,220
>> Hãy nhớ rằng, chúng tôi muốn đặt con số này theo thứ tự sắp xếp

28
00:02:04,220 --> 00:02:08,680
do đó, phần của chúng tôi được sắp xếp vẫn được sắp xếp đúng ở tất cả các lần.

29
00:02:08,680 --> 00:02:14,380
Nếu chúng ta đặt 4 đến bên phải của số 42, sau đó danh sách của chúng tôi sẽ ra khỏi trật tự.

30
00:02:14,380 --> 00:02:18,380
Vì vậy, chúng ta hãy tiếp tục di chuyển từ phải sang trái trong phần loại của chúng tôi.

31
00:02:18,380 --> 00:02:23,260
Như chúng ta di chuyển, cho phép chuyển từng số xuống một nơi để nhường chỗ cho số điện thoại mới.

32
00:02:25,440 --> 00:02:31,740
Được rồi, 4 cũng là ít hơn 23, vì vậy chúng tôi không thể đặt nó ở đây cả.

33
00:02:31,740 --> 00:02:34,480
Hãy di chuyển 23 phải một nơi.

34
00:02:36,500 --> 00:02:43,120
>> Điều đó có nghĩa là chúng tôi muốn đặt 4 vào khe đầu tiên trong phần được sắp xếp.

35
00:02:43,120 --> 00:02:46,300
Chú ý không gian này trong danh sách đã trống rỗng,

36
00:02:46,300 --> 00:02:51,120
bởi vì chúng tôi đã di chuyển các yếu tố được sắp xếp như chúng ta đã gặp phải.

37
00:02:51,120 --> 00:02:52,740
Được rồi. Vì vậy, chúng tôi đang nằm ở đó.

38
00:02:52,740 --> 00:02:57,990
Hãy tiếp tục thuật toán của chúng tôi bằng cách chèn thêm số 16 vào phần được sắp xếp.

39
00:02:59,260 --> 00:03:03,820
Mười sáu là ít hơn 42, vì vậy hãy thay đổi số 42 bên phải.

40
00:03:05,700 --> 00:03:10,190
Mười sáu cũng là ít hơn 23, vì vậy chúng ta hãy cũng thay đổi yếu tố đó.

41
00:03:11,790 --> 00:03:20,820
>> Bây giờ, 16 là lớn hơn 4. Vì vậy, có vẻ như chúng tôi muốn để chèn 16 giữa 4 và 23.

42
00:03:20,820 --> 00:03:24,620
Trong khi di chuyển qua phần sắp xếp danh sách từ phải sang trái,

43
00:03:24,620 --> 00:03:29,160
4 là số đầu tiên chúng ta đã thấy đó là nhỏ hơn so với số lượng

44
00:03:29,160 --> 00:03:31,540
chúng tôi đang cố gắng để chèn.

45
00:03:31,540 --> 00:03:35,820
Vì vậy, bây giờ chúng ta có thể chèn số 16 vào khe trống này,

46
00:03:35,820 --> 00:03:40,520
hãy nhớ rằng, chúng tôi đã tạo ra bởi các yếu tố di chuyển trong phần sắp xếp trên

47
00:03:40,520 --> 00:03:43,340
như chúng ta đã gặp phải.

48
00:03:43,340 --> 00:03:47,900
>> Được rồi. Bây giờ, chúng tôi có bốn yếu tố được sắp xếp và hai yếu tố được phân loại.

49
00:03:47,900 --> 00:03:51,600
Vì vậy, chúng ta hãy di chuyển 8 thành phần được sắp xếp.

50
00:03:51,600 --> 00:03:55,010
Tám là ít hơn 42.

51
00:03:55,010 --> 00:03:56,940
Tám là dưới 23.

52
00:03:56,940 --> 00:04:00,230
Và 8 là ít hơn 16.

53
00:04:00,230 --> 00:04:03,110
Nhưng 8 là lớn hơn 4.

54
00:04:03,110 --> 00:04:07,280
Vì vậy, chúng tôi muốn để chèn 8 giữa 4 và 16.

55
00:04:09,070 --> 00:04:13,650
Và bây giờ chúng tôi chỉ cần có một trong những yếu tố còn lại để sắp xếp trong 15.

56
00:04:13,950 --> 00:04:16,589
Mười lăm là ít hơn 42,

57
00:04:16,589 --> 00:04:19,130
Mười lăm là ít hơn 23.

58
00:04:19,130 --> 00:04:21,750
Và 15 là dưới 16.

59
00:04:21,750 --> 00:04:24,810
Nhưng 15 là lớn hơn 8.

60
00:04:24,810 --> 00:04:27,440
>> Vì vậy, đây là nơi chúng ta muốn làm cho chèn cuối cùng của chúng tôi.

61
00:04:28,770 --> 00:04:30,330
Và chúng tôi đang làm.

62
00:04:30,330 --> 00:04:33,540
Chúng tôi không có yếu tố hơn trong phần phân loại,

63
00:04:33,540 --> 00:04:36,670
và một phần của chúng tôi được sắp xếp theo thứ tự đúng.

64
00:04:36,670 --> 00:04:40,270
Các con số được sắp xếp từ nhỏ đến lớn.

65
00:04:40,270 --> 00:04:44,330
Vì vậy, chúng ta hãy có một cái nhìn tại một số mã giả mô tả các bước chúng tôi chỉ cần thực hiện.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, chúng ta có thể thấy rằng chúng tôi sẽ cần để lặp qua mỗi phần tử trong danh sách

67
00:04:51,740 --> 00:04:57,060
ngoại trừ lần đầu tiên, kể từ khi các yếu tố đầu tiên trong phần phân loại chỉ đơn giản là sẽ trở thành

68
00:04:57,060 --> 00:05:00,220
phần tử đầu tiên trong phần được sắp xếp.

69
00:05:00,220 --> 00:05:06,320
Trên dòng 2 và 3, chúng tôi đang theo dõi vị trí hiện tại của chúng tôi trong phần phân loại.

70
00:05:06,320 --> 00:05:10,450
Yếu tố đại diện cho số chúng tôi đang di chuyển vào phần được sắp xếp,

71
00:05:10,450 --> 00:05:15,600
và j đại diện cho chỉ mục của chúng tôi vào phần phân loại.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, chúng ta đang lặp lại thông qua phần được sắp xếp từ phải sang trái.

73
00:05:20,980 --> 00:05:26,010
Chúng tôi muốn dừng lại lặp lại một lần một phần tử bên trái của vị trí hiện tại của chúng tôi

74
00:05:26,010 --> 00:05:30,050
ít hơn so với các yếu tố mà chúng tôi đang cố gắng để chèn.

75
00:05:30,050 --> 00:05:35,600
Trên dong 5, chúng ta đang chuyển mỗi yếu tố chúng ta bắt gặp một không gian bên phải.

76
00:05:35,600 --> 00:05:40,950
Bằng cách đó, chúng tôi sẽ có một không gian rõ ràng để chèn vào khi chúng ta tìm thấy những yếu tố đầu tiên

77
00:05:40,950 --> 00:05:44,080
ít hơn so với các yếu tố mà chúng tôi đang di chuyển.

78
00:05:44,080 --> 00:05:50,800
On line 6, chúng tôi cập nhật truy cập của chúng tôi để tiếp tục di chuyển trái qua phần được sắp xếp.

79
00:05:50,800 --> 00:05:56,860
Cuối cùng, trên dòng 7, chúng tôi đang chèn các phần tử vào phần sắp xếp danh sách.

80
00:05:56,860 --> 00:06:00,020
>> Chúng tôi biết rằng nó được chèn vào vị trí j,

81
00:06:00,020 --> 00:06:05,360
bởi vì chúng tôi đã chuyển các yếu tố đó được sử dụng để có được một không gian bên phải.

82
00:06:05,360 --> 00:06:09,460
Hãy nhớ rằng, chúng tôi đang di chuyển qua phần sắp xếp từ phải sang trái,

83
00:06:09,460 --> 00:06:13,960
nhưng chúng tôi đang di chuyển qua phần được phân loại từ trái sang phải.

84
00:06:13,960 --> 00:06:19,090
Được rồi. Bây giờ chúng ta hãy có một cái nhìn bao lâu chạy rằng thuật toán mất.

85
00:06:19,090 --> 00:06:25,300
Đầu tiên chúng ta sẽ đặt câu hỏi như thế nào lâu cho thuật toán này để chạy trong trường hợp xấu nhất.

86
00:06:25,300 --> 00:06:29,040
Nhớ lại rằng chúng tôi đại diện cho thời gian chạy này với ký hiệu O Big.

87
00:06:32,530 --> 00:06:38,500
Để sắp xếp danh sách của chúng tôi, chúng tôi đã để lặp lại trên các yếu tố trong phần phân loại,

88
00:06:38,500 --> 00:06:43,430
và cho mỗi người trong số những yếu tố đó, có khả năng trên tất cả các yếu tố trong phần được sắp xếp.

89
00:06:43,430 --> 00:06:47,950
Trực giác, điều này nghe giống như một hoạt động O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Nhìn giả của chúng tôi, chúng tôi có một vòng lặp lồng nhau bên trong vòng lặp khác,

91
00:06:51,840 --> 00:06:55,290
, quả thật vậy, âm thanh như một hoạt động O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Tuy nhiên, phần sắp xếp danh sách không chứa toàn bộ danh sách cho đến phút cuối.

93
00:07:01,590 --> 00:07:06,920
Tuy nhiên, chúng tôi có thể có khả năng chèn một phần tử mới vào đầu của phần được sắp xếp

94
00:07:06,920 --> 00:07:09,320
trên mỗi lần lặp của thuật toán,

95
00:07:09,320 --> 00:07:14,500
điều này có nghĩa là chúng ta phải nhìn vào mỗi phần tử hiện đang trong phần được sắp xếp.

96
00:07:14,500 --> 00:07:20,090
Vì vậy, điều đó có nghĩa là chúng tôi có thể có khả năng làm cho một so sánh các yếu tố thứ hai,

97
00:07:20,090 --> 00:07:24,660
hai so sánh các yếu tố thứ ba, và như vậy.

98
00:07:24,660 --> 00:07:32,480
Vì vậy, tổng số của bước là tổng của các số nguyên từ 1 đến chiều dài của danh sách trừ đi 1.

99
00:07:32,480 --> 00:07:35,240
Chúng tôi có thể đại diện cho điều này với một tổng kết.

100
00:07:41,170 --> 00:07:47,270
>> Chúng tôi sẽ không đi vào summations ở đây, nhưng nó quay ra rằng tổng kết này là bằng

101
00:07:47,270 --> 00:07:57,900
n (n - 1) trên 2, tương đương với n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Khi nói về thời gian chạy tiệm cận,

103
00:08:00,800 --> 00:08:05,170
này n ^ 2 hạn sẽ chi phối hạn n.

104
00:08:05,170 --> 00:08:11,430
Vì vậy, chèn sắp xếp là Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Điều gì sẽ xảy ra nếu chúng ta chạy sắp xếp chèn vào một danh sách đã được sắp xếp.

106
00:08:16,150 --> 00:08:20,960
Trong trường hợp đó, chúng tôi chỉ đơn giản là muốn xây dựng phần được sắp xếp từ trái sang phải.

107
00:08:20,960 --> 00:08:25,050
Vì vậy, chúng tôi chỉ cần về trình tự các bước n.

108
00:08:25,050 --> 00:08:29,740
>> Điều đó có nghĩa là chèn loại có hiệu suất tốt nhất của n,

109
00:08:29,740 --> 00:08:34,130
mà chúng tôi đại diện với Ω (n).

110
00:08:34,130 --> 00:08:36,190
Và đó là nó sắp xếp chèn,

111
00:08:36,190 --> 00:08:40,429
chỉ là một trong rất nhiều các thuật toán chúng ta có thể sử dụng để sắp xếp một danh sách.

112
00:08:40,429 --> 00:08:43,210
Tên tôi là Tommy, và điều này là CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, bạn không thể dừng lại một khi nó bắt đầu.

115
00:09:01,620 --> 00:09:04,760
Ồ, chúng tôi đã làm điều đó - >> Boom!