一个插入排序方法 Our first algorithm,insertion sort,solves the sorting problem introduced in Chap- ter 1: Input:A sequence of n numbers (a.a2.....an). Output:A permutation (reordering)(aa2.....a of the input sequence such that a≤a2≤…≤an
一个插入排序方法
插入法： 在“插入每张 牌前，手上的 % 牌都是已经排 4 10 品 好序的” 云 品 坐
插入法： 在“插入每张 牌前，手上的 牌都是已经排 好序的
范例 总是已经排好序的片段 123 456 123456 1 23145 6 (a) 524613 (b) 254613 (c) 245613 总是已经排好序的片段 123456 123 456 12 3456 (d) 245 6 1 3 (e) 12 4 563 (f) 12 3456
范例 总是已经排好序的片段 总是已经排好序的片段
伪代码 提请注意：你应 INSERTION-SORT(A) 该会证明这个算 1 for j=2 to A.length 法的正确性！ 2 key =Alj] 3 /Insert A[j]into the sorted sequence A[1..j-1]. 4 i=j-1 5 while i >0 and A[i]>key 6 A[i+1]=A[] 7 i=i-1 8 Ali 1]key
伪代码 提请注意：你应 该会证明这个算 法的正确性！
用哪些数值来标定算法的性能？ ■时间性能（时间复杂度） 口算法在给定一个输入的情况下，要执行多少条指令 没错，数数字！
用哪些数值来标定算法的性能？ 时间性能（时间复杂度） 算法在给定一个输入的情况下，要执行多少条指令 没错，数数字！