1、基础排序算法

接下类，我们学习另外一类非常基础的算法，即排序算法。
排序算法是计算机科学领域研究的非常深入的一类算法，排序这个动作本身也是非常重要的，
很多时候面对无需的数据，首先需要做的就是对他们进行排序。

排序算法——目的：让数据有序。
排序算法——种类：种类也非常多，适用于不同的情景。
排序算法——思想：蕴含着重要的计算机科学中的算法设计思想。

我们即将学习2个简单的排序算法：

1、选择排序法
2、插入排序法

通过对这2个基础的排序算法的学习，引申出更多东西，以打牢算法基础；
后续学习更加高级和更加复杂的算法时，可以有充分的准备。

特别是插入排序法，由于它的一些特殊性质，后续我们甚至在一些高级排序算法的学习中，甚至需要用到这种
类似插入排序这样的低级算法来进行一些优化。

2、选择排序法算法设计思想

我们接下来首先来看选择排序法。什么是选择排序法呢？它的思路本身很简单。
比如说，给我们一些待排序的元素，我们如何将这些本来是乱序的元素从小到大排列好呢？
非常简单，思路如下；

先在所有元素中将最小的元素拿出来
剩下的元素中，把最小的拿出来
剩下的元素中，把最小的拿出来
剩下的元素中，把最小的拿出来
……
只剩下一个元素，这个元素就是“剩下的元素中”最小的元素，将这最后一个元素拿出来

即：每次都选择还没处理的元素中最小的元素。
上述的思路就是选择排序法。

我们现在创建一个数组如下：

其中最小的元素是1：

拿出最小的元素1:

接着继续拿出最小的元素，分别拿出2、3、4：

直到所有“剩余的最小的元素”全部拿完，新的排序后数组出现：

我们上述的图片流程，我们的数组从6、3、2、1、5、4
到1、2、3、4、5、6的这个过程。

其实是使用了一个额外的数组空间，是从旧的数组6、3、2、1、5、4的基础上，新开辟了一个数组。
之后每次从旧的数组中找到剩下的元素中最小的元素，然后存储到新开辟的数组中……

这样一个过程，其实这样操作就占用了额外的空间，也是一种空间上的浪费。

接下来，我们要做的一个比较重要的事情是，我们的选择排序可否在原地完成？
这也是排序算法中非常重要的一个概念，即原地排序。

可以参考度娘的定义：原地排序

后续，我们会接触较多原地排序的算法，随着深入学习，我们会发现，有些算法可以用原地排序的方式实现；
但是对于另外一些排序算法，我们是无法原地排序实现的，必须借助额外的空间。

我们今天即将实现的选择排序就是一个可以原地排序的算法。

接下来，我们对选择排序进行图流程讲解。

我们直接实现原地排序的算法代码，
其实思路比较简单，我们每一轮找剩下的元素中最小的元素，我们只需要把我们找到的最小的元素直接放在数组开头的位置即可，即直接利用原来的数组空间即可。
举一个例子：
对于我们的数组的索引i，它初始的时候指着我们的数组索引为0的位置，表示我们现在想寻找排序之后的数组的第0个元素的位置应该是谁？