直接插入排序性能分析:
时间复杂度:O(N^2)，最好情况当数据本来就有序时可以做到O(N)；
空间复杂度:直接插入排序并没再开过一段连续的空间所以为O(1)；
完整代码如下，我们看到while循环中的判断即是让tmp小于的数据 不断向前覆盖 直到找到小于tmp的数据 或者 end小于0(前面没有可比较的数据)时 跳出循环将数据插入。
希尔排序性能分析:
时间复杂度:最坏O(N^ 2) ,平均在<数据结构>严蔚敏中给出O(N^1.3);
空间复杂度:O(1);
完整代码如下，如有疑问随时私信或者在评论区提出。
选择排序性能:
时间复杂度:O(N^2);
空间复杂度:O(1);
正确代码如下:
堆排序在之前我就写过文章讲解，这里就不赘述了。需要注意的是:排升序、建大堆，排降序、建小堆文章堆和堆排序的链接
选择排序性能:
时间复杂度:O(N^2);
空间复杂度:O(1);
快速排序性能:
时间复杂度:O(N*logN)最坏O(N^2)
空间复杂度:O(1);
此版本需要注意的是如果将左边第一个作为基准值就需要让右边先走，需要小于基准值的数据，相反就让左边先走。
我们知道快速排序的效率是很高的，特别是处理无序的数据时，但是当数组为有序时，时间复杂度就会下降到O(N^2),这是因为我们总是将第一个数据作为基准值导致的。这里就有个优化的方法———三数取中———它将比较mid left right的数据，取中值作为基准值，使得即使数据有序，效率也不会太差。
（1）快速排序非递归
上文快速排序的三个版本都使用了递归，当数据量过大，建立的栈帧空间过多时，容易产生栈溢出，导致错误。所以我们要学习 将代码从递归改为非递归避免错误 是以后我们工作的必备技能。
快速排序的非递归需要使用到栈 使用栈辅助改为循环。
如何利用栈将快排改为循环呢？我们将数组左右下标压入栈，为了出栈顺序为先左后右，我们则要先压右下标，再压左下标。然后当栈非空时就 继续弹出区间给快排函数排序，当左右区间数据少于1时停止压栈。
归并排序性能:
时间复杂度:O(N*logN)；
空间复杂度:O(N);归并排序需要的辅助空间较多，所以常用于解决磁盘的外排序问题。
完整代码如下:
（2）归并排序非递归
而且非递归版本不想递归有mid，便于控制区间，其区间的控制需要理解:
到这里我们就不免有个疑问，不同于上图所示，如果数据为奇数，不能正好的分区间，那该怎么办呢？
我们则需要在区间控制后，再判断一下区间是否越界以及相关的处理。
- end1就越界了，begin2和end2肯定也就越界了，这时只有左区间的部分数据有效，所以无法进行比较＋排入，所以这时的gap是错误了，此次循环不进行直接。
- begin2和end2越界时，这时只有左区间有效，无法进行比较＋排入与第一种情况相同直接
- 最后一种情况只有end2越界了，我们只需将end2赋为正常区间之内即可。
调整代码如下:
完整代码如下:
上面的代码是归并一部分就拷贝一部分，也可以在for循环外一次性拷贝进去，一次性拷贝对区间的控制更为麻烦，这里就不过多赘述。感兴趣的可以在我的gitee中找到代码匿名者Unit码云
计数排序属于非比较排序，适合范围集中，并且范围不大的整形数组排序。
计数排序性能:
时间复杂度:O(N+range)；
空间复杂度:O(range);
完整代码如下: