插入排序算法 template <class record> void Insert Sort(Record array[l, int n)t /Aray[]为待排序数组,n为数组长度 Record TempRecord 临时变量 for(int i=1; k<n: i++i /依次插入第个记录 TempRecord= Array[i] //从j始往前寻找记录的正确位置 inti=ⅰ-1 //将那些大于等于记录的记录后移 while ((j>=0)&(TempRecord Array[jD) Array[j+1]= Array[j] /此时j后面就是记录的正确位置,回填 Array[j+1]= TempRecord: “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 插入排序算法 template <class Record> void InsertSort (Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; // 临时变量 for (int i=1; i<n; i++) { // 依次插入第i个记录 TempRecord = Array[i]; //从i开始往前寻找记录i的正确位置 int j = i-1; //将那些大于等于记录i的记录后移 while ((j>=0) && (TempRecord < Array[j])) { Array[j+1] = Array[j]; j = j - 1; } //此时j后面就是记录i的正确位置，回填 Array[j+1] = TempRecord; } }
算法分析 稳定 空间代价:⊙(1) 时间代价: 口最佳情况:n-1次比较,2(n-1)次移动,○(n 口最差情况:⊙(n2) 比较次数为∑1=n(n-1)/2=6(n) 移动次数为∑(+2)=(m-1)n+4)/2=(m2) 口平均情况:o(n2) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 算法分析 ◼ 稳定 ◼ 空间代价：Θ(1) ◼ 时间代价： ❑ 最佳情况：n-1次比较，2(n-1)次移动，Θ(n) ❑ 最差情况： Θ(n2 ) ◼ 比较次数为 ◼ 移动次数为 ❑ 平均情况：Θ(n2 ) 1 2 1 ( 1) / 2 ( ) n i i n n n − = = − = 1 2 1 ( 2) ( 1)( 4) / 2 ( ) n i i n n n − = + = − + =
发现逆序对,则交换? 依次对第ⅰ个记录进行排序 对记录Arry[ 口插入到有序区Aay0.-1的合适位 置 45347812341322964 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 发现逆序对，则交换？ 45 34 78 12 34’ 32 29 64 ◼ 依次对第i个记录进行排序 ◼ 对记录Array[i] ❑ 插入到有序区Array[0..i-1]的合适位 置
二分法插入排序 算法思想: 口在插入第个记录时,前面的记录已经 是有序的了 口可以用二分法査找第ⅰ个记录的正确位 置 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二分法插入排序 ◼ 算法思想： ❑ 在插入第i个记录时，前面的记录已经 是有序的了 ❑ 可以用二分法查找第i个记录的正确位 置
8.2.2Shel排序 直接插入排序的两个性质: 口在最好情况(序列本身已是有序的)下时间 代价为⊙(n) 口对于短序列,直接插入排序比较有效 She排序有效地利用了直接插入 排序的这两个性质 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 8.2.2 Shell排序 ◼ 直接插入排序的两个性质： ❑ 在最好情况（序列本身已是有序的）下时间 代价为Θ(n) ❑ 对于短序列，直接插入排序比较有效 Shell排序有效地利用了直接插入 排序的这两个性质