8.2插入排序插入排序的基本思想是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止简言之，边插入边排序，保证子序列中随时都是排好序的。常用的插入排序有：：直接插入排序和希尔排序两种8.2.1直接插入排序最简单的排序法！1、其基本思想是顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置
8.2 插入排序 插入排序的基本思想是：每步将一个待排序的对象，按 其关键字大小，插入到前面已经排好序的一组对象的适当位 置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 常用的插入排序有：直接插入排序和希尔排序两种。 8.2.1 直接插入排序 1、其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到已排 序数据元素子集合的适当位置。 最简单的排序法！
例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。初始关键字序列：【13】,6, 3,31,9,27,5, 11第一次排序：[6, 13],3,31, 9, 27, 5, 11第二次排序：[3, 6, 13],31, 9, 27, 5, 11第三次排序：[3,6,13,31],9,27,5, 11第四次排序：3, 6, 9, 13, 31] ,27,5, 11第五次排序：[3,6,9,13, 27,31],5,11第六次排序：[3,5,6.9,13,27,31】,11第七次排序：[3,5, 6,9, 11,13, 27.31】注：方括号「1中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移一个位置
初始关键字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11 第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11 第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11 第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11 第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 例1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。 注：方括号[ ]中为已排序记录的关键字，下划横线的关键字 表示它对应的记录后移一个位置
2.直接插入排序算法public static void insertSort(intla)int i, j, temp;int n = a.Length;for(i= 0;i<n - 1;i++)0temp = a[i + 1];j=i;while(j>-1 && temp< a[jl)al[j + 1] = a[i];j --;1a[j +1] = temp;初始关键字序列：【13】,6, 3, 31, 9, 27, 5, 11人第一次排序：[6, 13】,3, 31, 9, 27,5, 11第二次排序：【3, 6, 13】,31, 9, 27,5, 11
public static void insertSort(int[] a){ int i, j, temp; int n = a.Length; for(i = 0; i < n - 1; i ++){ temp = a[i + 1]; j = i; while(j > -1 && temp < a[j]){ a[j + 1] = a[j]; j -; } a[j + 1] = temp; } } 2.直接插入排序算法 初始关键字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11
3、直接插入排序算法分析(1)时间效率：当数据有序时，执行效率最好，此时的时间复杂度为O(n）；当数据基本反序时，执行效率最差，此时的时间复杂度为O(n2)。所以当数据越接近有序，直接插入排序算法的性能越好。(2)空间效率：仅占用1个缓冲单元0(1)(3）算法的稳定性：稳定
(1)时间效率：当数据有序时，执行效率最好，此时的时 间复杂度为O(n)；当数据基本反序时，执行效 率最差，此时的时间复杂度为O(n2)。所以当数 据越接近有序，直接插入排序算法的性能越好。 (2)空间效率：仅占用1个缓冲单元——O（1） (3)算法的稳定性：稳定 3、直接插入排序算法分析
8.2.2希尔（she11）排序（又称缩小增量排序）1、基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量d的记录组成一个小组，让增量d逐趟缩短（例如依次取5,3,1），直到d=1为止。3、优点：让关键学值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多
8.2.2 希尔（shell）排序（又称缩小增量排序） 1、基本思想：把整个待排序的数据元素分成若干个小组，对同 一小组内的数据元素用直接插入法排序；小组的个数逐次缩小， 当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某 个增量d的记录组成一个小组,让增量d逐趟缩短（例如依次取 5,3,1），直到d＝1为止。 3、优点：让关键字值小的元素能很快前移，且序列若基本有序 时，再用直接插入排序处理，时间效率会高很多