常见的排序算法1

排序：把无序的序列，变成有序（递增/升序，递减/降序）

排序的时候，指定升序/降序，最关键的就是指定“比较规则”

1 直接插入排序

类似于顺序表的插入效果（把元素往后倒腾啥的），但这里的关键是让新元素插到位置上，保持仍然有序

这里是升序排序

思路：

1）定义一个bound变量，把整个数组划分成两个区间，已排序区间为[1,bound)，待排序区间为[bound,size)

已排序区间不是从0开始的原因：第一个元素其实就已经是有序了，它就一个元素

2）取bound位置的元素，往前面这个已排序区间插入，插入到合适位置（插入之后，整个数组还是有序的）

3）经过一轮的插入之后，已排序区间多一个元素，未排序区间少一个元素

比如：

之后以此类推

代码：

运行结果：

它的时间复杂度为O(N^2)，空间复杂度为O(1)

稳定性：稳定（两个元素值相同，排序后这两个元素的相对顺序和排序前是一样的）

2 希尔排序

希尔排序也叫谢尔排序，英文术语为shell

它针对插入排序做了一个改进，对于插入排序来说，有两个特殊的情况：
1）如果序列本身很短，进行插入排序速度就很快 （gap值大的时候，每个分组里的元素都很少）

2）如果序列本身基本有序，插入排序速度也很快 （gap比较小，甚至到1的时候，虽然分组中的元素多了，但是经过前面的调整，基本有序了）

红颜色的字就解释了希尔排序快的原因

希尔排序就针对这两个特点进行了改进，它把整个数组进行分组，分成若干组，之后再对每个组分别进行插入排序。设置了一个变量：gap，通过gap进行分组操作

比如：

希尔排序的时间复杂度，不确定，它取决于gap的序列怎么取。刚才gap取的是3，2，1，效率比较低。一个典型的序列，效率比较高,gap为: size/2,size/4,size/8……1。希尔排序的效率最高能达到O(N^1.3)。

它的空间复杂度为O(1)，它不是稳定排序，因为相同的值，可能在不同的分组中，每个组内部插排是稳定的，组和组之间就不一定了。

代码：

这里解释一下为什么是bound++，而不是bound+=gap，因为是对所有分组进行插入排序，也就是说，把整个数组里面的元素都进行插入排序操作。不是说把一个分组处理完，再处理下一个分组，而是直接“水平的处理”：
先处理0号分组的1号元素

再处理1号分组的1号元素

再处理2号分组的1号元素

运行结果：

3 直接选择排序

核心思路类似于找“最大值”/“最小值”

按照打擂台的方式：
第一轮找出最小值，放到数组最前面

第二轮找出第二小的值，放到第二个位置上

第三轮找出第三小的值，放到第三个位置上

……

第N-I轮，找到第N-1小的值

代码：

运行结果：

它的时间复杂度为O(N^2)，空间复杂度为O(1)，是不稳定的，如果交换都是相邻的是稳定的，跨距离就不稳定了。