排序

排序模板

package algorithm.sort;
import java.lang.Comparable;
public abstract class SortExample<T extends Comparable<T>> {
    public abstract void sort(T[] a);

    public boolean less(T v, T w){
        return v.compareTo(w)<0;
    }
    public void exch(T[] a,int i,int j){
        T t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public void show(T[] a){
        for (T comparable : a) {
            System.out.println(comparable + "");
        }
    }
    public boolean isSorted(T[] a){
        for(int i=1;i<a.length;i++){
            if(less(a[i],a[i=1])) return false;
        }
        return true;
    }
}

插入排序

在尚未排序元素中按顺序遍历每个乱序元素，将每个乱序元素按顺序与有序元素比较，放在合适的位置后，操作下一个乱序元素

package algorithm.sort;
public class Insertion<T extends Comparable<T>> extends SortExample<T>{
    @Override
    public void sort(T[] a){
        int N = a.length;
        for(int i=1;i<N;i++){
            for(int j=i;j>0&&less(a[j],a[j=1]);j--){
                exch(a,j,j-1);
            }
        }
    }
}

希尔排序

希尔排序基于插入排序，插入排序的比较与交换是相邻元素之间的所以大规模的乱序会很慢，希尔排序的思想是将数组中任意间隔为h的元素都是有序的，即是说希尔排序意在构建多个相互独立的有序数组。伴随着间隔逐渐的缩减为1后便是有序数组，而各个间隔为h的独立数组的实现都是插入排序。
对于中等大小的数组，希尔排序的运行时间是可以接受的，代码量小，且不需要使用额外的内存，对于很大的N其它高效算法只会比希尔排序快两倍左右，但其更复杂。
此处希尔排序实现中的h的使用的是实时计算出的1/2（3^k-1）序列，也可以将h的序列存储在数组当中供使用。

package algorithm.sort;
public class Shell<T extends Comparable<T>> extends SortExample<T>{
    @Override
    public void sort(T[] a) {
        int N = a.length;
        int h = 1;
        while(h<N/3)
            h=3*h+1;
        while (h>=1){
            for(int i=h;i<N;i++){
                for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h)
                    exch(a,j,j-h);
            }
            h=h/3;
        }
    }
}

归并排序

归并排序的实现思想为：先将左边排序，再将右边排序，最后左右统一起来，在自顶向下调用的过程中总是先排左再排右最后联合，有种后序遍历的感觉，排序主要右merge算法实现。
归并排序在最坏的情况下的比较次数是~NlgN，这是任何最好的算法在最坏的情况下的最小的比较次数。

package algorithm.sort;
public class Merge{
    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,lo,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];
        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++];
    }
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w)<0;
    }
}

快速排序

快速排序适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。并且快速排序是原地排序，只需要一个很小的辅助栈，不会有太多余的内存开销，将长度为N的数组排序所需要的时间和NlgN成正比。
快速排序有着分治的思想：将一个数组分为两个数组，当两个子数组都有序时，整个数组自然有序了。
快速排序的缺点便是很脆弱，一不小心便会使得性能变得恶劣，主要注意一下几个点：原地切分（不在递归调用中新建数组）；越界；保持随机性（消除对输入的依赖）；终止循环；终止递归；切分元素值会有重复的情况

package algorithm.sort;
public class Quick <T extends Comparable<T>> extends SortExample<T>{
    @Override
    public void sort(T[] a) {
        sort(a,0,a.length-1);
    }
    private void sort(T[] 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 int partition(T[] a,int lo,int hi){
        //左右扫描指针
        int i=lo,j=hi+1;
        T v = a[lo];
        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;
    }
}

对于小数组而言，可以做如下更改将快速排序切换到插入排序
if(hi<=lo) return;
更改为
if(hi<=lo+M){Insertion.sort(a,lo,hi); return;}
当数据具有大量重复元素时，通过将原切分
a[lo,j-1]<v=a[j]<a[j+1,hi]
更改为
a[lo..lt-1]<v=a[lt,gt]<a[gt+1,hi]
具体实现为三向切分的快速排序

三向切分的快速排序

package algorithm.sort;
public class Quick3way extends Quick {
    @Override
    protected void sort(Comparable[] a, int lo, int hi) {
        if(hi<=lo)return;
        int lt = lo,i=lo+1,gt=hi;
        Comparable v = a[lo];
        while(i<=gt){
            int cmp = a[i].compareTo(v);
            if(cmp<0)exch(a,lt++,i++);
            else if(cmp>0)exch(a,i,gt--);
            else i++;
        }
        sort(a,lo,lt-1);
        sort(a,gt+1,hi);
    }
}

堆/队列

堆常为优先队列的实现采用的数据结构，由于优先队只在乎极值，所以在实现过程中少去了许多比较与交换。

基于堆的优先队列

public class MaxPQ <Key extends Comparable<Key>>{
    //基于堆的完全二叉树，pq[0]未使用
    private Key[] pq;
    private int N=0;
    //创建优先队列
    public MaxPQ(){
        ***
    }
    public MaxPQ(int max){
        pq = (Key[])new Comparable[max+1];
    }
    public MaxPQ(Key[] a){
      ***
    }
    public void insert(Key v){
        pq[++N] = v;
        swim(N);
    }
    //返回最大元素
    public Key max(){
        return pq[1];
    }
    //删除、返回最大元素
    public Key delMax(){
        Key max = pq[1];
        exch(1,N--);
        //N+1处不再使用，设为null以便系统回收空间
        pq[N+1]=null;
        sink(1);
        return max;
    }
    //返回队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j])<0;
    }
    private void exch(int i,int j){
        Key t = pq[i];pq[i] = pq[j];pq[j] = t;
    }

    //从下到上，将更大的节点向上传递
    private void swim(int k){
        while(k>1&&less(k/2,k)){
            exch(k/2,k);
            k = k/2;
        }
    }
    //从上到下，将顶部的节点向下传递
    private void sink(int k){
        while(2*k<=N){
            int j = 2*k;
            //选出当前节点的最大子节点
            if(j<N&&less(j,j+1)) j++;
            //若当前节点不小于选出的最大子节点，则打破循环
            if(!less(k,j)) break;
            exch(k,j);
            k=j;
        }
    }
}

基于堆的索引优先队列

适用于优先队列中的元素已经被多个地方的无关用例代码用整数索引来引用的情况
待修改：

public class IndexMinPQ <Key extends Comparable<Key>>{
    private int N;
    //元素对于的整数索引,索引二叉堆，这个是堆
    private int[] pq;
    //整数索引在pq中的位置，可以直接实现索引的访问与修改;访问索引i:pq[qp[i]]
    private int[] qp;
    //元素
    private Key[] keys;
    public IndexMinPQ(int maxN){
        keys = (Key[]) new Comparable[maxN+1];
        pq = new int[maxN+1];
        qp = new int[maxN+1];
        for(int i = 0;i<=maxN;i++) qp[i] =-1;
    }
    public Boolean isEmpty(){
        return N ==0;
    }
    public boolean contains(int k){
        return qp[k] !=-1;
    }
    public void insert(int k,Key key){
        N++;
        qp[k] = N;
        qp[N] = k;
        keys[k]=key;
        swim(N);
    }
    public Key min(){
        return keys[pq[1]];
    }
    public int delMin(){
        int indexOfMin = pq[1];
        exch(1,N--);
        sink(1);
        keys[pq[N+1]] = null;
        qp[pq[N+1]] = -1;
        return indexOfMin;
    }
    //从下到上，将更大的节点向上传递
    private void swim(int k){
        while(k>1&&less(k/2,k)){
            exch(k/2,k);
            k = k/2;
        }
    }
    //从上到下，将顶部的节点向下传递
    private void sink(int k){
        while(2*k<=N){
            int j = 2*k;
            //选出当前节点的最大子节点
            if(j<N&&less(j,j+1)) j++;
            //若当前节点不小于选出的最大子节点，则打破循环
            if(!less(k,j)) break;
            exch(k,j);
            k=j;
        }
    }
    private boolean less(int i,int j){
        return keys[pq[i]].compareTo(keys[pq[j]])<0;
    }
    private void exch(int i,int j){
        int t1 = pq[i];pq[i] = pq[j];pq[j] = t1;
        int t2 = qp[i];qp[i] = qp[j];qp[j] = t2;
    }
    //返回最小元素的索引
    public int minIndex(){
        return pq[1];
    }
    //将索引为k的元素设为key
    public void change(int k,Key key){
        keys[k] = key;
        //索引为k的元素的位置
        swim(qp[k]);
        sink(qp[k]);
    }
    public void delete(int k){
        int index = qp[k];
        exch(index,N--);
        swim(index);
        sink(index);
        keys[k] = null;
        qp[k]=-1;
    }
}

小结

多数情况下快速排序是最佳选择；当稳定性很重要，且空间又不是问题的同时，归并排序也还行。
原始类型数据的排序更快，非原始类数据排序过程中存储引用所需要的空间以及引用访问的成本再加上调用方法的开销都是比原始类型多得多。
Java系统库中的主要排序方法java.tuil.Arrays.sort();根据不同的参数类型，都代表了一系列排序算法
以上算法包括了Java现代系统的核心组成部分，所以实际应用开发中Java的Arrays.sort()实现再加上自己实现的CompareTo()、compare()已经够用，因为这里面已经涵盖了经典的三向快速排序以及归并排序。

各种排序算法的性能特点

查找

小错误

抽象类中的静态方法不可以被重写
抽象方法不可以是静态的
Raw use of parameterized class '*':含有泛型参数的类不能使用其原生态类型，不能不对泛型参数进行定义便将该泛型类进行使用
unchecked call to * as a member of the raw type $:泛型的引用后面没有规定类型
泛型数组创建存在的问题

《算法》读书笔记（未完）