浙江巨鑫建设有限公司网站企业在线培训系统

浙江巨鑫建设有限公司网站,企业在线培训系统,成都网站开发团队,石家庄最新招聘信息希尔排序 学习目标#xff1a; 一.希尔排序的思想 二.增量序列 三.复杂度分析 四.希尔排序为什么快#xff1f; 五.强化练习 一.希尔排序的思想 1.将待排序数组按照一定的“间隔”分为多个子数组#xff0c; 每组分别进行“插入排序” 2.逐渐缩小间隔#xff0c;…希尔排序学习目标一.希尔排序的思想二.增量序列三.复杂度分析四.希尔排序为什么快五.强化练习一.希尔排序的思想1.将待排序数组按照一定的“间隔”分为多个子数组每组分别进行“插入排序”2.逐渐缩小间隔进行下一轮排序3.最后一轮时取间隔为1相当于直接使用插入排序但此时经过 [宏观调控] 数组已经基本有序所以此时插入排序只需进行少量交换代码实现publicstaticvoidshellSort(int[]arr){for(intgaparr.length/2;gap0;gap/2){for(intgroupStartIndex0;groupStartIndexgap;groupStartIndex){for(intcurrentIndexgroupStartIndexgap;currentIndexarr.length;currentIndexgap){intcurrentNumberarr[currentIndex];intpreIndexcurrentIndex-gap;while(preIndexgroupStartIndexarr[preIndex]currentNumber){arr[preIndexgap]arr[preIndex];preIndex-gap;}arr[preIndexgap]currentNumber;}}}}目前的思路是根据gap分组处理完一组后调整指针再处理下一组这种思路非常符合人类思维但对于计算机而言它更喜欢从gap开始依次向前将每个数字插入到其对应的组中虽然数字好像在不同组间跳跃但对于计算机就像是在访问一段连续的数组代码优化将第二、三个for循环整合成一个publicstaticvoidshellSort(int[]arr){for(intgaparr.length/2;gap0;gap/2){for(intcurrentIndexgap;currentIndexarr.length;currentIndex){intcurrentNumberarr[currentIndex];intpreIndexcurrentIndex-gap;while(preIndex0arr[preIndex]currentNumber){arr[preIndexgap]arr[preIndex];preIndex-gap;}arr[preIndexgap]currentNumber;}}}二.增量序列1.定义Shell排序中每一遍排序的间隔 ‘gap’ 被称为 “增量” 所有增量组成的序列叫做增量序列也就是上述例子中的’5‘’2‘’1‘增量是依次递减所以Shell排序又称为缩小增量排序增量序列的选择会极大影响Shell排序的效率若没有正确选择增量序列Shell排序效率可能比插入排序更低如图所示在gap 8 , 4 , 2 时无元素交换只有在gap 1时才发挥了作用而此时Shell排序相比插入排序多做了无用功2.一些著名的增量序列(1) Hibbard增量序列Dk 2k- 1 , 也就是 13715… 。数学界猜想它最坏的时间复杂度为O(n3/2) 平均时间复杂度为O(n5/4)(2) Knuth增量序列D1 1; Dk1 3 * Dk 1也就是 141340… 。数学界猜想它的平均时间复杂度为O(n3/2)(3) Sedgewick增量序列151941109… 。这个序列的元素有的是通过 9 * 4k- 9 * 2k 1 计算出来的有的是通过 4k- 3 * 2k 1 计算出来的并将其按照从小到大排列数学界猜想它最坏的时间复杂度为O(n4/3)平均时间复杂度为O(n7/6)3.增量序列示例publicstaticvoidshellSort(int[]arr){//使用Knuth增量序列//先要找出增量序列的最大值intmaxKnuthNum1;//初始化while(maxknuthNum*31arr.length){maxKnuthNummaxknuthNum*31}//把值赋给gap并修改gap变化的规律for(intgapmaxknuthNum;gap0;gap(gap-1)/3){for(intcurrentIndexgap;currentIndexarr.length;currentIndex){intcurrentNumberarr[currentIndex];intpreIndexcurrentIndex-gap;while(preIndex0arr[preIndex]currentNumber){arr[preIndexgap]arr[preIndex];preIndex-gap;}arr[preIndexgap]currentNumber;}}}三.复杂度分析由于增量序列会极大影响Shell排序的效率时间复杂度平均时间复杂度介于O(n)到O(n2)​ 普遍认为最好的时间复杂度为O(n1.3)空间复杂度O(1) 只需要常数级的临时变量四.希尔排序为什么快1.“逆序对”概念引入当我们从小到大排序时在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对而所有排序算法的本质都是消除逆序对对于随机的数组逆序对的数量是O(n2)级的如果使用交换相邻元素的方法来消除逆序对每次只能消除一组逆序对所以交换的次数是O(n2)级的这就是冒泡、选择、插入排序算法时间复杂度只能达到O(n2)的原因而基于交换元素的排序算法 ( 空间复杂度为O(1) ) 想突破O(n2)必须通过一些比较交换间隔比较远的元素也就是需要在一次交换中能够消除一个以上的逆序对Shell排序算法就是如此此后的快排、堆排也是如此…五.强化练习506. 相对名次 - 力扣LeetCode杂度为O(1) ) 想突破O(n2)必须通过一些比较交换间隔比较远的元素也就是需要在一次交换中能够消除一个以上的逆序对Shell排序算法就是如此此后的快排、堆排也是如此…五.强化练习506. 相对名次 - 力扣LeetCode912. 排序数组 - 力扣LeetCode