StackTc
StackTc
采纳率61.9%
2018-01-25 06:20 阅读 965
已采纳

希尔排序分成4个序列时有错误,求指教。

10

希尔排序

话不多说,show code

 /**
 * 
 * Date : 2017/12/9.
 */
public class Solution {
    public static void  main(String[] agrs){
        int[] a = new int[10];
        for (int i = 0; i < 10; i++) {
            a[i] = (int) (Math.random() * 100);
        }
        System.out.println("原数组--------------");
        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + ",");
        }
        System.out.println();
        shellSort(a);
        System.out.println("");
        System.out.println("结果数组---------");
        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + ",");
        }
    }

    public static int[] shellSort(int[] a) {
        int x = 0;
        for (int d = a.length / 2; d > 0; d /= 2) {
            for (int j = d; j < a.length; j ++) {
                while (j > 0 && a[j] < a[j - d]) {
                    int temp = a[j];
                    a[j] = a[j - d];
                    a[j - d] = temp;
                }
            }
            x++;
            System.out.println("第" + x + "次d=" + d);
            System.out.println("第" + x + "次排序结果。");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + ",");
            }
            System.out.println();
        }
        return a;
    }
}

运行结果如下:


原数组--------------
91,48,74,56,84,30,44,90,9,1,
第1次d=5
第1次排序结果。
30,44,74,9,1,91,48,90,56,84,
第2次d=2
第2次排序结果。
30,9,1,44,48,90,56,84,74,91,
第3次d=1
第3次排序结果。
9,1,30,44,48,56,84,74,90,91,

---------
9,1,30,44,48,56,84,74,90,91,
Process finished with exit code 0

第一次排序,跟期望中的一样。因为只有2个序列,
然而第二次排序的时候,分成4个序列,交叉排序导致错误。
谁对希尔排序比较熟悉的,请指教。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • 已采纳
    crazy123snail crazy123snail 2018-01-25 07:24

    希尔排序原理首先分组 ,然后对分组进行(交换/插入)排序 ,关键代码如下,此部分省去了输入输出并添加了关键注释:

      public static int[] shellSort(int[] a) {
            for (int d = a.length / 2; d > 0; d /= 2) {          //选择分组大小d进行希尔排序
                    /*从第d个元素开始,依次为后续元素分组进行排序,例如d=2时,首先进行a[2] a[0] 的比较,再进行a[3] a[1] ,再进行a[4] a[2] a[0] */
                for (int j = d; j < a.length; j ++) {                   //此处 j 作为分组第一项
                             int i=j;
                    while (i-d> 0 && a[i] < a[i- d]) {                //  while语句中 i-d 创建以 j 开头的分组,后面则是比较语句 
                        int temp = a[i];
                        a[i] = a[i - d];
                        a[i - d] = temp;
                                            i-=d;
                    }
                }
    

    以上就是分组、排序的拆分步骤,楼主应该是没有正确理解分组的内涵

    点赞 1 评论 复制链接分享
  • StackTc StackTc 2018-01-25 09:20

    程序问题本人以解决,在这里问一下。希尔排序的最后一步是d = 1的排序,跟插入排序一样,而且在排序d = 1之前还做了多次d > 1的排序,
    为什么又说希尔排序比插入排序快呢?

    点赞 评论 复制链接分享

相关推荐