Java学习与技术总结——（二）神奇的排序算法

排序就是将一组数据按照某种逻辑顺序重新排列的过程，据说在计算时代早期，30%的计算周期都用在了排序上，现在这个比例下降了，主要是因为算法计算更加高效了。
我想算法中最经典的就是排序算法了，在各种领域都有重要地位，那么就从学习排序算法开始吧。

1.1游戏规则

我们关注的主要对象是重新排列数组元素的算法，其中每个元素都有主键，排序算法就是将所有主键按照某种方式排列。在Java中元素通常都是对象，对铸件的抽象描述则是通过一种内置的机制(comparable接口)来完成的。
这里给出了一个所有排序算法类的模板：

public class Example
{
    public static void sort(Comparable[] a)                 //排序函数
    {
    //这里写上你用的算法
    }
    public static boolean less(Comparable v,Comparable w)   //比较函数，如果 v<w 则输出true，反之输出false
    {
    return v.compareTo(w)<0;
    }
    public static void show(Comparable[] a)
    {
        for(int i=0;i<a.length;i++)
        {
        //输出函数，用来输出每个元素
        }
    }
    public static boolean isSorted((Comparable[] a))
    {
    //测试数组是否是有序
    for(int i=1;i<a.length,i++)
    {
    if(less(a[i],a[i-1]))   return false;//有任何一个元素居然小于前一个，说明还无序
    }
    return true;
    }
    public static main(String[] args)
    {
    String[] a=In.readStrings();
    sort(a);
    assert isSorted(a);
    show(a);
    }
}

以上这个类是数组排序实现的框架和模板，对于学习各种排序算法，都这样操作非常方便，这段代码使用已任何实现了Comparable接口的数据类型。

关于Comparable

我们的排序算法适用于任何实现了Comparable接口的数据类型，Java中封装的数字类型int，double,以及String和其他许多高级数据类型如（File和URL）都实现了该接口，因此你可以用这些类型的数组作为参数调用排序方法。

1.2选择排序

选择排序大概是最简单的排序方法了，无论是学习C语言还是其他编程语言，大概都会学习到这种算法，他的大概原理是这样的：找到数组中的最小元素和第一个元素交换位置，在再剩下的元素中选择最小的元素和第二个元素交换位置…如此往复，直至将整个数组排好序，由于他不断选择剩余元素中最小的，故成为选择排序。
选择排序的内循环只是在比较当前元素与目前已知的最小元素，这确实很简单了。交换的代码写在内循环外，每次交换都能排定一个元素，因此交换次数为N。
特点：
1.运行时间与输入无关，就是输入一个拍好的数组，他还是会用那么长时间。
2.数据移动很少，N此交换而已。

//选择排序
public class Selection
{
    public static void sort(Comparable[] a)
    {
    int N =a.length;
    for(int i=0;i<N;i++)
    {   //将a[i]和a[i+1...N]中的最小元素交换
        int min=i;
        for(int j=i+1;j<N;j++)
            if(less(a[j],a[min]))min=j; //记住下标到循环外交换
          exch(a,i,min);
    }
    }
    //less(),exch(),isSorted()...参考模板
}

1.3插入排序

插入排序最通俗的理解就是打牌拿牌的方式，当你拿到一张牌后，会往已经有序的牌中插入适当位置。插入排序也是同理，当前索引左边都是有序的，但最终位置还能不确定，一直和左边元素进行比较，如果有大的就交换，当索引到达最右端时排序结束。
插入排序对于实际应用中常见的某些类型的非随机数组也就是已经有部分有序的数组很有效，想象你对一个有序数组进行插入排序会发现秒速完成，而用选择排序还需等好久，这就是它的优势。

public class Insertion
{
    public static sort((Comparable[] a))
    {
    int N=a.length;
    for(int i=1;i<N;i++)
    {   //将a[i]插入到a[i-1],a[i-2],...之中
        for(int j=i;j>0&&less(a[j],a[j-1]);j--) //若a[j]<a[j-1]则进行交换，相当于牌往前插
                exch(a,j,j-1);

    }
    }
     //less(),exch(),isSorted()...参考模板
}

插入排序确实很适合部分有序的数组，也很适合小规模数组。

1.5归并算法

归并算法的基本思想是什么呢？其实用合并算法来形容更加贴切，简单来说就是，将一个数组排序，可以先递归的将其分成两半，在分别进行排序，排序完再合并。但是当用归并排序将一个大数组排序时，我们需要进行很多次归并，因为每次合并都需要创建一个新的数组来储存排序结果是很不友好的，所有下面几行代码实现了原地合并抽象化，就是将子数组归并成一个有序的数组并将结果存回原数组中，并且结合自顶而下的归并排序，将整个数组排序。

    public static void merge(Comparable[] a,int lo,int mid,int hi)
    {
        //将a[lo...mid]和a[mid+1...hi]

        int i=lo,j=mid+1;
        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 class Merge
    {
        private static Comparable[] aux;        //辅助数组
        private 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, lo, mid, hi);      //归并结果
        }

    }

1.6快速排序*

下面着重记录下实用最广泛的快速排序算法。快速排序算法流行的原因，是它简单，适用于各种情况，且在一般应用中它实在是太快，太好用了。

快速排序的核心就是切分，首先确定一个切分元素，然后从头尾两个两个指针开始往中间走，头指针往右走，遇到比切分元素小的就继续，直到遇到比切分元素大的；尾指针往左走，如果遇到比切分元素大的就继续，直到遇到比切分元素小的，这时候交换头尾指针的元素，确保头指针左边都是比切分元素小的，尾指针右边都是比切分元素大的，最后当两指针相遇时再把切分元素换到头尾指针所在的中间来，再递归同样的方法将左边小元素排序，递归右边大元素排序，这样整个数组就排好了。

public class Quick
{
    public static void sort(Comparable[] a)
    {
            StdRandom.shuffle(a);   //生成个随机数组
            sort(a,0,a.length-1);
    }
    private static void sort(Comparable[] a,int fst,int fin)
    {
    if(fin<=st)return;
    int j=partition(a,fst,fin);     //切分函数后面介绍
    sort(a,fst,j-1);                //对左边小元素排序
    sort(a,fin,fin);                //对右边大元素排序
    }
}

要完成这个实现，需要实现切分方法，一般都是随意的取a[fst]作为切分元素，即那个将会排定的元素，快速排序的切分实现如下：

    private static int partition(Comparable[] a,int fst,int fin)
    {
        //将数组切分为a[fst..i-1],a[i],a[i+1..fin] 
        int i =fst,j=fin+1;     //左右扫描指针
        Comparable  v=a[fst];   //切分元素
        while (true) {
            //扫描左右，检查扫描是否结束并且交换元素
            while(less(a[++i],v)) if(i==fin)break;  //若a[++i]小则继续右找，直到找到大的
            while(less(v,a[--j])) if(j==fst)break;  //若a[j--]大则继续左找，直到找到小的
            if(i>=j)break;
            exch(a,i,j);        //交换
        }
        exch(a,fst,fin);        //将v=a[j]放入正确位置
        return j;               //a[fst..j-1]<=a[j]<=a[j+1...fin]

    }

显然，这段代码按照a[fst]的值v进行切分，当指针i和j相遇时循环退出，在循环中具体交换在注释中已经说明清楚。
快速排序切分方法的内循环用一个递增的索引将数组元素和一个定值比较，这也他的优势所在，一般其他排序慢的原因就是因为在内循环中移动数据。

未完待续…