1插入排序(算法3-5) ●(1)基本思想:将n个元素的数列分为已有序 和无序两个部分。 {al},{a2,a3 a 4 ss, an {a1 a2( },{a3①,a4 an fal 2 },{anm1)}} 有序 无序 每次处理:将无序数列的第一个元素与有序数 上一页 列的元素从后往前逐个进行比较,找出插入位 置,将该元素插入到有序数列的合适位置中。 停止放映 从前往后,若比ai小,则放在ai前面 下一页 从后往前,若比ai大,则放在ai后边。 第11页下一页 上一页 停止放映 第 11 页 1.插入排序（算法3-5） ⚫ (1)基本思想： 将n个元素的数列分为已有序 和无序两个部分。 {{a1}，{a2，a3，a4，…,an}} {{a1 (1) ，a2 (1) }，{a3 (1) ，a4 (1) …,an (1) }} …... {{a1(n-1) ，a2(n-1) ，…}, {an(n-1)}} 每次处理：将无序数列的第一个元素与有序数 列的元素从后往前逐个进行比较,找出插入位 置,将该元素插入到有序数列的合适位置中。 从前往后，若比ai小，则放在ai前面 从后往前，若比ai大，则放在ai后边。 有序 无序