数据结构第章排序插入排序和交换排序.pptxVIP

数据结构 Data Structures;第10章 内部排序;概述;概述;概述;插入排序;;直接插入排序;直接插入排序性能分析 ;直接插入排序性能分析 ;折半插入排序;例：有6个记录，前5个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42 [ 15 27 36 53 69 ] 42 [ 15 27 36 53 69 ] 42 [ 15 27 36 42 53 69 ] ;折半插入排序算法 ;折半插入排序算法分析 ;2-路插入排序 ;2-路插入排序 ;【初始关键字】 49 38 65 97 76 13 27 49 排序过程中d 的状态如下： i=1: (49) i=2: (49) (38) i=3: (49 65) (38) i=4: (49 65 97) (38) i=5: (49 65 76 97) (38) i=6: (49 65 76 97) (13 38) i=7: (49 65 76 97) (13 27 38) i=8: (49 49 65 76 97) (13 27 38);void Path2Insertion(SqList L, SqList d){ d[0] = L[1];//L中D的第一个记录为d中排好序的记录。 int first = 0, final = 0;//first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 for (int i = 2; i = length; ++i) { //依次将L的第2个～最后一个记录插入d中。 if (L[i] d[first]) { //待插入记录小于d中最小值，插入到d[first]之前(不需移动d数组) first = (first - 1 + length) % length; d[first] = L[i]; } else if (L[i] d[final]) { //待插入记录大于d中最小值，插入到d[final]之后 final = final + 1; d[final] = L[i]; } else { //待插入记录大于d中最小值，小于d中最大值，插入到d的中间(需要移动d数组) int j = final ++;//移动d尾部元素以便按序插入记录。 while (L[i] d[j]) { d[(j + 1) % length] = d[j]; j = (j - 1 + length) % length; } d[j + 1] = L[i]; } }