分治思想之排序算法

分而治之是设计高效算法的一个重要思想。本文主要总结一下分治思想在排序算法中的运用。

排序在商业数据处理和现代科学计算中有着重要的地位，它能够应用于事物处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预报和很多其它领域。——《算法》。

发展至今，已经出现过很多的排序算法。如选择排序，插入排序，希尔排序，堆排序，归并排序，快速排序。这里主要总结下后面种，这种也是目前运用最广和最高效的（虽然在某些特殊情况下，前面一些算法的效率更加高，但这里主要是针对一般情况下），这2种排序是分治思想的典型运用（分治思想也就是把大问题转化为小问题，然后分别去解决，最后整体归并）。

一、归并排序

归并，即将2个有序的数组归并成一个更大的有序数组。而不管是归并排序还是快速排序都是基于归并进行操作的。

1.自顶向下的归并排序。

具体思想是先将左半边排序，然后将右半边排序，最后将排序好的结果归并起来。
如下

private static void sort(Comparable[] a,int lo,int hi) {
        if (hi <= lo) return;
        int mid = lo+(hi-lo)/2;
        sort(a,lo,mid); // 将左半边排序
        sort(a,mid+1,hi); // 将右半边排序
        merge(a,0,mid,hi); // 将排序好的结果归并
    }

注意进行归并操作时，需要使用一个辅助数组。首先把需要排序的所有元素放入到一个辅助数组中，归并时需要进行4个判断:如果左半边的元素取完就取右半边的元素；如果右半边的元素取完就取左半边的元素；如果右半边的当前元素小于左半边
的当前元素则取右半边的元素；如果左半边的当前元素大于右半边的当前元素则取左半边的元素。
最后看总体代码

public class MergeSort {

    //  定义一个辅助数组
    private static Comparable[] aux; 

    public static void sort(Comparable[] a) {
        // 分配辅助数组所需的空间
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }

    private static void sort(Comparable[] a,int lo,int hi) {
        if (hi <= lo) return;
        int mid = lo+(hi-lo)/2;
        sort(a,lo,mid); // 将左半边排序
        sort(a,mid+1,hi); // 将右半边排序
        merge(a,0,mid,hi); // 将排序好的结果归并
    }

    public static void merge(Comparable[] a,int lo,int mid,int hi) {
        int i=lo,j=mid+1;
       
        // 将元素复制到辅助数组
        for (int k=lo;k<=hi;k++) {
            aux[k] = a[k];
        }
        
        // 对应上面所述的4个判断
        for (int k=lo;k<=hi;k++) {
            if (i > mid){   
                a[k] = aux[j++]; 
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (less(aux[j],aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }
    
    //  元素v < w则返回true
    public static boolean less(Comparable v,Comparable w) {
        return v.compareTo(w) < 0;
    }
}

2.自底向上的归并排序

当需要归并的数组较小时，可以考虑另一种归并排序方法，自底向上发散。首先将数组中的每个元素都想像成一个大小为1的数组，然后两两归并。把归并后的结果想象成大小为2的数组，继续进行四四归并，接着八八归并......以此类推，归并完后的数组就是已经排好序的数组。
代码如下

public class MergeBU {
     
    //  定义一个辅助数组
    private static Comparable[] aux; 

    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz=1;sz<N;sz=2*sz) {  //  sz：子数组大小
            for (int lo=0;lo<N-sz;lo+=2*sz) {  // lo:子数组索引
                merge(a,lo,lo+sz-1,Math.min(lo+2*sz-1,N-1));
            }
        }
    }

    public static void merge(Comparable[] a,int lo,int mid,int hi) {
        int i=lo,j = mid+1;
        if (hi <= lo) return;

        for (int k=lo;k<=hi;k++) {
            aux[k] = a[k];
        }
        for (int k=lo;k<=hi;k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (less(aux[j],aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }
    public static boolean less(Comparable v,Comparable w) {
        return v.compareTo(w) < 0;
    }
}

注意merge()方法中传入的第4个参数，使用了Math中的min方法，因为这里涉及到边界问题，对于一个数组我们不能确定它的大小是否刚好是2的多少次幂。

二、快速排序

快速排序是被誉为二十世纪科学和工程领域的十大算法之一，正因为它在处理不同数据方面平均情况下比其它排序算法都要快得多，所以它也目前是应用最广泛的排序算法了，快速排序和归并排序是互补的，快速排序是当2个子数组都有序时，整个数组也就有序了。

1.基本的快速排序

快速排序中，选定一个切分元素v ，然后分遍历左右两边的元素，如果v左边的元素小于v,则进行递增操作；继续遍历右边，右边元素大于v则进行递减操作；其它情况下就把v左右两边的元素进行交换，直到遍历完整个数组。最后保证v左边的元素都小于v，v右边的元素都大于v。最终得到的切分元素v作为下一次进行排序的部分数组的边界，用同样的方式进行递归排序。
代码如下

public class QuickSort {

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a); //消除对输入的依赖
        sort(a,0,a.length-1);
    }
    private static void sort(Comparable[] a,int lo,int hi) {
        if (hi <= lo) return; 
        int j = partition(a,lo,hi);  // 得到切分元素
        sort(a,lo,j-1);  //  将左半部分进行排序
        sort(a,j+1,hi); //  将右半部分进行排序
    }
    
    // 切分方法
    private static int partition(Comparable[] a,int lo,int hi) {
        int i = lo,j = hi+1;  // 定义左右扫描指针
        Comparable v = a[lo];  // 初始化切分元素

      /**    当i和j相遇时退出循环
        *    a[i]小于v时增大i,a[j]大于v时减小j
        *    然后交换a[i]和a[j],当指针相遇时交换lo和j,切分结束
        */
        while (true) {
            while (less(a[++i],v)) { 
                if (i == hi)
                    break;
            }
            while (less(v,a[--j])) {
                if (j == lo)
                    break;
            }
            if (i >= j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);
        return j;
    }

    private static boolean less(Comparable v,Comparable w) {
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable[] a,int i,int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

2.三路快速排序

当需要进行排序的数组出现大量重复的元素时，按理来说重复的元素应该不必进行排序了，但是之前那种快速排序还是会对它们进行切分，所以这里快速排序有很大的改进空间。那就是把元素划分为三部分，对应小于、等于、大于切分元素的部分。如下图

如图所示，这里分别维护三个指标lt、i、gt。
如果a[i]小于v，则将a[lt]和a[i]进行交换，并且将i和lt都递增；如果a[i]大于v,将a[i]和a[gt]进行交换，并且将gt递减；如果a[i]等于v，将i递增，然后继续往后遍历。
这样一来就很好的解决了有大量相等元素时仍然进行切分并且重复遍历的问题。
最后看下代码

public class Quick3waySort {

    private static void sort(Comparable[] a,int lo,int hi) {
        int lt=lo,i=lo+1,gt=hi; // 定义三个指针
        if (hi <= lo) return;
        Comparable v = a[lo];
        while (i <= gt) {
            int temp = a[i].compareTo(v);
            if (temp < 0) {
                exch(a,lt++,i++);
            } else if (temp > 0) {
                exch(a,i,gt--);
            } else {
                i++;
            }
        }
        sort(a,lo,lt-1);
        sort(a,gt+1,hi);
    }
    private static void exch(Comparable[] a,int i,int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

最后，写这篇东西是复习一下。建议有兴趣的朋友去读下Robert Sedgewick和Kevin Wayne的《算法》。