黑马程序员技术交流社区

标题: 整理了一些排序的方法，高手勿喷（2） [打印本页]

---

作者: wojiaojay    时间: 2014-5-6 19:54
标题: 整理了一些排序的方法，高手勿喷（2）
4. 希尔排序

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ，则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题。

具体实例请参照插入排序。

希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

实现代码：



Java代码  收藏代码
/**
* Shell Sorting
*/  
SHELL(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        int length = array.length;  
        int gap = 1;  

        // use the most next to length / 3 as the first gap  
        while (gap < length / 3) {  
            gap = gap * 3 + 1;  
        }  

        while (gap >= 1) {  
            for (int i = gap; i < length; i++) {  
                T next = array[i];  
                int j = i;  
                while (j >= gap) {  
                    int compare = array[j - gap].compareTo(next);  
                    // already find its position  
                    if (compare == 0 || compare < 0 == ascend) {  
                        break;  
                    }  

                    array[j] = array[j - gap];  
                    j -= gap;  
                }  
                if (j != i) {  
                    array[j] = next;  
                }  
            }  
            gap /= 3;  
        }  

    }  
})  


5. 归并排序

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] （虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ，我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分）那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下：

1） 将两个子数组中的元素复制到新数组 copiedArray 中，以前面提到的例子为例，则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ；
2） 设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为 leftIdx 和 rightIdx ，则 leftIdx = 0 （对应 copiedArray 中的第一个元素 [3] ）， rightIdx = 4 （对应 copiedArray 中的第五个元素 [1] ）；
3） 比较 leftIdx 和 rightIdx 指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置 i ，赋值完毕后分别对参与赋值的这两个索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例：

第一趟：

辅助数组 [21 , 28, 39 | 35, 38] （数组被拆分为左右两个子数组，以 | 分隔开）

[21 ,  ,  ,  ,  ] （第一次 21 与 35 比较 , 左边子数组胜出， leftIdx = 0 ， i = 0 ）

第二趟：

辅助数组 [21, 28 , 39 | 35, 38]

[21 , 28,  ,  ,  ] （第二次 28 与 35 比较，左边子数组胜出， leftIdx = 1 ， i = 1 ）

第三趟： [21, 28, 39 | 35 , 38]

[21 , 28 , 35,  ,  ] （第三次 39 与 35 比较，右边子数组胜出， rightIdx = 0 ， i = 2 ）

第四趟： [21, 28, 39 | 35, 38 ]

[21 , 28 , 35 , 38,  ] （第四次 39 与 38 比较，右边子数组胜出， rightIdx = 1 ， i = 3 ）

第五趟： [21, 28, 39 | 35, 38]

[21 , 28 , 35 , 38 , 39] （第五次时右边子数组已复制完，无需比较 leftIdx = 2 ， i = 4 ）

以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分（每次一分为二）直到分为长度为 1 的小数组为止，长度为 1 时数组已经不用排序了。在这之后再逆序（由于采用递归）依次对这些数组进行归并操作，直到最后一次归并长度为 n / 2 的子数组，归并完成之后数组排序也完成。

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

实现代码：



Java代码  收藏代码
/**
* 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++];  
            }  
        }  
    }  
})  

---

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

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