个插入排序方法 Our first algorithm, insertion sort, solves the sorting problem introduced in Chap- ter l Input: A sequence of n numbers (a1, a2,..., an) Output: A permutation (reordering)(a'.d,,..., a" )of the input sequence such that a 1<
一个插入排序方法
插入法: 在“插入每张 牌前,手上的 牌都是已经排 好序的
插入法： 在“插入每张 牌前，手上的 牌都是已经排 好序的
范例 总是已绎排好序的片段 国b 总是已经排好序的片段
范例 总是已经排好序的片段 总是已经排好序的片段
伪代码 提请注意:你应 Ⅰ NSERTION-SORT(4) 该会证明这个算 I for j= 2 to A length 法的正确性! //Insert A[i into the sorted sequence A[..j-1 5 while i>0 and Ai> key Ali+1=Ai 8A1+1]=key
伪代码 提请注意：你应 该会证明这个算 法的正确性！
算法的性能度量模型 算法性能涉及 口空间性能(空间复杂度) ■算法在给定合法输入的情况下,要消耗多少“临时”存储空间 口局部变量、过程调用的堆栈空间等 ■特定场合中较为关注 口时间性能(时间复杂度) ■算法在给定合法输入的情况下,需要执行多少时间 重点关注内容! 算法的时间复杂度模型 口执行指令条数的统计模型:数数字!
算法的性能度量模型 ◼ 算法性能涉及 ❑ 空间性能（空间复杂度） ◼ 算法在给定合法输入的情况下，要消耗多少“临时”存储空间 ❑ 局部变量、过程调用的堆栈空间等 ◼ 特定场合中较为关注 ❑ 时间性能（时间复杂度） ◼ 算法在给定合法输入的情况下，需要执行多少时间 ◼ 重点关注内容！ ◼ 算法的时间复杂度模型 ❑ 执行指令条数的统计模型：数数字！