每次选出最小（或最大）的一个元素，存放在数组的起始位置，直到所有元素都排完。
- 在数组中选出最大（小）的元素。
- 若该元素不是数组的最好一个（第一个）元素，那么就与数组中的最后一个（第一个）元素进行交换。
- 然后在剩余的或者的数组中重复上述步骤，直到只剩下一个元素。
注意：本文讲解的是已经优化过一遍的版本（一次选出最大和最小）。
我们先设立好区间，使用begin作为遍历的起点，end为终点；由于begin和end是区间，所以我们在遍历的时候不能改变他们的值，所以我们再建立两个变量(mini和maxi)，用来存放最大和最小元素的下标。
然后再进行交换，最小的元素和第一个元素交换，最大的元素和最后一个元素交换。
但是，有一个特殊情况：当首元素（下标为begin的元素）是最大的元素的时候。
解决方法：由于我先交换了最小的元素，所以这时最大的元素就在mini下标处，那我在进行最大元素的交换前，先判断maxi是否等于begin，如果等于，我就将mini赋给maxi（由于mini和maxi存放的都是下标，所以在交换前并不会影响数组的原本顺序）
最后从单次排序转换成多次排序（改变区间的值）
尽管是优化了，但效率依旧不高。
- 直接插入的排序很好理解，但是效率不高，基本没用使用的价值
- 时间复杂度:
- 空间复杂度:
- 稳定性:不稳定
堆排序也是选择排序的一种，但是效率很高，由于堆排序在前文已经讲解过了，在本文就不讲解了（链接：堆排序）。
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序
所谓交换，就算根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置。
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
任取待排序序列中的某个元素为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序重复上的过程（找基准值->分割），直到所有元素都排列在相应的位置上。
主体框架为：
我们从框架可以发现，这与二叉树的前序遍历的规则非常相似，所以我们根据前序遍历可以很快的写出框架，后续只需要分析如何按照基准值来对区间内的数据进行划分即可。
2.3.1 Hoare版本
具体情况如下：
先让right走，遇到比基准值小的停下来，然后让left走，遇到比基准值大的停下来，当他们停下来后，将他们两个所对应的元素进行交换，重复此操作，直到他们两个相遇，相遇之后将基准值与相遇位置所对应的元素进行交换。
他们相遇位置的元素一定是基准值，所以不需要判断基准值与相遇元素的大小
关于元素一定基准值的证明
他们相遇只有两种情况，left 遇到 right，或者 right 遇到 left
这里的遇到指的是，移动的一方 遇到 静止的一方
- 情况一：right不动，left遇到right，前面我们说了，我们会先让right先走，right不动了，就代表此时right位置所对应元素一定是小于基准值的，然后left遇到了right那么就代表left走过的区域已经没有比基准值大的元素了而后面已经被right走过或者交换过了，那么相遇位置之前的元素就都小于基准值了。
- 情况二：right一直走到left的位置，那么这时就有两种情况，left没有移动过和left移动过；
left没有移动的话，那么他所在的值是基准值本身，这时就相遇元素等于基准值
left移动过的话，由于是right先移动，那么他们必定发生了交换，且left位置的值一定是交换过后的值，这就相遇元素就一定小于基准值。
2.3.2 挖坑法
随着快排的不断发展，人们优化了Hoare方法，用挖坑法，虽然这种方法没有效率的提升，但提高了代码的可读性，也不要纠结相遇元素与基准值的大小关系。
2.3.3 前后指针法
快速排序还有另一种方法，也是可读性最好的，我们可以定义两个指针（），prev一个指向开头，cur指向prev的下一个数，然后让cur一直向前走，直到找比key小的数，然后让prev走一步并进行交换，然后继续让cur找比key小的值（遇到大于key的就++cur），重复以上操作，直到cur越界（），当cur越界的时候，将key与prev指向的元素进行交换。
具体如图：
这个优化和上面的挖坑法、前后指针是不一样的，上述两种方法是优化了代码可读性和简化了思想复杂性，他们的效率都是一样的。
而这个优化的是快排的性能。
也就是说，由于每次排序，key值都是整个数组中最小的数，因此，每次分割都会分割出一个只有key的左区间和剩余元素的右区间。但由于内存中的栈空间无法同时容纳十万个函数，所以会出现栈溢出。
解决方法（三数取中）：先提取出数组的开头元素、结尾元素、中间元素，然后在他们三个中选择中间值，这样就能解决快排在有序情况下的栈溢出的问题，同时也能提升快排的效率
2.4.1 三数取中
放入快排：
2.4.2 小区间优化
小区间优化，就是当这个区间的大小到达一定程度时，直接用插入排序。
放入快排：
而快速排序我们讲解了Hoare版本，挖坑法和前后指针法，这三个方法并没有效率的差别，还讲解快排在有序情况下的优化（三数取中），和小区间优化。
其中小区间优化用到了直接插入排序，这个在前文也有讲到（链接：排序【插入排序】）。