黑马程序员技术交流社区

标题: 算法题 [打印本页]

---

作者: 陈建华    时间: 2012-12-5 16:36
标题: 算法题
用java写出希尔排序算法 并写出实现思路及原理

---

作者: 马海保    时间: 2012-12-5 18:48

/ * 希尔排序：
* 不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法，
* 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 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个数，然后将其用希尔算法排序再输出。
*/
//////////////////////////////////////////////////////////////////////////////////

---

作者: 彭璞    时间: 2012-12-5 18:59


{:soso_e113:}学习了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2