1
00:00:00,000 --> 00:00:02,826
>> [MUSIC CHƠI]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Vì vậy, sắp xếp chèn là một
thuật toán chúng ta có thể sử dụng để sắp xếp một mảng.

4
00:00:09,370 --> 00:00:12,350
Ý tưởng đằng sau thuật toán này
là xây dựng mảng được sắp xếp của bạn

5
00:00:12,350 --> 00:00:19,670
tại chỗ, chuyển các yếu tố ra khỏi
cách như bạn đi, để làm cho căn phòng.

6
00:00:19,670 --> 00:00:22,240
Điều này là hơi khác nhau
từ lựa chọn loại hoặc bong bóng

7
00:00:22,240 --> 00:00:25,460
sắp xếp, ví dụ, nơi
chúng tôi đang điều chỉnh các vị trí,

8
00:00:25,460 --> 00:00:26,910
nơi mà chúng tôi đang thực hiện giao dịch hoán đổi.

9
00:00:26,910 --> 00:00:29,760
>> Trong trường hợp này những gì chúng tôi đang thực sự
làm là yếu tố trượt

10
00:00:29,760 --> 00:00:31,390
hơn, ra khỏi con đường.

11
00:00:31,390 --> 00:00:34,030
Làm thế nào thuật toán này
làm việc trong giả?

12
00:00:34,030 --> 00:00:37,646
Vâng chúng ta hãy chỉ tùy tiện nói rằng
Yếu tố đầu tiên của mảng được sắp xếp.

13
00:00:37,646 --> 00:00:38,770
Chúng tôi đang xây dựng nó tại chỗ.

14
00:00:38,770 --> 00:00:42,660
>> Chúng ta sẽ đi một yếu tố tại một thời gian và
xây dựng nó, và do đó, điều đầu tiên chúng ta thấy

15
00:00:42,660 --> 00:00:43,890
là một mảng một phần tử.

16
00:00:43,890 --> 00:00:47,720
Và theo định nghĩa, một
mảng phần tử được sắp xếp.

17
00:00:47,720 --> 00:00:50,850
>> Sau đó chúng tôi sẽ lặp lại quá trình này until--
chúng ta sẽ lặp lại các quá trình sau đây

18
00:00:50,850 --> 00:00:52,900
cho đến khi tất cả các yếu tố đều được sắp xếp.

19
00:00:52,900 --> 00:00:57,770
Nhìn vào các yếu tố không được phân loại tiếp theo và
chèn nó vào phần được sắp xếp,

20
00:00:57,770 --> 00:01:01,209
bằng cách thay đổi số lượng yêu cầu
các yếu tố ra khỏi con đường.

21
00:01:01,209 --> 00:01:03,750
Hy vọng rằng hình này
sẽ giúp bạn thấy chính xác những gì

22
00:01:03,750 --> 00:01:05,980
xảy ra với sắp xếp chèn.

23
00:01:05,980 --> 00:01:08,010
>> Vì vậy, một lần nữa, đây là của chúng tôi
toàn bộ mảng không được phân loại,

24
00:01:08,010 --> 00:01:10,970
tất cả các yếu tố chỉ màu đỏ.

25
00:01:10,970 --> 00:01:13,320
Và chúng ta hãy thực hiện theo các
bước của mã giả của chúng tôi.

26
00:01:13,320 --> 00:01:16,970
Điều đầu tiên chúng tôi làm, là chúng ta gọi là
Yếu tố đầu tiên của mảng, sắp xếp.

27
00:01:16,970 --> 00:01:20,920
Vì vậy, chúng tôi sẽ chỉ nói
năm, bạn tôi bây giờ được sắp xếp.

28
00:01:20,920 --> 00:01:24,570
>> Sau đó, chúng ta nhìn vào các tiếp theo
yếu tố không được phân loại của mảng

29
00:01:24,570 --> 00:01:27,610
và chúng tôi muốn chèn rằng
thành phần được sắp xếp,

30
00:01:27,610 --> 00:01:29,750
bằng cách chuyển các yếu tố trên.

31
00:01:29,750 --> 00:01:33,470
Vì vậy, hai là không được phân loại tiếp theo
phần tử của mảng.

32
00:01:33,470 --> 00:01:36,250
Rõ ràng nó thuộc về trước
năm, vì vậy những gì chúng ta sẽ làm

33
00:01:36,250 --> 00:01:41,580
là loại giữ hai dành cho một thứ hai,
chuyển năm qua, và sau đó chèn hai

34
00:01:41,580 --> 00:01:43,210
trước năm, đâu cần đi.

35
00:01:43,210 --> 00:01:45,280
Và bây giờ chúng ta có thể nói rằng hai được sắp xếp.

36
00:01:45,280 --> 00:01:48,400
>> Vì vậy, như bạn có thể thấy, chúng ta chỉ đã cho đến nay
nhìn hai yếu tố của mảng.

37
00:01:48,400 --> 00:01:50,600
Chúng tôi đã không xem xét các
nghỉ ngơi ở tất cả, nhưng chúng ta

38
00:01:50,600 --> 00:01:54,582
đã hai yếu tố được sắp xếp theo
cách của các cơ chế chuyển dịch.

39
00:01:54,582 --> 00:01:56,410
>> Vì vậy, chúng ta lặp lại quá trình này một lần nữa.

40
00:01:56,410 --> 00:01:58,850
Nhìn vào không được phân loại tiếp theo
yếu tố, đó là một.

41
00:01:58,850 --> 00:02:04,010
Chúng ta hãy nắm mà dành cho một thứ hai,
thay đổi tất cả mọi thứ trên, và đặt một

42
00:02:04,010 --> 00:02:05,570
nơi cần đi.

43
00:02:05,570 --> 00:02:08,110
>> Một lần nữa, vẫn còn, chúng tôi đã chỉ có bao giờ
nhìn một, hai, và năm.

44
00:02:08,110 --> 00:02:12,480
Chúng tôi không biết những gì khác đang đến,
nhưng chúng tôi đã sắp xếp ba yếu tố.

45
00:02:12,480 --> 00:02:16,030
>> Yếu tố không được phân loại tiếp theo là
ba, vì vậy chúng tôi sẽ thiết lập nó sang một bên.

46
00:02:16,030 --> 00:02:18,200
Chúng tôi sẽ thay đổi theo những gì chúng tôi
cần đó, thời gian này

47
00:02:18,200 --> 00:02:21,820
không phải là tất cả mọi thứ như trong các trước
hai trường hợp, nó chỉ là các năm.

48
00:02:21,820 --> 00:02:25,440
Và sau đó chúng tôi sẽ dính ba,
giữa hai và năm.

49
00:02:25,440 --> 00:02:27,849
>> Sáu là tiếp theo không được phân loại
yếu tố để các mảng.

50
00:02:27,849 --> 00:02:31,140
Và trên thực tế lớn hơn sáu năm, vì vậy
chúng tôi thậm chí không cần phải làm bất cứ trao đổi.

51
00:02:31,140 --> 00:02:35,710
Chúng tôi chỉ có thể tack sáu phải vào
sự kết thúc của phần được sắp xếp.

52
00:02:35,710 --> 00:02:38,270
>> Cuối cùng, bốn là
yếu tố không được phân loại cuối cùng.

53
00:02:38,270 --> 00:02:42,060
Vì vậy, chúng tôi sẽ thiết lập nó sang một bên, thay đổi theo
các yếu tố chúng ta cần phải thay đổi theo,

54
00:02:42,060 --> 00:02:43,780
và sau đó đặt bốn nơi mà nó thuộc về.

55
00:02:43,780 --> 00:02:46,400
Và bây giờ nhìn, chúng tôi đã loại
của tất cả các yếu tố.

56
00:02:46,400 --> 00:02:48,150
Chú ý với chèn
sắp xếp, chúng tôi không có

57
00:02:48,150 --> 00:02:50,240
để đi qua lại trên mảng.

58
00:02:50,240 --> 00:02:54,720
Chúng tôi chỉ đi qua mảng
một thời gian, và chúng tôi chuyển điều

59
00:02:54,720 --> 00:02:59,870
rằng chúng ta đã gặp phải, theo thứ tự
để nhường chỗ cho các yếu tố mới.

60
00:02:59,870 --> 00:03:02,820
>> Vì vậy, trường hợp xấu nhất là gì
kịch bản với sắp xếp chèn?

61
00:03:02,820 --> 00:03:05,090
Trong trường hợp xấu nhất,
mảng là theo thứ tự ngược.

62
00:03:05,090 --> 00:03:11,180
Bạn phải thay đổi mỗi nguyên tố n
lên đến vị trí n, mỗi lần chúng ta duy nhất

63
00:03:11,180 --> 00:03:12,880
làm cho một chèn.

64
00:03:12,880 --> 00:03:15,720
Đó là rất nhiều thay đổi.

65
00:03:15,720 --> 00:03:18,014
>> Trong trường hợp tốt nhất,
mảng được sắp xếp một cách hoàn hảo.

66
00:03:18,014 --> 00:03:20,680
Và loại giống như những gì đã xảy ra
với năm và sáu trong ví dụ,

67
00:03:20,680 --> 00:03:23,779
đó chúng ta chỉ có thể tack nó trên
mà không cần phải làm bất cứ chuyển dịch,

68
00:03:23,779 --> 00:03:24,820
chúng tôi chủ yếu muốn làm điều đó.

69
00:03:24,820 --> 00:03:27,560
>> Nếu bạn tưởng tượng rằng chúng tôi
mảng là một đến sáu,

70
00:03:27,560 --> 00:03:29,900
chúng tôi muốn bắt đầu bằng
tuyên bố một được sắp xếp.

71
00:03:29,900 --> 00:03:33,300
Hai đưa ra sau khi một vì vậy chúng ta có thể chỉ
nói, OK, cũng một và hai đều được sắp xếp.

72
00:03:33,300 --> 00:03:36,190
Ba đưa ra sau khi hai như vậy, OK,
một và hai và ba đều được sắp xếp.

73
00:03:36,190 --> 00:03:39,590
>> Chúng tôi không thực hiện bất kỳ giao dịch hoán đổi, chúng tôi
chỉ cần di chuyển dòng tùy tiện này

74
00:03:39,590 --> 00:03:42,460
giữa sắp xếp và không được phân loại như chúng ta đi.

75
00:03:42,460 --> 00:03:46,646
Hiệu quả như chúng ta đã làm trong ví dụ này,
chuyển các yếu tố màu xanh, khi chúng tôi tiến.

76
00:03:46,646 --> 00:03:48,270
Vì vậy, thời gian chạy trường hợp xấu nhất là những gì, sau đó?

77
00:03:48,270 --> 00:03:51,854
Hãy nhớ rằng, nếu chúng ta phải thay đổi mỗi
các yếu tố n có thể là vị trí n,

78
00:03:51,854 --> 00:03:54,020
hy vọng cung cấp cho bạn
một ý tưởng rằng trường hợp xấu nhất

79
00:03:54,020 --> 00:03:57,770
thời gian chạy là Big O của n bình phương.

80
00:03:57,770 --> 00:04:00,220
>> Nếu mảng là hoàn hảo
sắp xếp, tất cả chúng ta phải làm

81
00:04:00,220 --> 00:04:04,480
là nhìn vào từng yếu tố duy nhất
một lần, và sau đó chúng tôi đang thực hiện.

82
00:04:04,480 --> 00:04:08,440
Vì vậy, trong trường hợp tốt nhất, đó là omega của n.

83
00:04:08,440 --> 00:04:09,490
>> Tôi Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Đây là CS50.

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