選擇排序

優(yōu)點：容易實現(xiàn)，原地排序不需要額外的存儲空間

缺點：擴展性差

void SelectSort(){
    int [] array={1,5,3,2,6,7,9,13,54,20};
    int min=0;//保存最元素值的下標(biāo)
    for(int i=0;i<array.length-1;i++){
        min=i;
        //查找最小數(shù)在數(shù)組中的下標(biāo)
        for(int j=i+1;j<array.length;j++){
            if(array[min]>array[j]){
                min=j;//保存最小數(shù)的下標(biāo)
            }
        }
        //如果第i個最小的數(shù)位置不在i上,則進行交換
        if(i!=min){
            int temp=array[i];
            array[i]=array[min];
            array[min]=temp;
        }
    }
}

冒泡排序

按照改進的算法，對于一個已經(jīng)有序的數(shù)組，算法完成第一次外層循環(huán)后就會返回。
實際上只發(fā)生了 N - 1次比較，所以最好的情況下，該算法復(fù)雜度是O(n)。

void BubbleSort(){
    int [] array={1,5,3,2,6,7,9,13,54,20};
    for(int i=0;i<array.length-1;i++){
        //每一輪比較的次數(shù)為N-1-i;
        for(int j=0;j<array.length-1-i;j++){
            //比較相鄰的兩個數(shù),小靠前
            if(array[j]>array[j+1]){
                //兩個數(shù)做交換.通過設(shè)置臨時變量
                int temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
            }
        }
    }
}

void BubbleSortImproved(){
    int [] array={1,5,3,2,6,7,9,13,54,20};
    boolean swapped=true;
    for(int i=0;i<array.length-1&&swapped;i++){
        swapped=false;
        //每一輪比較的次數(shù)為N-1-i;
        for(int j=0;j<array.length-1-i;j++){
            //比較相鄰的兩個數(shù),小靠前
            if(array[j]>array[j+1]){
                //兩個數(shù)做交換.通過設(shè)置臨時變量
                int temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                swapped=true;
            }
        }
    }
}

插入排序

優(yōu)點：實現(xiàn)簡單，數(shù)據(jù)量少時效率高

? 如果輸入序列已經(jīng)預(yù)排序，時間復(fù)雜度為O(n+d),d是反轉(zhuǎn)的次數(shù)。

? 算法運行效率優(yōu)于選擇排序冒泡排序即使是最壞的情況三個算法時間復(fù)雜度均為O($n^2$)

? 能在接收序列的同時進行排序

void InsertSort(){
    int [] array={20,25,15,42,36,16,12};
    for(int i=1;i<array.length;i++){
        int temp=array[i];
        //把下標(biāo)保存起來
        int j=i;
        while(j>0&&temp<array[j-1]){
            //上面的數(shù)覆蓋其下面的數(shù)
            array[j]=array[j-1];
            j--;
        }
        array[j]=temp;//插入數(shù)據(jù)
    }
}

希爾排序

希爾排序是基于直接插入排序的，直接插入排序在元素較少和元素基本有序時效率是不錯的，但隨著元素增多和有序性破壞，效率會下降的很明顯。希爾排序通過分組實現(xiàn)跳躍式移動，保證待排序序列基本有序后再排序，就能提高效率。

void ShellSort(){
    int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
    int d=a.length;
    while(true){
        d=d/2;
        for(int x=0;x<d;x++) {
            for(int i=x+d;i<a.length;i=i+d) {
                int temp=a[i];
                int j;
                for(j=i-d;j>=0&&a[j]>temp;j=j-d) {
                    a[j+d]=a[j];
                }
                a[j+d]=temp;
            }
        }
        if(d==1) {
            break;
        }
    }
}

歸并排序

歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個有序序列。

int[] sort(int[] o,int m,int n){
    int mid;
    int[] result = new int[o.length];
    if(o.length == 1|| m==n){
        result[0] = o[0];
    }else{
        mid = (m+n)/2;
        int[] temp1 = new int[mid-m+1];
        int[] temp2 = new int[o.length-mid+m-1];
        System.arraycopy(o,0,temp1,0,mid-m+1);
        System.arraycopy(o,mid-m+1,temp2,0,o.length-mid+m-1);
        int[] result1 = sort(temp1,m,mid);
        int[] result2 = sort(temp2,mid+1,n);
        result = Merge(result1,result2);
    }
    return result;
}
int[] Merge(int[] i,int[] j){
    int m=0,n=0,k=0;
    int[] result = new int[i.length+j.length];
    for(; m<i.length&&n<j.length; k++){
        if(i[m]<j[n]){
            result[k] = i[m++];
        }else{
            result[k] = j[n++];
        }
    }
    if(m<i.length){
        while(m<i.length){
            result[k++] = i[m++];
        }
    }
    if(n<j.length){
        while(n<j.length){
            result[k++] = j[n++];
        }
    }
    return result;
}

快速排序

快速排序的思想是分割，是分治算法技術(shù)的一個實例。確保一個元素左邊的元素都小于這個元素，右邊的元素都大于這個元素，然后對這兩部分分別繼續(xù)進行分割，從而達到排序的效果。

void Quicksort(int[] a,int low,int high){
    int temp;
    if(low<high){
        temp = partition(a,low,high);
        Quicksort(a,low,temp-1);
        Quicksort(a,temp+1,high);
    }
}

int partition(int[] a,int low,int high){
    int i=low;
    int j=high;
    while(i<j){
        while(i<j&&a[i]<=r[j]) j--;//右側(cè)掃描
        if(i<j){swap(a,i,j);i++;}//小記錄置前
        while(i<j&&a[i]<=r[j]) i++;//左側(cè)掃描
        if(i<j){swap(a,i,j);j--}//大記錄置后
    }
    return low;
}
void swap(int[] a,int low,int high){
    if(low<high){
        int temp=a[low];
        a[low]=a[high];
        a[high]=a[low];
    }
}

堆排序

基于比較的排序，屬于選擇排序，優(yōu)點是最壞的情況下O($n\log n$)

基本思想：首先將待排序的記錄序列構(gòu)造成一個堆，此時，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。

 void HeapSort(int[] a,int n){
        for(int i=n/2; i>=1; i--){
            heapAdjust(a,i,n);//從最后一個有子節(jié)點的節(jié)點開始依次往前調(diào)整對應(yīng)節(jié)點來生成大頂堆
        }
        for(int i=1; i<n; i++){
            swap(a,1,n-i-1);//交換堆頂元素與未排序堆最后一個元素
            heapAdjust(a,1,n-i);//根據(jù)調(diào)整節(jié)點重新生成大頂堆
        }
}
    void heapAdjust(int r[], int k, int m ){
        //要篩選結(jié)點的編號為k，堆中最后一個結(jié)點的編號為m
        int i=k;
        int  j=2*i;//到達下一層的左孩子
        while (j<=m ){           //篩選還沒有進行到葉子
            if (j<m && r[j]<r[j+1]) j++;  //左右孩子中取較大者
            if (r[i]>r[j]) break;
            else {
                swap(r,i,j);
                i=j;
                j=2*i;
            }
        }

    }

線性排序-計數(shù)排序

計數(shù)排序的基本思想是對于給定的輸入序列中的每一個元素x，確定該序列中值小于x的元素的個數(shù)（此處并非比較各元素的大小，而是通過對元素值的計數(shù)和計數(shù)值的累加來確定）。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小于x的值，則x可以直接存放在輸出序列的第18個位置上。

犧牲空間換取時間，當(dāng)K=O(n)時計數(shù)排序速度快，否則復(fù)雜度將會更高

int[] CountSort(int[]a){
        int b[] = new int[a.length];
        int max = a[0],min = a[0];
        for(int i:a){
            if(i>max){
                max=i;
            }
            if(i<min){
                min=i;
            }
        }
        int k=max-min+1;//這里k的大小是要排序的數(shù)組中，元素大小的極值差+1
        int c[]=new int[k];
        for(int i=0;i<a.length;++i){//O(n)
            c[a[i]-min]+=1;//優(yōu)化過的地方，減小了數(shù)組c的大小
        }
        for(int i=1;i<c.length;++i){//O(k)
            c[i]=c[i]+c[i-1];
        }
        for(int i=a.length-1;i>=0;--i){//O(n)
            b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
        }
        return b;
    }

線性排序-桶排序

與計數(shù)排序類似，桶排序也對輸入加以限制來提高算法性能。換言之。如果輸入的序列來自固定集合，則桶排序的效率較高。例如假設(shè)所有輸入元素是在【0，k-1】上的整數(shù)集合，這就表示k是輸入序列中最遠距離元素的數(shù)目。桶排序采用K個計數(shù)器，第i個計數(shù)器記錄第i個的元素出現(xiàn)次數(shù)。

static int BUCKET=10;
void BucketSort(int A[],int array_size){
    int[] bucket=new int[BUCKET];
    for(int i=0;i<BUCKET;i++)bucket[i]=0;
    for(int i=0;i<array_size;i++)++bucket[A[i]];
    for(int i=0,j=0;j<BUCKET;j++){
        for(int k=bucket[j];k>0;--k){
            A[i++]=j;
        }
    }
}

線性排序-基數(shù)排序

1）取每個元素最低有效位

2）基于最低有效位對序列中的元素進行排序，并保持具有相同位的元素的原有次序（穩(wěn)定排序）

3）對下一個最低有效位重復(fù)該過程

基數(shù)排序速度取決于內(nèi)部基本操作。如果輸入值具有的位數(shù)長度不等。還需要對附加位進行排序，這是基數(shù)排序最慢的部分之一，也是最難進行效率優(yōu)化的部分之一。

算法靈活性不如其他排序算法，對于每一種不同類型數(shù)據(jù)，基數(shù)排序都需要重寫，難以編寫一個處理所有數(shù)據(jù)的通用基數(shù)排序算法。

void RadixSort(int[] number, int d){ //d表示最大的數(shù)有多少位
    int k = 0;
    int n = 1;
    int m = 1; //控制鍵值排序依據(jù)在哪一位
    int[][]temp = new int[10][number.length]; //數(shù)組的第一維表示可能的余數(shù)0-9
    int[]order = new int[10]; //數(shù)組orderp[i]用來表示該位是i的數(shù)的個數(shù)
    while(m <= d) {
        for(int i = 0; i < number.length; i++) {
            int lsd = ((number[i] / n) % 10);
            temp[lsd][order[lsd]] = number[i];
            order[lsd]++;
        }
        for(int i = 0; i < 10; i++) {
            if(order[i] != 0)
                for(int j = 0; j < order[i]; j++) {
                    number[k] = temp[i][j];
                    k++;
                }
            order[i] = 0;
        }
        n *= 10;
        k = 0;
        m++;
    }
}

性能比較