频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
排序算法之希尔排序
2017-04-11 13:50:30           
收藏   我要投稿

排序算法之希尔排序:希尔排序是时间复杂度突破O(n2)的最早的一批算法之一,它是直接插入排序的升级版。

思想:由于直接插入排序在待排序列基本有序的情况下效率是很高的,但是在实际情况中,很少能满足基本有序。希尔排序就是要为直接插入排序创造基本有序的条件。

过程:以{9,1,5,8,3,4,6,10,2,12}为例

要确认分组的条件,即确认一个增量increment。

(1)设置第一次的增量为increment_1=length/2=10/2=5

分组为(9,4),(1,6),(5,10),(8,2),(3,12)

对这些分组进行内部直接插入排序,排序后为(4,9),(1,6),(5,10),(2,8),(3,12)

那么排序后的序列为{4,1,5,2,3,9,6,10,8,12}

(2)设置第二次的增量为increment_2=(increment_1)/2=5/2=2

分组为{4,5,3,6,8}和{1,2,9,10,12}

进行内部直接插入排序后为{3,4,5,6,8}和{1,2,9,10,12}

那么排序后的序列为{3,1,4,2,5,9,6,10,8,12}

(3)设置第三次的增量为increment_3=(increment_2)/2=2/2=1

增量为1的时候就是对整个序列{3,1,4,2,5,9,6,10,8,12}进行整体的直接插入排序。

public class ShellSort {

public static void main(String[] args) {

int[] arr = {9,1,5,8,3,4,6,10,2,12};

shellSort(arr);

}

private static void shellSort(int[] arr) {

int incre = arr.length/2; //增量初始值

int j;

while(incre>=1){ //当增量小于1时终止循环

//分组内部进行直接插入排序

for(int i = incre;i=0 && arr[j]>temp;j-=incre){

arr[j+incre] = arr[j];

}

arr[j+incre] = temp;

}

incre = incre/2;

}

}

}

复杂度分析:

希尔排序最关键的操作是比较而不是交换,由于希尔排序是根据增量来分组的,那么增量的选取会影响排序的效率。目前还没有人找到最好的一种增量序列,但要注意增量序列的选择必须满足序列最后一个增量值为1。

排序算法最差情况复杂度最好情况复杂度平均时间复杂度

希尔排序O(n3/2–O(nlog2n)

点击复制链接 与好友分享!回本站首页
上一篇:依赖传递与scope
下一篇:面试题之二维数组中的查找
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站