02-选择排序

本章内容

• 学习两种最基本的数据结构——数组和链表，它们无处不在。 数组是个重要的主题，一定要高度重视!但在有些情况下，使用链表比使用数组更合适。
• 学习第一种排序算法，选择排序。

内存的工作原理

假设你去看演出，需要将东西寄存。寄存处有一个柜子，柜子有很多抽屉。

每个抽屉可放一样东西，你有两样东西要寄存，因此要了两个抽屉。你将两样东西存放在这里。

现在你可以去看演出了!这大致就是计算机内存的工作原理。计算机就像是很多抽屉的集合体，每个抽屉都有地址。

fe0ffeeb是一个内存单元的地址。
需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一 个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。 但它们并非都适用于所有的情形，因此知道它们的差别很重要。接下来介绍数组和链表以及它们的优缺点。

数组和链表

场景描述

有时候，需要在内存中存储一系列元素。假设你要编写一个管理待办事项的应用程序，为此需要将这些待办事项存储在内存中。 应使用数组还是链表呢?鉴于数组更容易掌握，我们先将待办事项存储在数组中。使用数组意味着所有待办事项在内存中都是相连的(紧靠在 一起的)。 现在假设你要添加第四个待办事项，但后面的那个抽屉放着别人的东西! 这就像你与朋友去看电影，找到地方就坐后又来了一位朋友，但原来坐的地方没有空位置，只得再找一个可坐下所有人的地方。在这种情况下，你需要请求计算机重新分配一块可容纳4个待办事项的内存，再将所有待办事项都移到那里。

如果又来了一位朋友，而当前坐的地方也没有空位，你们就得再次转移!真是太麻烦了。
同样，在数组中添加新元素也可能很麻烦。如果没有了空间，就得移到内存的其他地方，因此添加新元素的速度会很慢。 一种解决之道是“预留座位”:即便当前只有3个待办事项，也请计算机提供10个位置，以防需要添加待办事项。这样，只要待办事项不超过 10 个，就无需转移。这是一个不错的权变措施，但你应该明白，它存在如下两个缺点。

• 你额外请求的位置可能根本用不上，这将浪费内存。你没有使用， 别人也用不了。
• 待办事项超过10个后，你还得转移。

因此，这种权宜措施虽然不错，但绝非完美的解决方案。对于这种问题，可使用链表来解决。

链表

链表中的元素可存储在内存的任何地方。

链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

这犹如寻宝游戏。你前往第一个地址，那里有一张纸条写着“下一个元素的地址为123”。因此，你前往地址123，那里又有一张纸条，写着“下一个元素的地址为847”，以此类推。在链表中添加元素很容易:只需将其放入内存，并将其地址存储到前一个元素中。

使用链表时，根本就不需要移动元素。这还可避免另一个问题。假设你与五位朋友去看一部很火的电影。你们六人想坐在一起，但看电影的人较多，没有六个在一起的座位。使用数组时有时就会遇到这样的情况。 假设你要为数组分配10000个位置，内存中有10000个位置，但不都靠在一起。在这种情况下，你将无法为该数组分配内存!链表相当于说“我们分开来坐”，因此，只要有足够的内存空间，就能为链表分配内存。

链表的优势在插入元素方面，那数组的优势又是什么呢?

数组

场景描述

排行榜网站使用卑鄙的手段来增加页面浏览量。它们不在一个页面中显示整个排行榜，而将排行榜的每项内容都放在一个页面中，并让你单击 Next来查看下一项内容。例如，显示十大电视反派时，不在一个页面中显示整个排行榜，而是先显示第十大反派(Newman)。你必须在每个页面中单击Next，才能看到第一大反派(Gustavo Fring)。这让网站能够在10个页面中显示广告，但用户需要单击Next 九次才能看到第一个， 真的是很烦。如果整个排行榜都显示在一个页面中，将方便得多。这样，用户可单击排行榜中的人名来获得更详细的信息。

链表存在类似的问题。在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道它所处的地址，必须先访问元素#1，从中获取元素 #2的地址，再访问元素#2并从中获取元素#3的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高:你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。

数组与此不同:你知道其中每个元素的地址。例如，假设有一个数组， 它包含五个元素，起始地址为00，那么元素#5的地址是多少呢?

只需执行简单的数学运算就知道:04。需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素的地址，以此类推，直到访问第五个元素。

效率的比较

下面是常见数组和链表操作的运行时间：

需要指出的是，仅当能够立即访问要删除的元素时，删除操作的运行时 间才为O (1)。通常我们都记录了链表的第一个元素和最后一个元素，因此删除这些元素时运行时间为O (1)。 数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它 支持随机访问。有两种访问方式：随机访问 和顺序访问 。顺序访问意 味着从第一个元素开始逐个地读取元素。链表只能顺序访问：要读取链 表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随 机访问意味着可直接跳到第十个元素。

链表擅长插入和删除，而数组擅长随机访问

问题： 当不能够立即访问要删除的元素时，链表和数组的插入删除时间复杂度都是o(n)，为什么链表效率高？

描述： 数组在插入删除的时候，要移动元素，复杂度为o(n)。
链表尽管不需要移动元素，只用改变指针关系，但是要插入或删除第i个节点，必须先找到第i-1个节点，复杂度为o(n)。
总体完成一次操作，大家都是o(n)的复杂度，为什么教材和网路上都说，要频繁删除插入操作时，选链表？
一般写入，删除的操作是要先读取定位，在写入、删除。所以链表和数组的插入删除时间复杂度都是o(n)，那为什么链表效率高？

原因：
因为这个O(n)内涵不同，分别是写O(n)和读O(n)。数组擅长读取，链表擅长写入。
写入要先读取定位，再写入。
读取场景：任意序位读取，复杂度： 数组O(1)，链表O(n)。
写入场景：任意序位写入，定位复杂度：数组O(1)，链表O(n)；写入复杂度：数组O(n)，链表O(1)。
在写入场景中，数组链表的复杂度是定位写入复杂度之和，都是O(n),但写入比定位的O(n)慢很多，所以两个表面看起来一样的O(n)的实际时间还是差很多。
所以说链表和数组的插入删除时间复杂度都是o(n)，链表写入效率高。

选择排序

时间复杂度

假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作品被 播放的次数。

你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队 排序。该如何做呢？ 一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队 添加到一个新列表中。

再次这样做，找出播放次数第二多的乐队。

继续这样做，你将得到一个有序列表。

对乐队列表进行简单查 找时，意味着每个乐队都要查看一次。

要找出播放次数最多的乐队，必须检查列表中的每个元素。正如你刚才 看到的，这需要的时间为O (n )。因此对于这种时间为O (n )的操作，你需要执行n 次。

需要的总时间为 O (n × n )，即O (n 2 )。

简单理解：
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。
对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。

void aFunc(int n) {
　　for(int i = 0; i < n; i++) { // 循环次数为 n
　　printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
　　}
}

此时时间复杂度为 O(n × 1)，即 O(n)。 当aFunc执行n次时 ，时间复杂度就变成了 需要的总时间为 O (n × n )，即O (n 2 )

为啥说选择排序是不稳定的

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最前（最后），直到所有待排序的数据元素排完。选择排序是不稳定的排序方法。

选择排序是给每一个位置选择当前元素最小的，比方给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推。直到第n-1个元素，第n个元素不用选择了，由于仅仅剩下它一个最大的元素了。那么，在一趟选择。假设一个元素比当前元素小。而该小的元素又出如今一个和当前元素相等的元素后面。那么交换后稳定性就被破坏了。比較拗口。举个样例，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了。

假如5不是一个数字，而是一个对象；我们是对一组List