1
00:00:00,000 --> 00:00:05,726
>> [音樂播放]

2
00:00:05,726 --> 00:00:08,600
道格·勞埃德：選擇排序是
算法，正如您所料，

3
00:00:08,600 --> 00:00:10,470
排序一組元素。

4
00:00:10,470 --> 00:00:12,470
與算法召回
是一步一步的設置

5
00:00:12,470 --> 00:00:15,260
的用於完成任務的指令。

6
00:00:15,260 --> 00:00:17,580
>> 在選擇排序
基本思路是這樣，

7
00:00:17,580 --> 00:00:22,080
找到最小的未分類的元素，
其添加到排序的列表的末尾。

8
00:00:22,080 --> 00:00:26,970
有效地這樣做是什麼版本
排序列表，一次一個元件。

9
00:00:26,970 --> 00:00:29,800
將它分解為偽
我們可以說明這個算法

10
00:00:29,800 --> 00:00:34,490
如下所示，重複上述操作直至
沒有排序的元素依然存在。

11
00:00:34,490 --> 00:00:38,660
通過搜索未排序
數據，以找到最小的值，

12
00:00:38,660 --> 00:00:44,130
然後交換的最小值與
未排序的部分的第一要素。

13
00:00:44,130 --> 00:00:47,130
>> 它可以幫助想像這一點，
讓我們來看看這個。

14
00:00:47,130 --> 00:00:49,710
所以，我主張，是一個
排序的數組，我已經

15
00:00:49,710 --> 00:00:53,040
通過表明所有表示，它
元素為紅色，

16
00:00:53,040 --> 00:00:54,420
它們還未排序。

17
00:00:54,420 --> 00:00:57,670
這是整個
陣列的未分類的一部分。

18
00:00:57,670 --> 00:01:02,020
>> 因此，讓我們通過以下步驟：
選擇排序該數組進行排序。

19
00:01:02,020 --> 00:01:05,296
所以，再一次，我們要重複
直到沒有未分類的元素依然存在。

20
00:01:05,296 --> 00:01:07,920
我們通過要去搜索
數據，以找到最小的值，

21
00:01:07,920 --> 00:01:11,990
然後交換用該值
未排序的部分的第一要素。

22
00:01:11,990 --> 00:01:14,380
>> 現在，再次，整個
數組是未排序的一部分。

23
00:01:14,380 --> 00:01:16,534
所有的紅色元素是無序。

24
00:01:16,534 --> 00:01:18,700
所以我們通過搜索和
我們發現的最小值。

25
00:01:18,700 --> 00:01:20,533
我們從頭開始，
我們去年底，

26
00:01:20,533 --> 00:01:23,630
我們發現最小的值，之一。

27
00:01:23,630 --> 00:01:24,860
所以這是第一部分。

28
00:01:24,860 --> 00:01:29,440
然後第二部分，換用該值
未排序部分的第一要素，

29
00:01:29,440 --> 00:01:31,340
還是先紅素。

30
00:01:31,340 --> 00:01:34,980
>> 在這種情況下，這將是
五，所以我們換一到五。

31
00:01:34,980 --> 00:01:37,320
當我們做到這一點，我們就可以
直觀地看到，我們已經

32
00:01:37,320 --> 00:01:41,260
移動最小的值元素
陣列的，到最開始。

33
00:01:41,260 --> 00:01:43,920
有效地排序的元素。

34
00:01:43,920 --> 00:01:47,520
>> 因此，我們的確可以確認
並指出之一，排序。

35
00:01:47,520 --> 00:01:52,080
因此，我們將指示排序部分
我們的陣列，通過著色它的藍色。

36
00:01:52,080 --> 00:01:53,860
>> 現在，我們只需再次重複這個過程。

37
00:01:53,860 --> 00:01:57,430
我們通過對未分類的部分搜索
陣列找到的最小元素。

38
00:01:57,430 --> 00:01:59,000
在這種情況下，它的兩種。

39
00:01:59,000 --> 00:02:02,100
>> 我們交換與第一
未排序的部分元素。

40
00:02:02,100 --> 00:02:05,540
在這種情況下，雙方還恰好是
未排序部分的第一個元素。

41
00:02:05,540 --> 00:02:08,650
因此，我們交換兩個與自身，
這真的只是留下了兩個

42
00:02:08,650 --> 00:02:11,257
它在哪裡，並且它的排序。

43
00:02:11,257 --> 00:02:13,840
繼續，我們通過搜索
找到的最小元素。

44
00:02:13,840 --> 00:02:15,030
這三種。

45
00:02:15,030 --> 00:02:17,650
我們的第一個交換是
元素，這是五。

46
00:02:17,650 --> 00:02:19,450
現在，三是排序。

47
00:02:19,450 --> 00:02:22,440
>> 我們通過再次搜索，而我們
找到最小的元素為四。

48
00:02:22,440 --> 00:02:28,070
我們用的第一個元素將其交換
未分類的一部分，現在四是排序。

49
00:02:28,070 --> 00:02:29,910
>> 我們發現，五是
的最小元素。

50
00:02:29,910 --> 00:02:32,900
我們的第一個交換是
未排序的部分元素。

51
00:02:32,900 --> 00:02:34,740
而現在五是排序。

52
00:02:34,740 --> 00:02:36,660
>> 然後最後，我們
未分類的部分由

53
00:02:36,660 --> 00:02:38,576
只是一個單一的元件的，
所以我們通過搜索

54
00:02:38,576 --> 00:02:41,740
而且我們發現六是
最小的，而事實上，唯一的元素。

55
00:02:41,740 --> 00:02:44,906
然後，我們可以說，它是排序。

56
00:02:44,906 --> 00:02:47,530
而現在，我們已經關掉我們的數組
被完全未排序

57
00:02:47,530 --> 00:02:52,660
紅色，完全排序
藍色，使用選擇排序。

58
00:02:52,660 --> 00:02:54,920
>> 那麼什麼是最糟糕的情況嗎？

59
00:02:54,920 --> 00:02:57,830
那麼在絕對最差
情況下，我們必須過目

60
00:02:57,830 --> 00:03:02,170
所有的數組的元素的
找到最小的未分類的元素，

61
00:03:02,170 --> 00:03:04,750
我們要重複
這個過程n次。

62
00:03:04,750 --> 00:03:09,090
一旦對陣列的每個元素
因為我們只在這個算法中，

63
00:03:09,090 --> 00:03:12,180
在時間排序一個元素。

64
00:03:12,180 --> 00:03:13,595
>> 什麼是最好的情況？

65
00:03:13,595 --> 00:03:15,040
那麼它是完全一樣的，對不對？

66
00:03:15,040 --> 00:03:18,440
實際上，我們必須通過仍然步驟
該陣列的每一個元素

67
00:03:18,440 --> 00:03:22,040
為了確認它，
事實上，最小的元素。

68
00:03:22,040 --> 00:03:26,760
>> 因此，最壞的情況下運行時，我們
要重複一個過程n次，

69
00:03:26,760 --> 00:03:28,960
一次，每個n個元素。

70
00:03:28,960 --> 00:03:31,940
並且在最好的情況下，
我們必須這樣做。

71
00:03:31,940 --> 00:03:35,340
>> 所以，回想起我們
計算複雜性的工具箱，

72
00:03:35,340 --> 00:03:39,250
你覺得是最糟糕的
情況下運行時選擇排序？

73
00:03:39,250 --> 00:03:41,840
你認為什麼是最好的
情況下運行時選擇排序？

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> 你猜大O n個平方，
和N大歐米茄平方？

76
00:03:49,325 --> 00:03:49,950
你是對的。

77
00:03:49,950 --> 00:03:52,490
那些是，事實上，該
最壞的情況下，最好的情況下運行

78
00:03:52,490 --> 00:03:55,100
次，選擇排序。

79
00:03:55,100 --> 00:03:56,260
>> 我是道格·勞埃德。

80
00:03:56,260 --> 00:03:58,600
這是CS50。

81
00:03:58,600 --> 00:04:00,279