Java中的七大排序_2 希尔排序
发布时间:2020-12-15 07:53:27 所属栏目:Java 来源:网络整理
导读:希尔排序 简单点说: 将元素进行分组,每组在进行组内的插入排序,在重新分组、排序。直到最后全部元素归为一组,做最后一次插入排序 注意: 将待排元素分为gap组(gap=gap/3+1),开始gap=array.length。每一组元素也不是位置连续的, 而是把每组中的第一个元
希尔排序
简单点说:将元素进行分组,每组在进行组内的插入排序,在重新分组、排序。直到最后全部元素归为一组,做最后一次插入排序 1.第一组:无序区间第一个数key=array[4]=2 2.第二组:无序区间第一个数key=array[5]=4 3.第三组:无序区间第一数key=array[6]=1 4.第四组:无序区间第一个数key=array[7]=5 5.再接着从第一组的无序区间的第二个元素key=array[8]=2开始 在会分新的组,gap=gap/3+1=4/3+1=2.分为两组 再重复以上比较移动交换的操作,完成第二次每组的排序 8.走到最后再分组gap=2/3+1=1组 最终比较完成后结果: 代码实现//希尔排序 public static void shellSort(int[] array) { int gap = array.length;//分组的个数 while (true) { gap = gap / 3 + 1; insertSortWithGap(array,gap);//分组的插入排序 if (gap == 1) { return; } } } //每组的组内插入排序 private static void insertSortWithGap(int[] array,int gap) { for (int i = 0; i < array.length - gap; i++) {//假设前gap组已经有序,所以只循环arr.length-gap次 int key = array[i + gap];//组内排序 int j; for (j = i; j >= 0 && key < array[j]; j -= gap) { array[j + gap] = array[j]; } array[j + gap] = key; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |