浅析java 希尔排序(Shell)算法

浅析java 希尔排序(Shell)算法

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

该方法实质上是一种分组插入方法。

原理图：

源代码

复制代码 代码如下:

package com.zc.manythread;

/**

 *

 * @author 偶my耶

 *

 */

public class ShellSort {

    public static int count = 0;

    public static void shellSort(int[] data) {

        // 计算出最大的h值

        int h = 1;

        while (h <= data.length / 3) {

            h = h * 3 + 1;

        }

        while (h > 0) {

            for (int i = h; i < data.length; i += h) {

                if (data[i] < data[i - h]) {

                    int tmp = data[i];

                    int j = i - h;

                    while (j >= 0 && data[j] > tmp) {

                        data[j + h] = data[j];

                        j -= h;

                    }

                    data[j + h] = tmp;

                    print(data);

                }

            }

            // 计算出下一个h值

            h = (h - 1) / 3;

        }

    }

    public static void print(int[] data) {

        for (int i = 0; i < data.length; i++) {

            System.out.print(data[i] + "\t");

        }

        System.out.println();

    }

    public static void main(String[] args) {

        int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };

        print(data);

        shellSort(data);

        print(data);

    }

}

运行结果:

Shell排序是不稳定的，它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间

该方法实质上是一种分组插入方法。

原理图：

源代码

复制代码 代码如下:

package com.zc.manythread;

/**

 *

 * @author 偶my耶

 *

 */

public class ShellSort {

    public static int count = 0;

    public static void shellSort(int[] data) {

        // 计算出最大的h值

        int h = 1;

        while (h <= data.length / 3) {

            h = h * 3 + 1;

        }

        while (h > 0) {

            for (int i = h; i < data.length; i += h) {

                if (data[i] < data[i - h]) {

                    int tmp = data[i];

                    int j = i - h;

                    while (j >= 0 && data[j] > tmp) {

                        data[j + h] = data[j];

                        j -= h;

                    }

                    data[j + h] = tmp;

                    print(data);

                }

            }

            // 计算出下一个h值

            h = (h - 1) / 3;

        }

    }

    public static void print(int[] data) {

        for (int i = 0; i < data.length; i++) {

            System.out.print(data[i] + "\t");

        }

        System.out.println();

    }

    public static void main(String[] args) {

        int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };

        print(data);

        shellSort(data);

        print(data);

    }

}

运行结果:

Shell排序是不稳定的，它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。