1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Hợp nhất Sắp xếp]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden - Đại học Harvard]

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

4
00:00:07,000 --> 00:00:09,000
Hãy nói chuyện về loại hợp nhất.

5
00:00:09,000 --> 00:00:14,000
Vì vậy, đến nay bạn đã nhìn thấy bong bóng loại, sắp xếp chèn và sắp xếp lựa chọn.

6
00:00:14,000 --> 00:00:17,000
Mặc dù tôi sẽ loại sóng tay của tôi vào những gì tôi có nghĩa là tốt hơn,

7
00:00:17,000 --> 00:00:21,000
hợp nhất loại nói chung thực hiện tốt hơn so với bất kỳ của 3 loại.

8
00:00:22,000 --> 00:00:27,000
>> Nhưng trước khi nói về loại hợp nhất, chúng ta hãy nói về việc sáp nhập 2 danh sách được sắp xếp.

9
00:00:27,000 --> 00:00:31,000
Chúng tôi sẽ gọi quá trình lấy 2 danh sách được sắp xếp như thế này,

10
00:00:31,000 --> 00:00:35,000
và thực hiện một danh sách được sắp xếp duy nhất trong số họ - kết hợp các danh sách.

11
00:00:35,000 --> 00:00:37,750
Làm thế nào chúng ta có thể làm điều này?

12
00:00:37,750 --> 00:00:41,290
Vâng, một trong những ý tưởng là chỉ dính một danh sách vào cuối của danh sách khác

13
00:00:41,290 --> 00:00:43,830
và sau đó sắp xếp danh sách kết quả.

14
00:00:43,830 --> 00:00:47,220
>> Trong khi điều này hoạt động, nó rất nhiều công việc không cần thiết.

15
00:00:47,220 --> 00:00:49,900
Chúng tôi có thể làm điều đó nhanh hơn là chỉ sắp xếp.

16
00:00:49,900 --> 00:00:54,100
Chú ý rằng sai một ý tưởng là để chỉ đưa ly xen kẽ từ mỗi danh sách.

17
00:00:54,100 --> 00:00:56,460
Trong khi đó có vẻ như rằng các công trình lần đầu tiên,

18
00:00:56,460 --> 00:01:05,760
làm điều đó chúng tôi kết thúc với 4, 8, 15, 23, 16 - thông báo rằng 16 và 23 ra khỏi vị trí.

19
00:01:05,760 --> 00:01:09,380
Điều này là do 2 yếu tố đó sẽ xuất hiện liên tiếp trong danh sách sáp nhập

20
00:01:09,380 --> 00:01:11,720
đang ở trong cùng một danh sách ban đầu.

21
00:01:11,720 --> 00:01:14,850
Cả hai 15 và 16 trong danh sách bên trái.

22
00:01:14,850 --> 00:01:19,810
Bí quyết là để tận dụng lợi thế của một thực tế rằng cả hai danh sách đã được sắp xếp.

23
00:01:19,810 --> 00:01:23,320
Điều này có nghĩa rằng nếu chúng ta chỉ cần nhìn vào các yếu tố đầu tiên của cả hai danh sách -

24
00:01:23,320 --> 00:01:29,580
ở đây, 4 và 8 - một trong số họ cũng phải có yếu tố đầu tiên của danh sách sáp nhập.

25
00:01:29,580 --> 00:01:31,620
Vâng, tại sao vậy?

26
00:01:31,620 --> 00:01:33,520
Cả hai của các danh sách đã được sắp xếp,

27
00:01:33,520 --> 00:01:38,410
và do đó, hoặc 4 hoặc 8 phải là phần tử nhỏ nhất khi chúng ta kết hợp 2 danh sách.

28
00:01:38,410 --> 00:01:41,770
Trong trường hợp này, nhỏ nhất là 4,

29
00:01:41,770 --> 00:01:46,370
vì vậy chúng tôi có thể đưa ra 4 và làm cho nó là yếu tố đầu tiên của danh sách sáp nhập của chúng tôi.

30
00:01:46,370 --> 00:01:50,710
Bây giờ chúng ta tiếp tục hợp nhất 3 yếu tố còn lại của danh sách đầu tiên

31
00:01:50,710 --> 00:01:52,920
và 4 yếu tố của danh sách thứ hai.

32
00:01:52,920 --> 00:01:57,150
>> Một lần nữa, chúng ta chỉ cần nhìn vào các yếu tố đầu tiên của cả hai danh sách.

33
00:01:57,150 --> 00:02:01,060
Các nhỏ hơn trong 2 phải là yếu tố thứ hai của danh sách sáp nhập của chúng tôi.

34
00:02:01,060 --> 00:02:05,440
Thời gian này, từ 8 đến 15 nhỏ nhất là 8, và vì vậy chúng tôi chèn

35
00:02:05,440 --> 00:02:09,240
như là phần tử thứ hai của danh sách được sắp xếp của chúng tôi.

36
00:02:09,240 --> 00:02:12,180
Chúng tôi có thể tiếp tục so sánh các yếu tố đầu tiên của cả hai danh sách

37
00:02:12,180 --> 00:02:14,420
và loại bỏ nhỏ hơn trong 2.

38
00:02:14,420 --> 00:02:19,460
So sánh 15 và 23, 15 là nhỏ hơn và do đó yếu tố thứ ba của chúng tôi.

39
00:02:21,000 --> 00:02:23,910
Bây giờ so sánh 16 và 23, 16 là nhỏ hơn.

40
00:02:23,910 --> 00:02:26,820
Vì vậy, đó là yếu tố thứ tư.

41
00:02:26,820 --> 00:02:30,390
>> Chú ý rằng 2 yếu tố đến từ cùng một danh sách trong một hàng.

42
00:02:30,390 --> 00:02:34,400
Đây là lý do tại sao danh sách sáp nhập có thể không chỉ thay thế các yếu tố từ 2 danh sách.

43
00:02:34,400 --> 00:02:40,020
So sánh 50 và 23, 23 là nhỏ hơn, do đó, chúng tôi chọn điều đó.

44
00:02:40,770 --> 00:02:44,070
Giữa 50 và 42, 42 là nhỏ hơn.

45
00:02:44,070 --> 00:02:48,290
Từ 50 và 108, 50 là nhỏ hơn.

46
00:02:48,290 --> 00:02:52,330
Và, cuối cùng, chúng tôi chỉ có 108, vì vậy nó phải đi vào cuối danh sách của chúng tôi.

47
00:02:53,750 --> 00:02:56,180
Chú ý rằng chúng tôi có một danh sách, tốt đẹp được sắp xếp.

48
00:02:56,180 --> 00:02:59,040
Mỗi khi chúng ta so sánh 2 yếu tố đầu tiên của 2 danh sách

49
00:02:59,040 --> 00:03:02,730
chúng tôi đã có thể xác định các yếu tố tiếp theo của danh sách sáp nhập.

50
00:03:02,730 --> 00:03:08,070
Điều này có nghĩa rằng nếu danh sách cuối cùng chứa số n, trong đó n ở đây là 8,

51
00:03:08,070 --> 00:03:12,610
sau đó chúng ta cần ở hầu hết các so sánh n để có được tất cả những con số này vào đúng chỗ.

52
00:03:13,230 --> 00:03:16,230
Một thuật toán như vậy được cho là để chạy trong thời gian tuyến tính,

53
00:03:16,230 --> 00:03:18,090
nhưng đừng lo lắng về điều đó ở đây.

54
00:03:18,570 --> 00:03:22,810
>> Sử dụng thuật toán của chúng tôi cho việc sáp nhập, chúng ta có thể thực hiện một thuật toán hợp nhất loại nhanh.

55
00:03:22,810 --> 00:03:25,170
Vì vậy, chúng ta hãy thiết lập lại danh sách của chúng tôi.

56
00:03:35,210 --> 00:03:37,750
Có 2 bước lớn trong quá trình hợp nhất loại.

57
00:03:37,750 --> 00:03:41,500
Thứ nhất, liên tục chia danh sách các cốc vào nửa

58
00:03:41,500 --> 00:03:44,860
cho đến khi chúng tôi có một loạt các danh sách với chỉ 1 chén trong họ.

59
00:03:44,860 --> 00:03:47,350
Đừng lo lắng nếu một danh sách có chứa một số lẻ

60
00:03:47,350 --> 00:03:49,880
và bạn không thể làm cho một cắt hoàn toàn sạch giữa chúng.

61
00:03:49,880 --> 00:03:53,750
Chỉ cần tùy tiện chọn danh sách để bao gồm thêm chén.

62
00:03:53,750 --> 00:03:56,240
Vì vậy, chúng ta hãy phân chia các danh sách này.

63
00:03:58,140 --> 00:04:01,310
Bây giờ chúng tôi có 2 danh sách.

64
00:04:04,120 --> 00:04:06,570
Bây giờ chúng tôi có 4 danh sách.

65
00:04:10,350 --> 00:04:13,870
>> Và bây giờ chúng tôi có 8 danh sách với một ly duy nhất trong mỗi danh sách.

66
00:04:13,870 --> 00:04:16,630
Vì vậy, đó là nó cho bước 1.

67
00:04:16,630 --> 00:04:22,230
Đối với bước 2, chúng tôi liên tục hợp nhất cặp danh sách bằng cách sử dụng các thuật toán hợp nhất chúng tôi đã học được trước.

68
00:04:22,230 --> 00:04:29,160
Sáp nhập 108 và 15, chúng tôi kết thúc với danh sách 15, 108.

69
00:04:30,330 --> 00:04:36,250
Sáp nhập 50 và 4, chúng tôi kết thúc với 4, 50.

70
00:04:36,960 --> 00:04:41,400
Sáp nhập 8 và 42, chúng tôi kết thúc với 8, 42.

71
00:04:42,790 --> 00:04:48,130
Và sáp nhập 23 và 16, chúng tôi kết thúc với 16, 23.

72
00:04:49,740 --> 00:04:52,450
Bây giờ tất cả các danh sách của chúng tôi là kích thước 2.

73
00:04:53,020 --> 00:04:56,180
Chú ý rằng mỗi trong 4 danh sách được sắp xếp.

74
00:04:56,180 --> 00:04:59,160
>> Vì vậy, chúng ta có thể bắt đầu sáp nhập các cặp danh sách một lần nữa.

75
00:04:59,160 --> 00:05:03,240
Sáp nhập 15 và 108 và 4 và 50 -

76
00:05:03,240 --> 00:05:11,170
đầu tiên lấy 4, sau đó là 15, sau đó là 50, sau đó số 108.

77
00:05:11,170 --> 00:05:15,120
Sáp nhập 8, 42 và 16, 23,

78
00:05:15,120 --> 00:05:22,440
chúng tôi lần đầu tiên mất 8, sau đó số 16, sau đó số 23, số 42.

79
00:05:22,440 --> 00:05:27,370
Vì vậy, bây giờ chúng tôi có 2 danh sách các kích thước 4, mỗi trong số đó được sắp xếp.

80
00:05:27,370 --> 00:05:30,980
Vì vậy, bây giờ chúng tôi hợp nhất 2 danh sách này.

81
00:05:30,980 --> 00:05:33,440
Trước tiên, lấy 4.

82
00:05:33,440 --> 00:05:36,580
Sau đó, chúng tôi đi 8.

83
00:05:36,580 --> 00:05:50,700
Sau đó, chúng tôi mất 15 và 16, sau đó 23, sau đó 42, sau đó 50, sau đó 108.

84
00:05:50,700 --> 00:05:52,220
Và chúng tôi đang làm.

85
00:05:52,220 --> 00:05:54,900
Bây giờ chúng ta có một danh sách được sắp xếp.

86
00:05:54,900 --> 00:05:57,890
Vì vậy, làm thế nào nhanh chóng được điều này, chính xác?

87
00:05:57,890 --> 00:06:02,000
Trong điều kiện kỹ thuật, hợp nhất sắp xếp là O (n log n),

88
00:06:02,000 --> 00:06:07,380
trong khi đó tất cả các loại bong bóng, sắp xếp chèn và sắp xếp lựa chọn là O (n ²).

89
00:06:07,380 --> 00:06:11,120
Trong thực tế, bạn sẽ học sớm, bạn sẽ không có thể để đến với một loại

90
00:06:11,120 --> 00:06:14,820
thực hiện tốt hơn so với O (n log n) trong trường hợp chung.

91
00:06:14,820 --> 00:06:19,120
Một lần nữa, đừng lo lắng về điều này ký hiệu O lớn nếu bạn không nhìn thấy nó.

92
00:06:19,120 --> 00:06:23,490
>> Chỉ biết rằng điều này có nghĩa là nếu chúng ta muốn sắp xếp một danh sách thực sự lớn

93
00:06:23,490 --> 00:06:26,820
bong bóng sắp xếp, sắp xếp chèn, và lựa chọn loại có khả năng có thể mất

94
00:06:26,820 --> 00:06:29,500
lâu hơn đáng kể hơn so với hợp nhất loại.

95
00:06:29,500 --> 00:06:33,210
Nó không có nghĩa rằng loại hợp nhất sẽ nhanh hơn cho tất cả các danh sách

96
00:06:33,210 --> 00:06:36,220
hoặc ngay cả đối với bất kỳ danh sách duy nhất theo một kích thước nhất định.

97
00:06:36,220 --> 00:06:41,950
Ví dụ, chèn loại có thể là các loại nhanh nhất cho tất cả các danh sách nhỏ hơn 5 yếu tố.

98
00:06:41,950 --> 00:06:47,360
Trong thực tế, loại hợp nhất thường là nhanh hơn cho các danh sách nhỏ như 50 phần tử.

99
00:06:47,360 --> 00:06:51,120
>> Tuy nhiên, tốc độ này không đến mà không có một mức giá.

100
00:06:51,120 --> 00:06:54,770
Không giống như các loại khác của chúng tôi, có một danh sách và sửa đổi danh sách ở vị trí

101
00:06:54,770 --> 00:06:58,740
cho đến khi chúng tôi nhận được một danh sách được sắp xếp, hợp nhất loại cần thêm một số không gian

102
00:06:58,740 --> 00:07:00,900
hợp nhất 2 danh sách với nhau.

103
00:07:00,900 --> 00:07:04,690
Chúng ta có thể không ngay lập tức sử dụng danh sách đang được sáp nhập để lưu trữ các danh sách sáp nhập

104
00:07:04,690 --> 00:07:08,880
kể từ khi chúng tôi có thể ghi đè lên các yếu tố vẫn cần phải được sáp nhập.

105
00:07:08,880 --> 00:07:13,540
Không gian này là một chút của một mức giá, nhưng nó thường không phải là không hợp lý.

106
00:07:13,540 --> 00:07:15,330
Và đó là nó cho hợp nhất loại.

107
00:07:15,330 --> 00:07:18,490
>> Tên tôi là Rob Bowden, và đây là CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
Và lựa chọn sắp xếp.

110
00:07:24,000 --> 00:07:25,880
[Cười]

111
00:07:25,880 --> 00:07:31,480
Oh, có đi mà ra quá vì tôi chuyển sang làm thế nào tôi đã trình bày nó.

112
00:07:31,480 --> 00:07:35,680
Danh sách bên trái. Đó là một lỗi đánh máy.

113
00:07:35,680 --> 00:07:39,290
[Misspoke Tôi hơi say lên -

114
00:07:39,290 --> 00:07:41,190
[Cười]

115
00:07:41,190 --> 00:07:44,190
Tôi không biết những gì