1.直接插入排序 直接插入排序是一种最简单的排序算法，它的基本操作是将一个记录插入到已经排序好的序列中，从而得到一个新的有序表。直接插入排序算法原理如下图所示：
直接插入排序算法如下：
void InsertSort(int arr[],int length){ int key,j; for(int i=1;i<length;++i) {key=arr[i]; //记录标志;j=i-1;//循环比较并且交换相邻的两个数;while (j>=0&&arr[j]>key){arr[j+1]=arr[j];j=j-1;}arr[j+1]=key; }}
插入排序的算法复杂度分析：从空间的角度来看，它需要一个记录的辅助空间，从时间的角度上来看，排序的基本操作：比较两个关键字的大小和移动记录。从算法中可以看出，for循环的次数取决于待插入关键字与前面i-1个关键字的关系。在整个排序过程中，当待排序的序列中记录按关键字按从小到大正序排列时，只需进行n-1次比较，比较次数达到最小值，记录不需要进行移动。反之，当待排序的序列是按逆序进行排列时，总的比较次数达到了最大值（n+2）（n-1）/2。记录移动的次数也达到了最大值（n+4）（n-1）/2。我们可以取最小值和最大值的平均值，则比较次数和移动记录次数约为n^2/4。因此，直接插入排序的算法复杂度为O（n^2）插入排序中相同的元素排序前后的位置不会发生改变，因此直接插入排序是一种稳定的排序方式。
2.希尔排序 希尔排序又称”缩小增量排序“它也属于插入排序类方法，但在时间效率上较前述直接插入排序方法有较大的改进。在进行插入排序时，如果全部是正序时，其时间复杂度为O（n）。 因此，如果待记录序列”基本有序“时，直接插入排序的效率可大大提高。希尔排序的基本思想：先将整个待排记录序列分割成为若干了子序列分别进行插入排序，待整个序列”基本有序“时，再对全体记录进行一次直接插入排序。希尔排序的过程如下图：
希尔排序的算法思路：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，，最后使用直接插入排序完成排序。 希尔排序算法描述如下：
void ShellSort(int arr[],int length){(gap = length / 2; gap > 0; gap = gap / 2){//进行gap次排序;for (int i = 0; i < gap; i++){//一次插入排序;for (int j = i + gap; j < length; j = j + gap){if (arr[j] < arr[j – gap]){int temp = arr[j];int k = j – gap;while (k>=0&&arr[k]>temp){arr[k + gap] = arr[k];k = k – gap;}arr[k + gap] = temp;}}}}}
希尔排序的算法复杂度计算是一个复杂的过程，到目前为止还未找到一种最好的”增量“序列函数。平均情况下希尔排序的算法复杂度为O（n^1.3）由于在希尔排序中会根据增量来进行局部排序，因此相同的元素在希尔排序前后位置会发生改变，因此希尔排序是一种不稳定的排序。
3.总结 排序算法是算法的基础，只有多了解算法的基础，才会对算法有更深的了解，本篇博客主要是为了更加深入的了解排序算法中的插入排序，如果有什么不妥之处，望大家多多指教。
福报不够的人，就会常常听到是非；
