目录
一、排序的概念及其应用
1 排序的概念：
? ? ? ? ?排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
????????稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
????????内部排序：数据元素全部放在内存中的排序。
????????外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
2 排序的应用
生活中处处存在排序，比如班级成绩排行榜、购物车上的商品排序等等。
3 常见的排序算法
?二、常见的排序算法代码实现
1.插入排序
插入排序的基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
就好比如我们在玩扑克牌时就运用到了插入排序，把牌按顺序逐个进行插入排序。
①直接插入排序的思路为：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
也就是说，在已经排序好的[0,end]这个区域内，对end+1这个下标的元素进行插入，插入到[0，end]中，插入后，变成了[0,end+1]，然后end后移，变成了[0,end]。
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
代码如下(下面代码是降序，若要升序，则将a[end] < temp 中的 <? 换成 > )
②希尔排序（缩小增量排序）：希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。??
也就是说，分组来排序，当分组为1的时候，就是直接插入排序了。
希尔排序的特点是：前面几组的排序会让数据趋于有序，但不是有序，这叫预排序，当达到这种状态的时候，再最后分成1组去排序，也就是直接排序，效率会增大。
?希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化.
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4.稳定性：不稳定? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
对于希尔排序的时间复杂度，根据殷人昆老师的《数据结构-用面相对象方法与C++描述》里面所提到的：我们可以将其定为O(logN^1.3)
代码如下：
2.选择排序
在这里就不再将堆排序了，如果要去了解堆排序可以去看我的二叉树(入门级)的文章，里面有对堆排序的详解。
2.1 选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
这里介绍直接选择排序：
?直接选择排序:
? ? ? ? ·在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
????????·若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
????????·在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
也就是说，定义max和mini，单趟走的时候，来找到本趟中最小和最大的两个数，然后将最小的放到数组的前面，最大的放到后面，然后多趟循环，每一次循环都不算入已经排好的数。
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
代码如下：
?3 交换排序
交换排序的基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
3.1 冒泡排序：
这是一个简单的排序。将每一个数组的元素进行一一比较，不断的往后放，每循环一次，就不算上已经排序好的元素，因此每一趟排序都是减1.
?冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
代码如下：
?3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
在实现快速排序的时候，可以有递归和非递归两种方式！
3.2.1递归的方法，可以将其想象成二叉树，每一次分左右两块排序，分了再分，直到不能再分了，就排序完成了。
将区间按照基准值划分为左右两半部分的常见方式有：①hoare 版本? ②挖坑法? ③前后指针法
①hoare 版本
找出一个key值，用来分割左右区域，让右边区域的值是比key大的值，左边的则是比key的值要小。
然后分完一趟后，使用递归：将key所在的下标传回去，然后分割成[left,key-1]? key? [key+1,right]? 三个区域，然后再将[left,key-1]? 和?[key+1,right] 进行一趟的排序。接下来依次按照上面的步骤进行，直到每个区域里的? left >= right 就返回。最终成功排序。
这里需要注意的是：如何确保当两边相遇的时候，其相撞的位置是小于key的值，以至于能够将key的值和这个位置的值交换，达到右边小左边大，key为分割线的目的呢？
这里就需要确定好，谁先走的问题。
因此，结论是：如果左边第一个做key，那就让r先走，如果右边第一个做key，那就left先走。
流程图：
?代码如下：
?接下来，我们可以通过计算这个递归，类似二叉树的深度，可得知：如果每次的key，我们都是选在了中位数，那么，递归的深度就是logN，时间复杂度在O(N*logN)然后我们再继续分析：
?如果我们选的key不在中位数，那么深度大概就是N,时间复杂度在O(N*N)
?所以，我们要优化这个算法，从选key这个点上入手！尽量把key值，选在中位数。那么，对于随机数而言，该如何去选取出来呢？
我们采取三数取中的方法便可，即 第一个数? ?中间值? ? 最后一个数? ?咱们选取中间值。
代码如下：
?当取到这个中位数后，我们可以将左边第一个或者右边第一个与之交换，这样我们就可以使用上面的思路：关于哪边先走的问题了。优化好后的代码如下：
?然而，这还不是最优化的。我们可以通过二叉树的概念，观察到这里的递归部分，从第一层开始，每一层的数量是从2^0? ?2^1? ?2^2.......依次往下增长，使得递归的次数越来越多，函数栈帧建立就越来越多，如果数量太大，会导致栈溢出的问题。
而通过观察，我们可以发现，二叉树的2^(h-1)层这一部分占了总数的百分之五十，2^(h-2)占了总数的百分之25，2^(h-3)占了总数的百分之12.5。这三层加起来，总共是87.5，占了总数的87.5.
如果我们在递归的时候，可以放弃这一部分，不通过递归来排序这一部分，那么算法的效率将会增大！那么我们要怎么放弃这一部分，又怎么样来排序这一部分呢？
?我们通过画图，可以发现，当key是中位数，而数组中有8个元素的时候，继续递归的话，要继续递归3次，而这三次，恰好就是最后那占用了百分之87.5的次数，因此，我们可以通过判断，元素个数是否为8，如果是，那就不递归了。我们直接使用直接插入排序。
因此，在递归的时候，我们可以把代码改写成
?
②挖坑法
挖坑，就是用这个坑来分割左右区域。思路与hoare版本类似，但是细节不一样。也比较容易理解。
先将选取好的key值记录保存起来，然后将这个key值所在的数组下标作为坑，这个坑可以覆盖，因为key已经保存好了。
先让一边开始走，走到需要的位置后，比如先让右边走，走到比key值要小的位置，那么右边所处的下标的值就赋值给坑，再让坑移动到右边所处的位置。
然后让左边走，走到比key要大的值后，将这个值赋给坑，坑再移动到左边的这个位置。
依次循环，直到两边相撞。相撞的位置，将key拿过来。单趟排序完成。
?③前后指针法
通过两个指针，prev和cur。
cur找比key小的值，而prev先不动。当cur找到比key小的值后，perv++，交换prev和cur的位置的值。为什么prev要++？这里是有两种情况的，cur找到小值后，刚好是在prev的前面，然后prev++，再交换的话，就是这个小值自己跟自己交换。第二种情况就是，cur找到小值后，prev前面的都是大值，然后perv++，此时的prev的位置的值就是大的值，再跟cur的位置的小值交换，就能达到小的往左边放，大的往右边放的目的了。
?
3.2.2 非递归方法
我们可以使用数据结构中的栈来实现非递归的方法?。每次入栈，都是将begin和end两个先入栈。然后出栈，每出一次栈，将其作为最左右两个下标来计算中间值并进行分割排序。拿到这个中间值后，就将这个数组划分成? ?[left, keyi-1]? ? keyi? ? [keyi+1,right]三个区域，然后再将他们各自的区域的begin和end入栈。当栈不为空，出栈，依次进行相同的操作，直到栈为空，排序也就完成了。
?这就是快速排序啦！
未完待续......等我学了剩下的再来总结吧！
?