参考：
常用排序算法的时间空间复杂度：
一、 冒泡排序
1.原理概述
冒泡排序是遍历整个序列，并相邻两元素两两比较，如果反序就交换位置，最终就将最大的数放到序列末尾。遍历第二次就将倒数第二大的数放到了倒数第二的位置，重复该操作，直到遍历n-1次后，整个序列完成排序。
2.算法实现
使用了一个标志位 int swapped = 0; // 是否发生了交换的标志
作为哨兵，当某次没有出现交换提前结束循环，作为对冒泡排序算法的优化。
二、选择排序
1.原理概述
遍历整个序列，找到最小元素的位置，然后将其放到序列最开始作为已排序序列。然后再从剩余的序列中找到最小的元素放在已排序序列后面。依次类推直到所有元素排列完毕。
选择排序与冒泡排序的区别是：选择排序遍历完整个序列才交换一次；而冒泡排序是两两比较视情况交换，所以每遍历一个元素都可能交换。
2.算法实现
3.算法优化实现(每一趟筛选出未排序的最大最小元素)
三、插入排序
1.原理概述
直接插入排序，也简称为插入排序。基本思想是：假设左边i个元素已经排好序，从i开始，从左向右开始遍历，将遍历到的元素放在已排序列中第一个小于该元素的元素后面。
直接插入排序对于最坏的情况(严格递减的序列)，需要比较和移位的次数为n(n-1)/2;对于最好的情况(严格递增的序列)，需要比较的次数为n-1，需要移位的次数为0。
2.算法实现
插入排序的不足之处：
1、寻找插入位置、移动元素
优化方案：
1、对于已经排序好的序列，使用二分查找算法。（lower_bound()函数）
2、数据链表化
3、希尔排序
四、希尔排序
1.原理概述
希尔排序也是一种插入排序，是在简单插入排序基础上改进的一个高效版本，也称为缩小增量排序。该算法是第一批冲破O(n2)的算法之一。利用了插入排序的最佳时间代价特性，它试图将待排序序列变成基本有序的，然后再用插入排序来完成排序工作。
基本思想是将待排序的数分成多组，对每个组进行插入排序，是数据整体有序，然后调整分组的数据顺序，最后再使用一次插入排序，使数据全部有序。希尔排序在此基础上采用跳跃分组的策略，通过增量(跳跃的量化)将序列划分为若干组，然后分组进行插入排序，接着缩小增量，继续按组进行插入排序操作，直至增量为1。采用这个策略的希尔排序使整个序列在初始阶段从宏观上看就基本有序，小的基本在前面，大的基本在后面。然后缩小增量至增量为1时，多数情况下只需要微调就可以了，不涉及到大量的数据移动。
2.算法实现
五、 快速排序
1.原理概述
快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-onquerMethod)。它的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。
具体算法步骤为：
1、先从待排序数组中找到一个基准数
2、扫描数组，把比基准小的放在他的左边，大的放在右边（得到两个区间）。
3、再对左右区间重复 1 、2的操作。
2.算法实现
快速排序算法优化：
1、选择更加合理的基准数（有效降低递归深度），选取多个数，选择中间的数据。
2、区间元素很少，采用插入排序更加好。
六、 归并排序
1.原理概述
归并排序是利用归并的思想实现的排序方法。该方法采用分治策略(分治法将问题分解为一些小问题，然后递归求解；而治阶段将分段得到的答案合并在一起。实际是将已经有序的子序列合并得到另外一个有序的序列。
具体算法步骤为：
1、先拆分，后合并起来。
这种结构类似于完全二叉树，归并排序需要使用递归或者迭代的方法实现。
分阶段就是递归拆分子序列，递归深度为log2n。治阶段需要将两个已经有序的子序列相互比较再合并。