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