< n; j++) {/** 内层循环,对当前元素进行直接插入排序,注意同一子序列中* 的相邻元素的下标相差increment 。如果当前元素大于或等于* 它所在子序列的前一个元素,那么它当前就已经排好序了 。* 否则,需要在它所在的子序列中查找它应该插入的位置,并将* 大于它的所有元素在该子序列中向后移动一个位置 。*/if(array[j] < array[j - increment]) {temp = array[j];for(k = j - increment; k >= 0 && array[k] > temp; k -= increment) {array[k + increment] = array[k];}array[k + increment] = temp;}}}}5. 复杂度分析希尔排序的平均时间复杂度和执行它所选择的增量序列有关,按照我们实现中采用的增量序列,它的平均时间复杂度可以达到O(n^(3/2)),即n的3/2次方 。那么哪一种增量序列是最好的呢?还没有人知道这一问题的答案 。
从我们以上的实现代码中可以看出,希尔排序只需要几个固定的额外存储空间,分别用于存储变量i、j、k、temp、increment,这和它的待排序序列的大小无关 。所以,它的空间复杂度为O(1) 。
(完)
推荐阅读
- 16张图解锁Spring的整体脉络
- 石竹花谢后剪到哪图解,石竹花如何扦插图解介绍如何配土
- 图解固件、驱动、软件的区别
- Excel 中那么多未排序的日期,如何自动标出下个月的所有日期?
- 数据库,MySQL,实战,优化,多表联合查询排序问题优化
- 如何扦插杜鹃花,石竹花如何扦插图解介绍如何配土
- 长寿花老桩的修剪方法图解,长寿花天天花开爆盆的修剪方法
- 动图图解!收到RST,就一定会断开TCP连接吗?
- 图解TCP的通信机制
- 冒泡排序,我可以这样学