排序篇：
冒泡排序：
?原理
? ??趟一趟的比，每一趟中，循環(huán)剩余的數(shù)，和后一個(gè)進(jìn)行比較，若比它小則交換。這樣一趟下來最小的在第一個(gè)，最大的在最后一個(gè)。總共比n-1趟。
/**
* 最簡(jiǎn)單的冒泡排序
* 原理：比較相鄰兩個(gè)元素，從第一對(duì)開始比較一直到最后一對(duì)，若順序不對(duì)就交換（感覺就像冒泡一樣）。
*? ? ? 一趟比較后，最大（或最?。┑臅?huì)位于最后的位置，然后再以類似方式比較前面的元素。
*/
public class BubbleSort extends Sortable {
public BubbleSort(){
super.LABLE = "冒泡排序";
}
@Override
public void sort(int[] a) {
for(int i=0;i
for(int j=0;j
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
}
時(shí)間復(fù)雜度（n^2)
選擇排序:
?原理
? ? 選擇排序可以說是最好理解的算法。就是每次遍歷一趟，找出最小的數(shù)，放到最前端。（這里說的是最前，是指無序的隊(duì)列中的最前
public void sort(int[] a) {
? ? ? ? for(int i=0;i
? ? ? ? ? ? int min=i;
? ? ? ? ? ? for(int j=i+1;j
? ? ? ? ? ? ? ? if(less(a[j],a[min])){
? ? ? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? exch(a,i,min);
? ? ? ? }
插入排序
? ??時(shí)間復(fù)雜度O(n2)。
? ? 遍歷未排序序列。把未排序數(shù)列的第一個(gè)數(shù)和已排序數(shù)列的每一個(gè)數(shù)比較，若比它大則交換。經(jīng)典的理解方式就是理解成摸牌時(shí)候理牌的順序。我上面的實(shí)現(xiàn)是直接交互數(shù)字，若是把大的數(shù)直接往后移效率還會(huì)更高。
public void sort(int[] a) {
? ? ? ? for(int i=1;i<a.length;i++){
? ? ? ? ? ? for(int j=i;j>0;j--){
? ? ? ? ? ? ? ? if(less(a[j],a[j-1])){
? ? ? ? ? ? ? ? ? ? exch(a,j,j-1);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else break;
? ? ? ? ? ? }
? ? ? ? }
?適合插入排序的數(shù)據(jù)
? ? 當(dāng)你的數(shù)據(jù)是基本有序的時(shí)候且數(shù)據(jù)量小，利用插入排序的時(shí)候，效率會(huì)很高。若數(shù)據(jù)為逆序的話，效率很低。
希爾排序
? ? 可以看出是插入排序的一種優(yōu)化，或者是預(yù)處理。希爾排序就是先進(jìn)行h-sort，也就是讓間隔為h的元素都是有序的。普通的插入排序就是1-sort。
?原理
? ? 主要就是選定一個(gè)h的有序數(shù)組來進(jìn)行預(yù)排序。這樣最后進(jìn)行插入排序的時(shí)候，能使數(shù)據(jù)局部有序。就算交換的話，交換的次數(shù)也不會(huì)很多。這樣h序列稱為遞增序列。希爾的性能很大部分取決于遞增序列.一般來說我們使用這個(gè)序列3x + 1.
public void sort(int[] a) {
? ? ? ? int h=1;
? ? ? ? while(h
? ? ? ? ? ? h=3*h+1;
? ? ? ? }
? ? ? ? while(h>=1){
? ? ? ? ? ? for(int i=h;i
? ? ? ? ? ? ? ? for(int j=i;j>=h;j=j-h){
? ? ? ? ? ? ? ? ? ? if(less(a[j],a[j-h])){
? ? ? ? ? ? ? ? ? ? ? ? exch(a,j,j-h);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? h=h/3;
? ? ? ? }
? ? }
? 性能
? ? 對(duì)于希爾排序的性能其實(shí)無法準(zhǔn)確表示。介于O(nlogn)和O(n2)之間，大概在n的1.5次冪左右。
? ? 希爾排序?qū)τ谥写笮蛿?shù)據(jù)的排序效率是很高的，而且占用空間少，代碼量短。而且就算是很大的數(shù)據(jù)，用類似快排這種高性能的排序方法，也僅僅只比希爾快兩倍或者不到。
歸并排序
? ? 復(fù)雜度O(nlogn).
? ? 核心思想就是采用分而治之的方法，遞歸的合并兩個(gè)有序的數(shù)組。效率比較高，缺點(diǎn)是空間復(fù)雜度高，會(huì)用到額外的數(shù)組。
/**
* 歸并排序
* @author anxpp.com
*
*/
public class MergeSort extends Sortable {
public MergeSort(){
super.LABLE = "歸并排序";
}
? ? int[] temp ;
? ? private void merge(int[] a, int l, int m, int h){
? ? ? ? for(int i=l;i<=h;i++){
? ? ? ? ? ? temp[i]=a[i];
? ? ? ? }
? ? ? ? int i=l;
? ? ? ? int j=m+1;
? ? ? ? for(int k=l;k<=h;k++){
? ? ? ? ? ? if(i>m) a[k]=temp[j++];
? ? ? ? ? ? else if(j>h) a[k]=temp[i++];
? ? ? ? ? ? else if(less(temp[i],temp[j])) a[k]=temp[i++];
? ? ? ? ? ? else a[k] = temp[j++];
? ? ? ? }
? ? }
? ? private void sort(int[] a,int l,int h) {
? ? ? ? if(l
? ? ? ? ? ? int mid = (l+h)/2;
? ? ? ? ? ? sort(a,l,mid);
? ? ? ? ? ? sort(a,mid+1,h);
? ? ? ? ? ? if (!less(a[mid+1], a[mid])) return;
? ? ? ? ? ? merge(a,l,mid,h);
? ? ? ? }
? ? }
? ? @Override
? ? public void sort(int[] a) {
? ? ? ? temp = new int[a.length];
? ? ? ? sort(a,0,a.length-1);
? ? }
}
? 如果遞歸時(shí)判斷已經(jīng)有序則不用繼續(xù)遞歸。也可以增加效率。
private void sort(int[] a,int l,int h) {
if(l
int mid = (l+h)/2;
sort(a,l,mid);
sort(a,mid+1,h);
if (!less(a[mid+1], a[mid])) return;
merge(a,l,mid,h);
}
}
? ??另外在合并時(shí)交互兩個(gè)數(shù)組的順序，能節(jié)省復(fù)制數(shù)組到輔助數(shù)組的時(shí)間，但節(jié)省不了空間。
快速排序
? ? 傳說中最快的排序算法，聽說能裸寫快排，月薪可上10k...
? ? 快排平均情況下時(shí)間復(fù)雜度O(nlogn)，最糟糕情況O(n2)。O(n2)主要是因?yàn)檫x定的主元是極端值造成的，比如說最大值，最小值。不過這種情況一般很少出現(xiàn)，所以在進(jìn)行快排之前我們需要對(duì)數(shù)組進(jìn)行亂序，盡量避免這種情況的發(fā)生。
? ? 第一步打亂數(shù)組。
? ? 然后也是分治法。歸并是先分再合并?？炫攀窍扰判蛟俜謩e排序兩邊。
? ? 排序過程核心思想是為了選出一個(gè)數(shù)，把數(shù)組分成左右兩邊，左邊比主元小，右邊比主元大。
? ? 選定第一個(gè)數(shù)作為主元。然后設(shè)定兩個(gè)index指向數(shù)組首尾，比如i，j。接著從兩邊向中間掃描，分別用a[i]和a[j]和主元比較。若兩邊位置不對(duì)則交換a[i]和a[j]，比如說a[i]在掃描過程中遇到a[i]>主元，那么則停止掃描,因?yàn)槲覀冃枰筮叺臄?shù)小于主元,反正右邊也一樣等到a[j]也停下來,則交換a[i]和a[j]。
private void sort(int[] a,int low,int high){
//左
int l =low;
//右
int h = high;
//基準(zhǔn)值
int k = a[low];
//判斷一趟是否完成
while(l
//若順序正確就比較下一個(gè)
while(l=k)
h--;
if(l
int temp = a[h];
a[h] = a[l];
a[l] = temp;
l++;
}
while(l
l++;
if(l
int temp = a[h];
a[h] = a[l];
a[l] = temp;
h--;
}
}
if(l>low) sort(a,low,l-1);
if(h
}
@Override
public void sort(int[] a) {
sort(a,0,a.length-1);
}
?適用范圍
? ? 雖然快速排序是不穩(wěn)定的。但快速排序通常明顯比其他Ο(nlogn)算法更快，因?yàn)樗膬?nèi)部循環(huán)很小。快速排序在對(duì)重復(fù)數(shù)據(jù)的排序時(shí)，會(huì)重復(fù)劃分?jǐn)?shù)據(jù)進(jìn)行排序。雖然性能也還行，但這里可以進(jìn)行改進(jìn)，就是下面介紹的三向切分排序。
堆排序
? ? 時(shí)間復(fù)雜度O(nlogn)，堆排序主要用二叉堆實(shí)現(xiàn)，在講堆排序之前我們可以要先了解下二叉堆。
? ? 所謂的二叉堆用一顆二叉樹表示，也就是每一個(gè)節(jié)點(diǎn)都大于它的左右子節(jié)點(diǎn)。也就是說根節(jié)點(diǎn)是最大的。
? ? 二叉樹用數(shù)組存儲(chǔ)，可以用下標(biāo)來表示節(jié)點(diǎn)。比如i這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)為i/2，左兒子為2*i，右兒子為2*i+1.
? ? 堆的操作主要有兩種上浮和下沉。主要對(duì)應(yīng)兩種情況，比如在數(shù)組末尾添加節(jié)點(diǎn)，此時(shí)需要上浮節(jié)點(diǎn)，保證二叉堆的特點(diǎn)。反之在替換根節(jié)點(diǎn)是則需要下沉操作。
? ??分為兩步。
? ? 把數(shù)組排成二叉堆的順序
? ? 調(diào)換根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)的位置，然后對(duì)根節(jié)點(diǎn)進(jìn)行下沉操作。
?適用范圍
? ? 堆排序也是不穩(wěn)定的。
? ? 堆排序在空間和時(shí)間上都是O(nlogn),且沒有最糟情況，但在平均情況下比快排慢。
? ? 所以現(xiàn)在大部分應(yīng)用都是用的快排，因?yàn)樗钠骄屎芨撸瑤缀醪粫?huì)有最糟情況發(fā)生。
? ? 但如果你的應(yīng)用非常非常重視性能的保證，比如一些醫(yī)學(xué)上的監(jiān)控之類的。
? ? 那么可以使用堆排序。還有一個(gè)堆排序的缺點(diǎn)，是它無法利用緩存，幾乎很少和相鄰元素的比較。
