Shel1排序算法思想 m先将序列转化为若干小序列,在这些小序列 内进行插入排序 逐渐扩大小序列的规模,而减少小序列个数 使得待排序序列逐渐处于更有序的状态 ■最后对整个序列进行扫尾直接插入排序,从 而完成排序 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 Shell排序算法思想 ◼ 先将序列转化为若干小序列，在这些小序列 内进行插入排序 ◼ 逐渐扩大小序列的规模，而减少小序列个数， 使得待排序序列逐渐处于更有序的状态 ◼ 最后对整个序列进行扫尾直接插入排序，从 而完成排序
shel排序动画 45347812341322964 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 shell排序动画 45 34 78 12 34’ 32 29 64
增量每次除以2递减”的Shel排序 template <class record> void ShellSort(Record Array[], int n) /5hel排序,Aray[为待排序数组,n为数组长度 int i, delta /增量de|ta每次除以2递减 for(delta= n/2; delta>0; delta /=2) for(i=o: i< delta; i++) ∥分别对deta个子序列进行插入排序 /“&传 Array的地址,数组总长度为n-i ModIns Sort(&Array[i], n-i, delta 如果增量序列不能保证最后一个deta间距为1 可以安排下面这个扫尾性质的插入排序 / ModIns Sort(Array, n, 1) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 “增量每次除以2递减”的Shell 排序 template <class Record> void ShellSort(Record Array[], int n) { // Shell排序，Array[]为待排序数组，n为数组长度 int i, delta; // 增量delta每次除以2递减 for (delta = n/2; delta>0; delta /= 2) for (i = 0; i < delta; i++) // 分别对delta个子序列进行插入排序 //“&”传 Array[i]的地址，数组总长度为n-i ModInsSort(&Array[i], n-i, delta); // 如果增量序列不能保证最后一个delta间距为1 // 可以安排下面这个扫尾性质的插入排序 // ModInsSort(Array, n, 1); }
针对增量而修改的插入排序算法 template <class Record> void ModIns Sort(Record Array[l, int n, int delta)t ∥/修改的插入排序算法,参数 delta表示当前的增量 int for (i= delta; i< n; i+= delta) ∥/对子序列中第个记录,寻找合适的插入位置 for gj=i; j>= delta;j-= delta)t 1/j以deaa为步长向前寻找逆置对进行调整 计f(Arcy[]<Aray- delta])1/逆置对 sWap(Aray,、j,j- delta)://交换 else break “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 针对增量而修改的插入排序算法 template <class Record> void ModInsSort(Record Array[], int n, int delta) { // 修改的插入排序算法，参数delta表示当前的增量 int i, j; for (i = delta; i < n; i += delta) // 对子序列中第i个记录，寻找合适的插入位置 for (j = i; j >= delta; j -= delta) { // j以dealta为步长向前寻找逆置对进行调整 if (Array[j] < Array[j-delta]) // 逆置对 swap(Array, j, j-delta);// 交换 else break; } }
算法分析 不稳定 空间代价:Q(1) 增量每次除以2递减,时间代价:O(n2) ■选择适当的增量序列,可以使得时间代 价接近Q(n) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 算法分析 ◼ 不稳定 ◼ 空间代价：Θ(1) ◼ 增量每次除以2递减，时间代价：Θ(n2 ) ◼ 选择适当的增量序列，可以使得时间代 价接近Θ(n)