数据结构与算法—排序(下)

<h3>在上一篇排序算法中介绍了3中基础排序算法：选择排序，插入排序，希尔排序。接下来介绍的两钟排序算法《归并排序》和《快速排序》也是基于排序(上)中的思想，进行改进后的高级排序算法。没看的可以去看看。
传送门：<a href="http://www.jianshu.com/p/73574e7e1fbc">数据结构与算法—排序(上)</a></h3>
<h5>话不多说，直接进入主题。</h5>

<blockquote>归并排序的思想是将一个数组分成两半，再将结果进行归并。归并排序最吸引人的特点就是对于任意长度为 N的数组，其所需时间和NlogN成正比，当然带来的缺点就是储存临时数组的空间开销。接下来看看归并排序的可视化过程帮助我们理解。</blockquote>

merge.png

<h6>结合图就很好理解了，先将数组分成两份，并将两份排序，然后将结果归并。最后还是要上代码的：</h6>

<pre>

package com.example.sort;
/**
 * 归并排序
 * */
public class Merge extends SortTamplate{
    private static Comparable aux[];
    public static void merge(Comparable a[],int low,int mid,int high){
        int i = low;
        int j = mid+1;
        for(int k=low;k<=high;k++){
            aux[k] = a[k];
        }
        for(int k=low;k<=high;k++){
            if(i > mid){
                a[k] = aux[j++];
            }else if( j > high){
                a[k] = aux[i++];
            }else if(less(aux[j],aux[i])){
                a[k] = aux[j++];
            }else{
                a[k] = aux[i++]; 
            }
        }
    }
    @Override
    public void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable a[],int low,int high){
        if(low >= high){
            return;
        }
        int mid = low + (high-low)/2;
        sort(a,low,mid);
        sort(a,mid+1,high);
        merge(a,low,mid,high);
    }
    public static void sortBU(Comparable a[]){
        int N = a.length;
        aux = new Comparable[a.length];
        for(int i = 1;i<N;i+=i){
            for(int low = 0;low<N-i;low+=i+i){
                merge(a,low,low+i-1,Math.min(low+i+i-1, N-1));
            }
        }
    }
}

</pre>

<blockquote>然后就是最后一个排序算法：快速排序。
快速排序采用分治的思想，它将一个数组切分成两个子数组，将两部分独立排序，听起来和归并排序貌似一样啊？但是不同之处在于快速排序将两个子数组排序完成之后整个数组不用归并也就有序了。在归并排序中，递归调用发生在处理这个数组之前，而快速排序中递归调用发生在处理整个数组之后。在归并排序中，一个数组被切分成两半，快速排序却分的位置取决于数组的内容。
以下为可视化步骤：</blockquote>

quicksort-overview.png

快速排序轨迹图实在是不好画。。。还是之间上代码吧╥﹏╥...

<pre>

package com.example.sort;

public class QuickSort extends SortTamplate{
    private final static int M = 10; /*对于小数组使用插入排序比快速排序效率高*/
    @Override
    public void sort(Comparable[] a) {
        // TODO Auto-generated method stub
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable[] a,int low,int high){
        if(high <= low +M){
            Insertion.sort(a,low,high);
            return;
        }
        int j = partition(a,low,high);
        sort(a,low,j-1);
        sort(a,j+1,high);
        
    }
    private static int partition(Comparable[] a, int low, int high) {
        int i = low;
        int j = high+1;
        Comparable v = a[low];
        while(true){
            while(less(a[++i],v)){
                if(i == high){
                    break;
                }
            }
            while(less(v,a[--j])){
                if(j==low){
                    break;
                }
            }
            if(i>=j){
                break;
            }
            exchange(a,i,j);
        }
        exchange(a,low,j);
        return j;
    }

}

</pre>

<h4>到这里一些常用的排序算法都已经介绍完毕了，初衷是想尽可能通俗易懂的与大家分享，所以出了快速排序，其他排序的轨迹图都是拿windows自带的画图工具自己画的，很粗糙，不美观，但是也尽力了。</h4>