Shell排序选择增量序列 增量每次除以2递减”时,效率仍然为@(n2) 问题:选取的增量之间并不互质 口间距为2k-的子序列都是由那些间距为2k的子序列 组成的 口上一轮循环中这些子序列都已经排过序了,导致 处理效率不高 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 Shell 排序选择增量序列 ◼ 增量每次除以2递减”时，效率仍然为Θ(n2 ) ◼ 问题：选取的增量之间并不互质 ❑ 间距为2 k-1的子序列都是由那些间距为2 k的子序列 组成的 ❑ 上一轮循环中这些子序列都已经排过序了，导致 处理效率不高
■ Hibbard增量序列 口{2k-1,2k1-1,…,7,3,1}, She(3)和 Hibbard增量序列的She排 序的效率可以达到Q(n32) 选取其他增量序列还可以更进一步减少 时间代价 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ Hibbard增量序列 ❑ {2k -1，2 k-1 -1，…，7，3，1}， ◼ Shell(3)和Hibbard增量序列的Shell排 序的效率可以达到Θ(n3/2) ◼ 选取其他增量序列还可以更进一步减少 时间代价
8.3选择排序 831直接选择排序 口选出剩下的未排序记录中的最小记录,然后 直接与数组中第i个记录交换,比冒泡排序减 了移动次数 832堆排序 口堆排序:基于最大值堆来实现 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 8.3 选择排序 ◼ 8.3.1 直接选择排序 ❑ 选出剩下的未排序记录中的最小记录，然后 直接与数组中第i个记录交换 ，比冒泡排序减 少了移动次数 ◼ 8.3.2 堆排序 ❑ 堆排序：基于最大值堆来实现
直接选择排序动画 45347812341322964 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 直接选择排序动画 45 34 78 12 34’ 32 29 64
直接选择排序 template <class record> void Select Sort(Record Array[l, int n) t ∥/依次选出第ⅰ小的记录,即剩余记录中最小的那个 for (int i=0; kkn-1; i ++t 首先假设记录就是最小的 int Smallest= i: 开始向后扫描所有剩余记录 for(ntj=+1」n:j++) 如果发现更小的记录,记录它的位置 if (array[j]< Array[ SmallestD Smallest =j //将第ⅰ小的记录放在数组中第个位置 swap(Array, i, Smallest) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 直接选择排序 template <class Record> void SelectSort(Record Array[], int n) { // 依次选出第i小的记录，即剩余记录中最小的那个 for (int i=0; i<n-1; i++) { // 首先假设记录i就是最小的 int Smallest = i; // 开始向后扫描所有剩余记录 for (int j=i+1;j<n; j++) // 如果发现更小的记录，记录它的位置 if (Array[j] < Array[Smallest]) Smallest = j; //将第i小的记录放在数组中第i个位置 swap(Array, i, Smallest); } }