顺序插入排序顺序插入排序算法将待排序元素，从后向前寻找适当的插入位置，直到所有元素都插入为止25*初始25*第1步插入25，25≥21，无需移动25*第2步插入49，49≥25，无需移动25*第3步插入25*，25*<49，25*49后移，25*填入25*第4步插入16，16<49,25*,25,21，25*49,25*,25,21后移，16填入25*第5步插入08，08<49,25*,25,21,1625*49,25*,25,21,16后移，08填入6
顺序插入排序 ◼ 顺序插入排序算法 将待排序元素，从后向前寻找适当的插入位置，直 到所有元素都插入为止 6 初始 25* 第1步 25* 第2步 25* 第3步 25* 第4步 25* 第5步 25* 插入25，25 ≥ 21，无需移动 插入49，49 ≥ 25，无需移动 插入25* ，25* < 49， 25* 插入16，16 < 49,25*,25,21， 25* 25* 插入08，08 < 49,25*,25,21,16， 49后移，25*填入 49,25*,25,21后移，16填入 49,25*,25,21,16后移，08填入
顺序插入排序算法分析最好情况（n个元素）原数据是按小到大顺序排好的每步只需与前一个数据比较一次，而不用移动数据总比较次数n-1，总移动次数0口最坏情况(n个元素,i=0,1....,n-1）原数据按大到小顺序排好的元素需要比较次，每比较1次移动1次，元素移动2次总比较次数和总移动次数temp = a[i]i= n(n -1)/2 ~n’/2,KCN =a[0] = tempi=1岁比较和移动最坏最好平均值约为n2/4RMN=(i+ 2) = (n +4)(n -1)/2 ~ n2/2时间复杂度O（n2）i=1
顺序插入排序 ◼ 算法分析 最好情况(n个元素) ➢ 原数据是按小到大顺序排好的 ➢ 每步只需与前一个数据比较一次，而不用移动数据 ➢ 总比较次数n-1，总移动次数0 最坏情况(n个元素,i=0,1,.,n-1) ➢ 原数据按大到小顺序排好的 ➢ 元素i需要比较i次，每比较1次移动1次，元素i移动2次 ➢ 总比较次数和总移动次数 − = − = = + = + − = = − n 1 i 1 2 n 1 i 1 2 RMN (i 2) (n 4)(n 1)/2 n /2 KCN i n(n 1)/2 n /2, temp = a[i] a[0] = temp 比较和移动最坏最好平均值约为n2 /4 时间复杂度O(n2 )
顺序插入排序算法分析口是稳定的算法，key相同元素原来的顺序不会打乱25*初始25*排序后需要额外一个存储空间temp =a[i]a[0] = temp8
顺序插入排序 ◼ 算法分析 是稳定的算法，key相同元素原来的顺序不会打乱 需要额外一个存储空间 8 初始 25* 排序后 25* temp = a[i] a[0] = temp
折半插入排序折半插入排序算法将待排序元素，按折半搜索法寻找适当的插入位置，直到所有元素都插入为止25*25*不不不midhighlowmidhighlowmid>23,high=mid-1,mid=(low+high)/2low>high，49,25*,25后移，23填入25*25*杯个low mid highmid≤23,low=mid+1,mid=(low+high)/225*大个凡.low mid highmid≤23,low=mid+1,mid=(low+high)/2
折半插入排序 ◼ 折半插入排序算法 将待排序元素，按折半搜索法寻找适当的插入位置 ，直到所有元素都插入为止 9 25* low>high，49,25*,25后移，23填入 25* low mid high 25* low mid high 25* low mid high mid>23,high=mid-1,mid=(low+high)/2 mid≤23,low=mid+1,mid=(low+high)/2 25* mid high low mid≤23,low=mid+1,mid=(low+high)/2
折半插入排序算法分析口平均情况下，折半搜索比顺序搜索快搜索元素i需比较Llog2il+1次口总比较次数Z(og,i+1)=++2+2+3++3.++k20i=12124-12=1*2°+2*2' +3*2’+..+k*2k-1=(k -1)* 2* +1 = n *(log,n -1)+1 =n *log2n -n +1比较的时间复杂度O（n*log2n）移动的时间复杂度O(n2)10是稳定的排序算法，需额外一个存储空间7
折半插入排序 ◼ 算法分析 平均情况下，折半搜索比顺序搜索快 搜索元素i需比较log2 i +1次 总比较次数 移动的时间复杂度O(n2 ) 是稳定的排序算法，需额外一个存储空间 10 0 1 2 k 1 2 n 1 i 1 2 2 2 ( log 2 i 1 ) 1 2 2 3 3 k k k − + = + + + + + + + + + + − = (k 1 ) * 2 1 n * (log n 1 ) 1 n * log n n 1 1* 2 2 * 2 3 * 2 k * 2 2 2 k 0 1 2 k 1 = + = + = − + = + + + + − - - 比较的时间复杂度O(n*log2n)