排序把无序的序列变成有序递增/升序递减/降序排序的时候指定升序/降序最关键的就是指定“比较规则”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取的是321效率比较低。一个典型的序列效率比较高,gap为: size/2,size/4,size/8……1。希尔排序的效率最高能达到O(N^1.3)。它的空间复杂度为O(1)它不是稳定排序因为相同的值可能在不同的分组中每个组内部插排是稳定的组和组之间就不一定了。代码这里解释一下为什么是bound而不是boundgap因为是对所有分组进行插入排序也就是说把整个数组里面的元素都进行插入排序操作。不是说把一个分组处理完再处理下一个分组而是直接“水平的处理”先处理0号分组的1号元素再处理1号分组的1号元素再处理2号分组的1号元素运行结果3 直接选择排序核心思路类似于找“最大值”/“最小值”按照打擂台的方式第一轮找出最小值放到数组最前面第二轮找出第二小的值放到第二个位置上第三轮找出第三小的值放到第三个位置上……第N-I轮找到第N-1小的值代码运行结果它的时间复杂度为O(N^2)空间复杂度为O(1)是不稳定的如果交换都是相邻的是稳定的跨距离就不稳定了。