- 时间复杂度:shell排序时间复杂度取决于所选取的步长序列,介于O(nlogn)和O(ns)(1<s<2)
- 也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。
- 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。
- 假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序(冒泡排序或插入排序),可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据,所以小数据只需进行少数比较和交换即可到正确位置。
- 一个更好理解的希尔排序实现:将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += step_size而不是i++)。
- 例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
- 图片截取自维基百科
public class ShellSort {public static void shellSort(int[] array) {int stepLength = array.length / 2;while (stepLength >= 1) {for (int i = 0; i < stepLength; i ++) {for (int j = i; j + stepLength < array.length; j += stepLength) {int temp = array[j + stepLength];while (temp < array[j]) {array[j + stepLength] = array[j];if (j == i) {j -= stepLength;break;}j -= stepLength;}array[j + stepLength] = temp;}}stepLength /= 2;}}}
详细解决方案
排序专题(八) / 不稳定的内部排序 / 希尔(shell)排序
热度:64 发布时间:2024-01-16 21:45:47.0
相关解决方案
- 遇到一个怪有关问题,createobject("wscript.shell").run "a.vbs" vbs咋是多线程的
- shell 获取字符串中某单纯词的后面一个单词
- mongo shell 里边find不出数据
- Shell.Application的异常抓取
- shell 写资料
- shell while循环内的变量在循环外部值不能传送
- shell 程序监控网站网页是不是被修改,如果被修改停止服务器的运行
- shell cd解决方案
- shell 中 在if 语句中执行 查询语句 会出现语法异常 !请高人指点
- shell 函数返回值,该如何解决
- shell cd,该如何解决
- 批量剔除 .svn shell
- mongodb鍏ラ棬<浜?gt;mongodb鐨刯avascript shell
- PHP shell 不能批改服务器的文件
- 编译PHP替interactive shell
- maven-antrun-plugin中没法调用 jsch shell target
- start/stop weblogic server in shell
- IE7.0中 var Wsh=new ActiveXObject("WScript.Shell");保[object error]错解决思路
- 请教为什么小弟我在html中用js可以new ActiveXObject("WScript.Shell"),但是在jsp中却不行呢?小弟初学者,望各位帮助
- java中应用SSH(secure shell)登录远程服务器之后,怎样获得当前文件夹的绝对路径
- unix shell 逐行读文件并赋值给变量解决方法
- unix shell 调用sqlplus 遍历表,该如何处理
- SWT shell 窗体怎么在桌面中央显示
- Linux Qt shell 外部程序解决方案
- adb shell 中am start有关问题求教,请进!
- Android 执行linux shell 语句有关问题
- ,shell 命令,怎么删除当前目录中不包含某字符串的文件
- PHP shell 不能批改服务器的文件
- 编译PHP替interactive shell
- shell 脚本出错“syntax error near unexpected token `'”