排序算法

选择排序：

​ 选择排序一般来说就是，我们 始终从中右边的序列中找出那些最小的元素，放在左侧，这样我们就能保证左边始终有序。

​ 但是这个算法的复杂度比较高，为 $$ n^2/2 $$ ​ 那为什么是这个值，假若我们放一张 n x n 的表格，然后我们在排序的过程中用灰色表示不变的元素，然后用黑色表示变化的元素。这样一来我们会发现这个表格是一个以对角线分隔的一个矩阵。很统一看到我们进行了二分之一的 n^2 扫描。

​ 这个算法的另外一个问题就是无论我们的序列本来是否有序，我们都需要不停地扫描，所以说这个不存在最好情况和最坏情况，一直都效率不高。

插入排序：

​ 插入排序的算法过程和选择排序类似，这是这个地方我们始终让左边的序列保持有序，然后把剩下的那些无序的元素一个个插入到有序序列之中。或许你已经明白了整整比较消耗时间的就是插入操作，我们又需要不停地移动着数组。但是这就有一个好处就是当我们序列比较有序的时候我们所做的操作非常少，甚至当序列完全有序的时候我们只需要进行 n 次比较而已。他的算法复杂度比上面的要好一点,为 $$ n^2/4 $$ 同样的我们可以画一个矩阵，最终我们会发现有黑色全部在对角线下面，而且对角线下面只有一半是黑色的，因此就是 1/4

希尔排序：

​ 希尔排序事实上可以看做插入排序的一个变种，他是首先进行了分组，然后在组内进行了插入排序，这样改造后的性能提高了很多。重点就在于如何进行分组的问题，希尔自己提出的方法就是使用 n/3 也就是每一次步长减少 n/3

归并排序：

​ 归并排序是比较有名的排序，这个排序的思想就是归和并，所谓的归就是递归，递归的去求左右子序列。而并就是最后需要合并这些子序列。这个算法一般需要一个辅助数组来支撑，也就是把两个子序列合并成一个新的数组的时候，需要这个辅助数组，最后还需要把他拷贝回去。下面是归并的流程图。

​

​ 除了这种使用递归的方式我们还可以从下到上的进行合并操作，也就是我们合并操作不变，但是把递归改成循环了，这里就用到了双循环，首先两两排序，然后两两合并。有点类似于希尔排序了。但是这种方式的算法复杂度并没有改变依然就是 nlogn

​ 对于这种比较高级的排序我们可以做一定的优化让他们支持所中情况下的排序。首先这个归并排序并不适合于少量的数据，少量的数据的时候我们使用分治循环是很不划算的，我们可以在归并排序前面添加一些判断条件，当数组的容量少于多少的时候我们可以采用插入排序，这样算法更具有通用性。

​