) G! i- w ]! N; o , R# c% E& H' b l/ |/ H4 `! i, M8 s 当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array的排序码与 3 L% b8 m! I. H) sarray[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array插入,原来位置上的元素顺序后移。! a4 D. t1 L& h( Y$ I" }+ G! Q5 x+ k
" x3 V d0 p& ^- n
升序排列的示例: D* C6 W& y m) I4 I : }( }6 ?1 F1 A6 t$ n , i2 h# [' e% X, X/ b# J8 m5 x % d1 i: \ j. k3 X下面以升序排列为例讲解过程: 1 T' C2 W& J5 O2 G% T. ^* }8 E ' V) e6 ~3 Q* ~1 L% t 原序列中可以分成两个序列,前面的是已排序的有序序列,用一个下标end标志该序列的尾,初始状态下end是0;后面的是还未排序的序列,用一个tmp变量暂存未排序序列首个元素,实际上是通过tmp = arr[end + 1] 实现的,也就是end指向的下一个元素。为什么要用变量暂存end的下一个元素呢?因为有可能涉及到元素后移,比如说,如果arr[end]要比tmp的值大,根据升序,应该把arr[end]的值后移对吧,那要是直接后移就会覆盖掉arr[end + 1],所以在移动前要先把元素暂存到tmp中。在每一次比较后end要递减一下,向前移动。要是tmp比arr[end]要大该怎么操作呢?这时候就说明找到要插入的位置了,把tmp的值插入到arr[end + 1]即可。' \5 G5 w3 l8 n4 V" o2 m$ h
0 {; b" ]3 `) j1 g3 I( R% n$ K' S/ j6 X" B
7 e- b' U! |2 r6 Q; k 可以看出,直接插入排序不可能只有一轮,像前面讲的过程就是一轮的过程,结果就是把未排序序列的首元素插入到了已排序序列中并保持原来的顺序,正如把刚摸到的一张牌按顺序插入到你的手牌中。实际上,一开始序列是全部未排序的,我们可以把第一个元素作为已排序元素,也就是说已排序序列一开始只有一个元素,end值就为0,后面的元素就全部都是未排序序列的了。3 h; }2 M; e! z9 x6 O$ \. u" B) R