//从已排好序部分的尾元素开始向前 //查找待插入位置 While(curr>=l & hold<rec[curr]) rec [curr+1]=rec [currl; CuII rec curr+l]=hold //将待插入元素插到合适的位置
//从已排好序部分的尾元素开始向前 //查找待插入位置 while(curr>=1 && hold<rec[curr]) { rec[curr+1]=rec[curr]; curr--; } rec[curr+1]=hold; //将待插入元素插到合适的位置 } }
算法中,whi1e语句的条件表达式由两部 分组成,∞uxx>=1保证数组下标不会越界 curr不会被减到低于零,rec[curx]保证 有意义),但这样做就会增加一次条件判断。 为了提高效率,我们把待插入元素先放在 临时空间rec[0]中,依次让它和前面的元素 作比较,直到发现其应插入的位置,将其插入 注意rec[O]起到了“哨兵”的作用。因 为 While语句的条件表达式使得curr不会被 减到低于零
算法中，while语句的条件表达式由两部 分组成，curr>=1保证数组下标不会越界 （curr不会被减到低于零,rec[curr]保证 有意义），但这样做就会增加一次条件判断。 为了提高效率，我们把待插入元素先放在 临时空间rec[0]中，依次让它和前面的元素 作比较，直到发现其应插入的位置，将其插入。 注意rec[0]起到了“哨兵”的作用。因 为while语句的条件表达式使得curr不会被 减到低于零
//改进后的直接插入排序 //数组rec为待排序的序列, count为排序元 //素的个数 insertsortsimple (int rec[], int count) t int curr for(int inx=2 inx<=count inx++) //从第二个元素起依次做插入排序 t rec[o]=rec [inx]i curr=inx-1
//改进后的直接插入排序 //数组rec为待排序的序列，count为排序元 //素的个数 insertSortSimple(int rec[], int count) { int curr; for(int inx=2; inx<=count; inx++) //从第二个元素起依次做插入排序 { rec[0]=rec[inx]; curr=inx-1;
//从已排好序部分的尾元素开始向前 //查找待插入位置 While(rec [o]<rec [curr]) t rec [curr+l]=rec [currli cu了 rec [curr+l]=rec[o] //将待插入元素插到合适的位置 从 While语句的条件表达式得知直接插入 排序是稳定的排序算法
//从已排好序部分的尾元素开始向前 //查找待插入位置 while(rec[0]<rec[curr]) { rec[curr+1]=rec[curr]; curr--; } rec[curr+1]=rec[0]; //将待插入元素插到合适的位置 } } 从while语句的条件表达式得知直接插入 排序是稳定的排序算法
分析算法中元素比较与移动的次数 如果每轮待插入的元素都是在已排好序 部分中的最大元素,那么每轮比较次数只有 次(只和已排好序部分的尾元比较一次), 而且不用移动元素。N个元素的序列只做了 N-1轮的操作,所以标准操作次数T=(N- 1)为1+(N-1)*0=N-1=0(N),显然这种方 式对应的情况是原序列已经是升序
分析算法中元素比较与移动的次数 如果每轮待插入的元素都是在已排好序 部分中的最大元素，那么每轮比较次数只有 一次（只和已排好序部分的尾元比较一次）， 而且不用移动元素。N个元素的序列只做了 N-1轮的操作，所以标准操作次数Tmin=(N- 1)*1+(N-1)*0=N-1=O(N)，显然这种方 式对应的情况是原序列已经是升序