衡量排序方法的标准 排序时所需要的平均比较次数 排序时所需要的平均移动 排序时所需要的平均辅助存储空间
衡量排序方法的标准 ▪ 排序时所需要的平均比较次数 ▪ 排序时所需要的平均移动 ▪ 排序时所需要的平均辅助存储空间
插入排序( Insert Sorting) 插入排序的基本方法是:每步将一个待排序的对 象,按其关键字大小,插入到前面已经排好序的 组对象的适当位置上,直到对象全部插入为止。 直接插入排序( nsert Sort 直接插入排序的基本思想是:当插入第i(≥1)个对象 时,前面的V10,Ⅵ,,v1已经排好序。这时,用 v引的关鍵字与叫l,v2],的关键字顺序进行比较 找到插入位置即将v插入,原来位置上之后的所有对 象依次向后顺移
插入排序 (Insert Sorting) 直接插入排序的基本思想是：当插入第i (i 1) 个对象 时，前面的V[0], V[1], …, v[i-1]已经排好序。这时，用 v[i]的关键字与v[i-1], v[i-2], …的关键字顺序进行比较， 找到插入位置即将v[i]插入，原来位置上之后的所有对 象依次向后顺移。 插入排序的基本方法是：每步将一个待排序的对 象，按其关键字大小，插入到前面已经排好序的 一组对象的适当位置上，直到对象全部插入为止。 直接插入排序 (Insert Sort)
各 趟 排 21 25//49 25 608 序 012345 结 果 =1目 49 25 6(8 25 2 3 5 temp 49 i=2 2125 08 012345 tem
各 趟 排 序 结 果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 1 25 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2
49 i=3 2125 608 25 012345 4同园回同 0123 5 temp 5同 21 252549 b 012345 tem
21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 i = 4 08 0 1 2 3 4 5 temp 21 25 49 16 25* 08 i = 5 i = 3 25* 16 08
完成08(16 25|2s449 012345 i=4时的排序过程 j=3 2525449 08 012345 ten j=2 212525 49 08 012345 temp
16 49 16 16 21 25 49 16 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 08 i = 4 时的排序过程 0 1 2 3 4 5 temp 21 25 25* 49 完成 16 08 16 i = 4 j = 3 i = 4 j = 2