1 .插入排序插入排序的基本思想：插入排序是最简单的排序思想，它的思想是将一个数据插入到一个有序的数据列表，得到一个新的有序列表。
插入排序类型是将我们结束的扑克、卡片ttdkn张插入我们的排列中，形成有序的排列。
插入对数组9 1 2 5 7 4进行整形排序的过程。 蓝色箭头指向的值是tmp值。 紫色箭头是插入tmp的位置。
插入与排序对应的代码：
voidinsert(intarr[]，int n ) ) for ) intI=0； i n； I//插入排序的次数{int end=i； //指向有序序列结束的指针int tmp=arr[end]； //蓝色箭头所指的值while(end-1=0arr[end-1]tmp ) {arr[end]=arr[end - 1]； //结束数据； }arr[end]=tmp； //在正确的位置插入数据}}插入排序的时间复杂度。 如果一个序列完全有序(例如，如果该序列为12-3-45……)，那么由于此时的排序的插入时间复杂度为o(n )，因此该序列越接近有序，时间复杂度为o(n )； 如果序列完全相反，例如序列5(4)3)2)……，则每次遍历前一个时间的复杂度必须插入到o(n^2)中，但时间复杂度是按最坏的情况去考虑的，所以插入排序的时间复杂度为O(N^2).
2 .希尔排序
希尔排序也称为“缩小增量排序”，是一种插入排序方法，但比直接插入排序的时间效率更高。
其基本思想首先是将整个待排序列分成若干子序列分别进行直接插入排序，待整个序列中记录”基本有序时“在对整个序列进行一次直接插入排序
在数组中使用9 1 2 5 7 4 8 6 3 5，来看看希尔排序是如何有序排列这个数组的。
的gap为每一趟中的子序列之间的间隔对每个子序列进行插入排序，在一个排序完成后进行下一个排序，当gap逐渐缩小时，序列也趋于有序，当gap减少到1时，然后soso 当gap较大时，序列排序较快，当gap较小时，排出的序列接近有序。当gap为1时相当于插入排序，此时序列已经接近有序了，所以该插入排序的时间复杂度接近O(n).
插入已排序的代码：
//希尔排序voidshellsort(intarr )，int n ) intgap=n； //gap是子序列的间隔while(gap1) gap=gap/31； //gapfor不断变小(intI=0； i n - gap； I ) )//进行每圈的排序({ int end=i； //子序列每1圈插入排序//子序列内的数据插入排序int tmp=arr[end gap]； while(end=0arr[end]tmp ) { arr[end gap]=arr[end]； end -=gap； } arr[end gap]=tmp； }}希尔排序代码分析： 1. gap=gap/3+1,
各圈的gap持续缩小为3倍，加1可以防止最后一圈的gap变为0。 这是因为在最后的第二次gap为2的情况下，除了3以外，最终回合在2/3的情况下为0。
2.
int end=i；
int tmp=arr[end gap]；
while(end=0arr[end]tmp ) )。
{
arr[end gap]=arr[end]；
end -=gap；
}
arr[end gap]=tmp；
分类各趟中的部分系列的插入，将部分系列中的间隔作为gap，移动将gap的位置向后偏移。
对应于下一个子序列的插入过程。 类型插入排序只是每个数据之间的间隔为gap。 插入排序的gap
3.for (int i = 0; i n - gap; i++)
原因是对每个子序列进行插入排序，以确保所有子序列都是有序的。 此时，如果我们遍历整个序列，调查I指向哪个值，就会出现与I对应的子序列。 在子序列中，将I的下一位值插入有序子序列中，从I到列n-gap结束。 如下图所示。
希尔排序的时间复杂性：希尔排序中的分析是一个复杂的问题。 因为，其时间复杂度是可取的“增量”序列的函数，它涉及到一些数学上尚未研究的难题，至今无人寻求最高增量序列，但许多研究表明其时间复杂度为o(n^ ) (3/2)
可以估算希尔排序的最差时间复杂度：
首先计算for循环的时间复杂度，
当gap较大时，由于几乎没有中的while循环，所以for循环为o(n )、
.
gap变小的话，本来是插入分类，但是由于排列中已经接近秩序，所以插入分类接近o(n )
计算while(gap1)的时间复杂度
n/3/3/3 .=1
3^x=n，x是循环的次数，所以while的时间复杂度为o(log3n )
因此，希尔排序最差的时间复杂度可能是o () log3n ) (n ) )，该算法比插入排序更快。