A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 陈建华 中级黑马   /  2012-12-5 16:36  /  2225 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

用java写出希尔排序算法 并写出实现思路及原理

2 个回复

倒序浏览

/ * 希尔排序:
* 不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法,
* 在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2),
* 没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是
* 最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。
* 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏
* 的情况下执行的效率会非常差。
*
* 专家门提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,
* 再改成快速排序这样更高级的排序算法。
*
* 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。
* 原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。
* 当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。
* 正是这两种情况的结合才使希尔排序效率比插入排序高很多。
*/
////////////////////////////////////////////////////////////////////////////////

class Array {

    private long[] theArray;
    private int nElems;

    public Array(int max) {
        theArray = new long[max];
        nElems = 0;
    }

    public void insert(long value) {
        theArray[nElems] = value;
        nElems++;
    }

    public void display() {
        System.out.print("A=");
        for (int j = 0; j < nElems; j++) {
            System.out.print(theArray[j] + " ");
        }
        System.out.println("");
    }

    public void shellSort() {
        int inner, outer;
        long temp;

        int h = 1;
        while (h <= nElems / 3) {
            h = 3 * h + 1;
        }

        while (h > 0) {
            for (outer = h; outer < nElems; outer++) {
                temp = theArray[outer];
                inner = outer;

                while (inner > h - 1 && theArray[inner - h] >= temp) {
                    theArray[inner] = theArray[inner - h];
                    inner = inner - h;
                }
                theArray[inner] = temp;
            }
            h = (h - 1) / 3;
        }
    }
}
class ShellSortApp {

    public static void main(String[] args) {
        int maxSize = 30;
        Array arr = new Array(maxSize);

        for (int j = 0; j < maxSize; j++) {
            long n = (int) (java.lang.Math.random() * 99);
            arr.insert(n);
        }
        arr.display();
        arr.shellSort();
        arr.display();
    }
}
////////////////////////////////////////////////////////////////////////////////
/**
* 运行结果:
* A=29 14 28 16 40 64 29 11 58 27 88 96 41 63 19 30 55 82 6 10 83 93 86 13 29 19 20 83 83 8
* A=6 8 10 11 13 14 16 19 19 20 27 28 29 29 29 30 40 41 55 58 63 64 82 83 83 83 86 88 93 96
*/

/**
* 总结:
* 希尔排序是对插入排序的一种强有力的改进,极大的提升了其效率,特别是当排序的
* 数据项增加的时候。
* 例子为随机生成30个数,然后将其用希尔算法排序再输出。
*/
//////////////////////////////////////////////////////////////////////////////////

评分

参与人数 1技术分 +1 收起 理由
古银平 + 1 神马都是浮云

查看全部评分

回复 使用道具 举报
本帖最后由 彭璞 于 2012-12-5 19:06 编辑

{:soso_e113:}学习了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马