排序

排序模板

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);
            }
        }
    }
}

希爾排序

希爾排序基于插入排序谜喊，插入排序的比較與交換是相鄰元素之間的所以大規(guī)模的亂序會很慢，希爾排序的思想是將數(shù)組中任意間隔為h的元素都是有序的倦始，即是說希爾排序意在構(gòu)建多個相互獨(dú)立的有序數(shù)組斗遏。伴隨著間隔逐漸的縮減為1后便是有序數(shù)組，而各個間隔為h的獨(dú)立數(shù)組的實(shí)現(xiàn)都是插入排序楣号。
對于中等大小的數(shù)組最易，希爾排序的運(yùn)行時(shí)間是可以接受的，代碼量小炫狱，且不需要使用額外的內(nèi)存藻懒，對于很大的N其它高效算法只會比希爾排序快兩倍左右，但其更復(fù)雜视译。
此處希爾排序?qū)崿F(xiàn)中的h的使用的是實(shí)時(shí)計(jì)算出的1/2（3^k-1）序列嬉荆，也可以將h的序列存儲在數(shù)組當(dāng)中供使用。

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;
        }
    }
}

歸并排序

歸并排序的實(shí)現(xiàn)思想為：先將左邊排序酷含，再將右邊排序鄙早，最后左右統(tǒng)一起來汪茧，在自頂向下調(diào)用的過程中總是先排左再排右最后聯(lián)合，有種后序遍歷的感覺限番，排序主要右merge算法實(shí)現(xiàn)舱污。
歸并排序在最壞的情況下的比較次數(shù)是~NlgN，這是任何最好的算法在最壞的情況下的最小的比較次數(shù)弥虐。

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;
    }
}

快速排序

快速排序適用于各種不同的輸入數(shù)據(jù)且在一般應(yīng)用中比其他排序算法都要快得多扩灯。并且快速排序是原地排序，只需要一個很小的輔助棧霜瘪，不會有太多余的內(nèi)存開銷珠插，將長度為N的數(shù)組排序所需要的時(shí)間和NlgN成正比。
快速排序有著分治的思想：將一個數(shù)組分為兩個數(shù)組颖对，當(dāng)兩個子數(shù)組都有序時(shí)捻撑，整個數(shù)組自然有序了。
快速排序的缺點(diǎn)便是很脆弱缤底，一不小心便會使得性能變得惡劣顾患，主要注意一下幾個點(diǎn)：原地切分（不在遞歸調(diào)用中新建數(shù)組）；越界训堆；保持隨機(jī)性（消除對輸入的依賴）描验；終止循環(huán)；終止遞歸坑鱼；切分元素值會有重復(fù)的情況

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){
        //該算法實(shí)現(xiàn)的核心思想是將數(shù)組首位的元素放在合適的位置膘流，使得元素左邊的小于元素右邊的
        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){
            //從左到右遍歷，直到某一值大于首位元素鲁沥，或者遍歷完整個數(shù)組
            while(less(a[++i],v))
                if(i==hi)break;
            //從右到左遍歷呼股，直到某一值小于首位元素，或者遍歷完整個數(shù)組
            while(less(v,a[--j]))
                if(j==lo)break;
                
            if(i>=j) break;
            //交換該兩元素画恰，使得整個數(shù)組呈現(xiàn)左邊小右邊大的趨勢
            exch(a,i,j);
        }
        //此時(shí)整個數(shù)組已經(jīng)遍歷完畢彭谁，掃描指針已經(jīng)重合，重合的位置有著左邊小右邊大的特點(diǎn)允扇，將首元素移動該位置缠局，并返回以供歸并
        exch(a,lo,j);
        return j;
    }
}

對于小數(shù)組而言，可以做如下更改將快速排序切換到插入排序
if(hi<=lo) return;
更改為
if(hi<=lo+M){Insertion.sort(a,lo,hi); return;}
當(dāng)數(shù)據(jù)具有大量重復(fù)元素時(shí)考润，通過將原切分
a[lo,j-1]<v=a[j]<a[j+1,hi]
更改為
a[lo..lt-1]<v=a[lt,gt]<a[gt+1,hi]
具體實(shí)現(xiàn)為三向切分的快速排序

三向切分的快速排序

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);
    }
}

堆/隊(duì)列

堆常為優(yōu)先隊(duì)列的實(shí)現(xiàn)采用的數(shù)據(jù)結(jié)構(gòu)狭园，由于優(yōu)先隊(duì)只在乎極值，所以在實(shí)現(xiàn)過程中少去了許多比較與交換糊治。

基于堆的優(yōu)先隊(duì)列

public class MaxPQ <Key extends Comparable<Key>>{
    //基于堆的完全二叉樹唱矛，pq[0]未使用
    private Key[] pq;
    private int N=0;
    //創(chuàng)建優(yōu)先隊(duì)列
    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處不再使用，設(shè)為null以便系統(tǒng)回收空間
        pq[N+1]=null;
        sink(1);
        return max;
    }
    //返回隊(duì)列是否為空
    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;
    }

    //從下到上绎谦，將更大的節(jié)點(diǎn)向上傳遞
    private void swim(int k){
        while(k>1&&less(k/2,k)){
            exch(k/2,k);
            k = k/2;
        }
    }
    //從上到下管闷，將頂部的節(jié)點(diǎn)向下傳遞
    private void sink(int k){
        while(2*k<=N){
            int j = 2*k;
            //選出當(dāng)前節(jié)點(diǎn)的最大子節(jié)點(diǎn)
            if(j<N&&less(j,j+1)) j++;
            //若當(dāng)前節(jié)點(diǎn)不小于選出的最大子節(jié)點(diǎn)，則打破循環(huán)
            if(!less(k,j)) break;
            exch(k,j);
            k=j;
        }
    }
}

基于堆的索引優(yōu)先隊(duì)列

適用于優(yōu)先隊(duì)列中的元素已經(jīng)被多個地方的無關(guān)用例代碼用整數(shù)索引來引用的情況
待修改：

public class IndexMinPQ <Key extends Comparable<Key>>{
    private int N;
    //元素對于的整數(shù)索引,索引二叉堆窃肠，這個是堆
    private int[] pq;
    //整數(shù)索引在pq中的位置包个，可以直接實(shí)現(xiàn)索引的訪問與修改;訪問索引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;
    }
    //從下到上，將更大的節(jié)點(diǎn)向上傳遞
    private void swim(int k){
        while(k>1&&less(k/2,k)){
            exch(k/2,k);
            k = k/2;
        }
    }
    //從上到下冤留，將頂部的節(jié)點(diǎn)向下傳遞
    private void sink(int k){
        while(2*k<=N){
            int j = 2*k;
            //選出當(dāng)前節(jié)點(diǎn)的最大子節(jié)點(diǎn)
            if(j<N&&less(j,j+1)) j++;
            //若當(dāng)前節(jié)點(diǎn)不小于選出的最大子節(jié)點(diǎn)赃蛛，則打破循環(huán)
            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的元素設(shè)為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;
    }
}

小結(jié)

多數(shù)情況下快速排序是最佳選擇；當(dāng)穩(wěn)定性很重要搀菩，且空間又不是問題的同時(shí)，歸并排序也還行破托。
原始類型數(shù)據(jù)的排序更快肪跋，非原始類數(shù)據(jù)排序過程中存儲引用所需要的空間以及引用訪問的成本再加上調(diào)用方法的開銷都是比原始類型多得多。
Java系統(tǒng)庫中的主要排序方法java.tuil.Arrays.sort();根據(jù)不同的參數(shù)類型土砂，都代表了一系列排序算法
以上算法包括了Java現(xiàn)代系統(tǒng)的核心組成部分州既，所以實(shí)際應(yīng)用開發(fā)中Java的Arrays.sort()實(shí)現(xiàn)再加上自己實(shí)現(xiàn)的CompareTo()、compare()已經(jīng)夠用萝映，因?yàn)檫@里面已經(jīng)涵蓋了經(jīng)典的三向快速排序以及歸并排序吴叶。

各種排序算法的性能特點(diǎn)

查找

小錯誤

抽象類中的靜態(tài)方法不可以被重寫
抽象方法不可以是靜態(tài)的
Raw use of parameterized class '*':含有泛型參數(shù)的類不能使用其原生態(tài)類型，不能不對泛型參數(shù)進(jìn)行定義便將該泛型類進(jìn)行使用
unchecked call to * as a member of the raw type $:泛型的引用后面沒有規(guī)定類型
泛型數(shù)組創(chuàng)建存在的問題

《算法》讀書筆記（未完）