我们今天继续来讲解我们的排序算法：
先看一下我们的这个图，我们在上一章节里面，我们讲解了插入排序里面的：
直接插入排序和希尔排序；
这节课我们继续来看；
首先是我们的选择排序：
堆排序的话，我们之前学过的，他也是选择排序。
1. 直接选择排序：
先来看一下我们选择排序的思想：
每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
我们来看这个图片，我们的选择排序，我们先把我们的无序的数据进行遍历，然后找到最小的数据，把这个最小的数据放到前面，然后不断的进行重复。
这样最后就可以得到我们的有序的数据。
咱们看这个数组，现在咱们就使用直接选择排序来实现我们的这个排序:
首先，咱们和咱们的第一个图片里面的排序方式是不一样的，咱们的第一个图片里面使用的是，找到咱们的数组里面的最小的数据，然后放到前面，但是咱们在这里，咱们和他不一样，我们换成在我们的数组里面找我们的最小的数据和我们的最大的数据，我们同时找最小和最大，然后交换位置，我们把大的数据放到后面，把小的数据放到前面，这样会更快一点，那么现在我们来实现一下：
这个就是咱们的直接选择排序的代码的实现；
然后我们来运行一下：
假如我们现在传过来一个这样的数组，然后我们来使用我们的直接选择排序来进行排序；
那么我们的结果是什么呢？
在这里你就可以惊奇的发现，我们排序完后的结果居然不是有序的，这就有问题了，这是怎么回事呢？
我们来看我们的这个图片，当我们的代码找到了最小的数据和最大的数据的时候，我们的maxi下标指向了我们的第一个数据，我们的mini下标指向了我们的第二个数据，并且我们的第一个数据的下标也是我们的begin，我们的最后一个数据的下标是end，这两个下标是我们在一开始就确定好的。
然后我们开始交换我们的数据，我们的目标是把小的数据放到最前面，然后把大的数据放到最后面
然后我们开始进行交换，我们把mini下标指向的数据和我们的begin指向的数据进行交换，然后我们的数据3就跑到了最前面，这就说明了什么呢？我们的maxi下标指向的数据现在是3，我们的begin下标指向的数据也是3，然后我们让maxi下标和我们的end下标交换位置，这时候我们的3就到了我们的最后面。6就到了我们的最前面，然后我们的结果就是6 3 9。
那我们该怎样修改我们的代码才可以改变我们的结果呢？
我们来看，当我们的maxi下标和我们的begin下标是一样的话，（在这里我们不能看他们指向的数据是不是一样的，我们要看他们的下标是不是一样的，因为有可能下标不一样，但是他们的数据是一样的）我们交换了下标mini和下标begin的数据，由于下标maxi和下标begin指向的数据是一样的，所以begin（maxi）指向的数据在下标mini上，所以，在这种情况下，我们就可以改变我们的下标maxi的大小，把他改成mini，这时候我们的maxi指向的数据又变回我们的最大值了。
我们判断一下，我们的第一个数据是不是最大值，如果是的话，我们就把下标maxi改成mini；
直接选择排序的时间复杂度我们可以看出来是O（n^2）；
我们来看这几个排序的用时比较，其中我们的堆排序是最快的，然后是希尔排序，然后是直接插入排序，然后是直接选择排序（这里可以看出，直接选择排序其实并不是非常好的一种排序），最后是咱们熟知的冒泡排序。
堆排序我们在这里就不进行详细的讲解了，我们之前说过堆排序。
然后我们来看下一个排序算法：
交换排序：
交换排序包括： 1. 冒泡排序，2. 快速排序。
冒泡排序的话，在这里因为我们之前讲解C语言的时候我们就提过了，所以在这里我们就看快速排序就可以了；
2. 快速排序：
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素 序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩ 于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为⽌。
我们看上面的讲解，快速排序是利用二叉树的结构的交换排序方法；
二叉树的话，我们是比较熟悉的。
快排里面说要在数组里面找到一个基准值，然后把这个数组分割，
我们看我们的这个图，我们的第一行现在是1个元素，第二行两个元素，，，就像是一个二叉树一样。
但是，虽然我们的这个和二叉树比较相似，但是我们的快速排序的结果并不是创造一个二叉树，我们最终的要求还是对我们传过来的数组进行排序，让这个数组最终变成一个有序的数组。
我们来看我们的这个图片，我们在一开始的时候，我们的第一层就是我们的第一次找到基准值的时候的数组，然后我们不断地拆分，在左右两个数组里面再次寻找基准值，最后的话，我们其实看的是我们的红方框圈起来的数据，然后这个数据就是 1，2，3，4，6，7。这个就是我们的快速排序后的结果。
我们选择第一个数据为我们的基准值，然后我们设置两个指针，我们的前一个指针指向我们的第二个数据，然后我们的后面的指针指向我们的最后一个数据，然后我们的前一个指针从前往后移动寻找比我们的基准值大的数据，然后我们的后面的指针从后往前移动，寻找比我们的基准值小的数据，，，当我们的两个指针都找到我们的数据的时候，这时候我们把这两个数据进行交换。
当我们的left > right 的时候，这时候我们把我们的基准值和我们的right下标指向的数据进行交换。
但是如果当我们交换一次结束以后，我们的left依然是小于我们的right的，这时候我们就继续遍历，然后进行交换。
这个是我们的hoare版本的寻找基准值的方式，
其实我们在实现我们的代码的时候其实是有很多的问题的，
我们看场景一，我们的left指向7的时候，我们的right指向3，然后我们把他们进行交换，这时候我们中间的数据是不能直接和我们的基准值进行替换的，这时候因为我们的基准值为第一个数据，如果我们把我们的基准值和我们的这个值替换以后，我们的基准值前面的数据就有比基准值大的数据了。
我们把继续来进行分析，当我们的7和3进行交换以后，我们的7和3中间的数据和我们的基准值的大小是一样的，那么这个时候我们是交换还是不交换呢？如果我们交换了，那么我们的基准值前面的数据还有和他一样的，这还不能说得过去。
我们来看我们的场景3，这个时候，当我们直接交换我们的数据以后，我们的基准值就可以替换我们中间的数据。
其实我们仔细地研究了上面的场景，我们就可以得到我们最终的代码
这时候我们就更新了我们的说法，我们加上条件，当我们的left > right 的时候，我们就吧keyi指向的基准值和我们的right指向的基准值进行交换。
这个就是我们的快速排序的代码的实现；
我们的快速排序的时间复杂度为nlogn
我们来看一下快速排序的速度
在这张图片里面我们就可以发现，我们的快速排序还是很快的，只比堆排序慢了一点。
但是我们的快速排序他有时候的时间复杂度并不好，当我们的数组是有序的数组的时候，我们的快速排序的时间复杂度就是O（n^2）;
当我们的数组有序或者基准值找的不好，就会出现这种情况。
这样的话，他就不是一个二叉树类型的结构了，
我们的递归的深度增加了
由于每次分区都不能有效地将数组分成两部分，导致递归的深度增加。
递归深度增加通常会导致时间复杂度变差
在数组有序的情况下，快速排序的递归深度会达到数组的长度 n。例如，对于长度为 n 的有序数组，需要进行 n - 1 次分区操作，每次分区只减少一个元素，相当于退化为了简单的插入排序。