龙盟编程博客 | 无障碍搜索 | 云盘搜索神器
快速搜索
主页 > 软件开发 > JAVA开发 >

Java中常用的6种排序算法详细分解(5)

时间:2014-07-26 11:11来源:网络整理 作者:网络 点击:
分享到:
归并排序需要的额外空间是所有排序中最多的,每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空

归并排序需要的额外空间是所有排序中最多的,每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判断),时间复杂度比较难估,这里小弟也忘记是多少了(囧)。

实现代码:

复制代码 代码如下:

/** 
* Merge sorting 
*/
MERGE(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        this.sort(array, 0, array.length – 1, ascend); 
    } 
 
    private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) { 
        // OPTIMIZE ONE 
        // if the substring's length is less than 20, 
        // use insertion sort to reduce recursive invocation 
        if (hi – lo < 20) { 
            for (int i = lo + 1; i <= hi; i++) { 
                T toInsert = array[i]; 
                int j = i; 
                for (; j > lo; j–) { 
                    int compare = array[j - 1].compareTo(toInsert); 
                    if (compare == 0 || compare < 0 == ascend) { 
                        break; 
                    } 
                    array[j] = array[j - 1]; 
                } 
 
                array[j] = toInsert; 
            } 
 
            return; 
        } 
 
        int mid = lo + (hi – lo) / 2; 
        sort(array, lo, mid, ascend); 
        sort(array, mid + 1, hi, ascend); 
        merge(array, lo, mid, hi, ascend); 
    } 
 
    private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) { 
        // OPTIMIZE TWO 
        // if it is already in right order, skip this merge 
        // since there's no need to do so 
        int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]); 
        if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) { 
            return; 
        } 
 
        @SuppressWarnings("unchecked") 
        T[] arrayCopy = (T[]) new Comparable[hi - lo + 1]; 
        System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length); 
 
        int lowIdx = 0; 
        int highIdx = mid – lo + 1; 
 
        for (int i = lo; i <= hi; i++) { 
            if (lowIdx > mid – lo) { 
                // left sub array exhausted 
                array[i] = arrayCopy[highIdx++]; 
            } else if (highIdx > hi – lo) { 
                // right sub array exhausted 
                array[i] = arrayCopy[lowIdx++]; 
            } else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) { 
                array[i] = arrayCopy[lowIdx++]; 
            } else { 
                array[i] = arrayCopy[highIdx++]; 
            } 
        } 
    } 
})

6. 快速排序

收藏文章
表情删除后不可恢复,是否删除
取消
确定
图片正在上传,请稍后...
评论内容为空!
还没有评论,快来抢沙发吧!

热评话题

按钮 内容不能为空!
立刻说两句吧! 查看0条评论
精彩图集

赞助商链接