亲宝软件园·资讯

展开

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

人气:0
想了解浅析java 希尔排序(Shell)算法的相关内容吗,在本文为您仔细讲解浅析java 希尔排序(Shell)算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:java,希尔排序算法,Shell,下面大家一起来学习吧。

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<;…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。

原理图:

源代码

复制代码 代码如下:

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)之间

加载全部内容

相关教程
猜你喜欢
用户评论