一、直接插入排序由于直接插入排序和希尔排序是插入排序类，所以将其分类为模块。
插入排序是指将数组的当前元素插入到该元素之前的有序序列中。 也就是说
通过从头到尾遍历数组，在第一个有序数组的相应位置依次插入元素，然后从头到尾遍历元素，可以确保在遍历元素时上一个数组是有序的具体步骤。
从头到尾遍历数组元素，然后从当前元素开始顺序遍历数组，找到小于元素值的元素数组索引，将索引移动到当前元素索引之间的数组中，最后将当前元素插入有序数组中的特定代码。
vectorintinsertsort (vectorintarr ) { int tmp； int i，j； for(I=1； i arr.size (； I ) { int k=i； //找到小于前一有序数列的arr[i]的索引for (j=I； j=0； j--}{if(arr[j]=arr[I]}{k=j； } else break； (if ) I！=k () { tmp=arr[i]； //将数组放在后面输入for(j=I-1； j=k； j--(arr[j1]=arr[j] )； arr[k]=tmp； } } return arr； }复杂度分析：
在最佳情况下，排序有序，不需要向后移动，时间复杂度在o(n )最坏的情况下，排序为相反顺序，比较次数为(n 2 ) ) n-1 )/2，移动次数为(n 4 ) ) n-1 )/2概率相同可以说是直接插入排序的升级版本。
希尔排序的关键是利用分治的思想，通过将数组的一部分增量分组为一个子串实现跨越式移动，通过逐步缩小增量组，使整体数组有序化。 具体步骤：
选择增量增量索引=length/31，直接插入间距为increment的子数组进行排序。 increment=increment/3 1重复循环，直到increment=1。 具体代码：
vectorintmysort(vectorintarr ) { //write code here int tmp； int i，j； int increment=arr.size (； do { increment=increment/3 1； for(I=increment； i arr.size (； I=Iincrement(intk=I； //找到小于前一有序数列的arr[i]的索引for (j=I； j=0； j=j - increment () if ) arr[j]=arr[I] ) k=j； } else break； (if ) I！=k () { tmp=arr[i]； //将数组放在后面，输入for(j=I-increment； j=k； j=j-increment (arr [ j increment ]=arr [ j ] )； arr[k]=tmp； }}while(increment1)； 返回区域； }增量值是可选的，但最后一个增量必须为1