插入排序
復(fù)雜度
最優(yōu) O(N)
最差 O(N^2)
平均 O(N^2)
空間 O(1)
穩(wěn)定排序
思路
插排的思路是保證遍歷到每個(gè)元素時(shí)呼伸，該元素前面的序列都是有序的谨垃。
基于這個(gè)前提，我們將遍歷到的新元素和它前面的序列相比對(duì)，然后將這個(gè)元素插入到適當(dāng)?shù)奈恢没屑沟眠@個(gè)包含新元素的序列也是有序的。
雖然外層遍歷只要O(N)時(shí)間，但是因?yàn)檎业叫略氐倪m當(dāng)位置后要將之后的所有元素后移峰伙，所以最差時(shí)間是O(N^2）。
public class InsertionSort<T extends Comparable> {
public T[] sort(T[] a){
T[] array=a;
T tmp;
for(int i = 1; i<a.length; i++){
tmp=array[i];
int j;
// 從后向前找到插入新元素的適當(dāng)位置该默，比新元素大的都后移一位
for(j=i;j>0;j--){
if(array[j-1].compareTo(tmp)<0) break;
array[j]=array[j-1];
}
// 較大的元素都后移了一位瞳氓，這里只要插入這個(gè)新元素，則新序列還是有序的
array[j]=tmp;
}
return array;
}
}
希爾排序
復(fù)雜度
最優(yōu) O(N)
最差 O(N^2)
空間 O(1)
不穩(wěn)定排序
思路
插排的一個(gè)優(yōu)化是希爾排序栓袖，在原本的插入排序中顿膨，我們選擇以一個(gè)一個(gè)往后看等待插入的元素锅锨。
然而插入排序有這么一個(gè)性質(zhì)，即如果序列有序程度越高恋沃，則時(shí)間復(fù)雜度越低。
所以希爾排序利用了這個(gè)性質(zhì)必指，先通過(guò)較大的步長(zhǎng)進(jìn)行一次插入排序（不再是一個(gè)一個(gè)往后找待插元素囊咏，而是隔一個(gè)或者隔n/2個(gè)元素來(lái)找），
這樣每次子插排都能將序列變得更有序一點(diǎn)塔橡，而且因?yàn)椴介L(zhǎng)一開(kāi)始很大梅割，所以要遍歷的數(shù)少，時(shí)間復(fù)雜度也很低葛家。后來(lái)步長(zhǎng)變小了户辞，要遍歷的數(shù)
變多了，但數(shù)組也更有序了癞谒，時(shí)間復(fù)雜度也降低了底燎。當(dāng)然n/2^i這個(gè)步長(zhǎng)序列不是最好的，最好的步長(zhǎng)序列能使最差復(fù)雜度降低至O(N(logN)^2)
public class Shellsort {
public static <T extends Comparable<? super T>> T[] sort(T[] a) {
int j = 0;
// 從n/2開(kāi)始選擇步長(zhǎng)弹砚，每輪插排后減少步長(zhǎng)双仍，直到步長(zhǎng)為1是最后一次
for (int gap = a.length / 2; gap > 0; gap /= 2) {
T tmp = null;
// 步長(zhǎng)為gap的插入排序
for(int i = gap; i<a.length; i++){
tmp = a[i];
// 找到合適的插入點(diǎn)
for(j=i;j>=gap&&tmp.compareTo(a[j-gap])<0;j-=gap){
a[j]=a[j-gap];
}
a[j]=tmp;
}
}
return a;
}
}
選擇排序
復(fù)雜度
最優(yōu) O(N^2)
最差 O(N^2)
平均 O(N^2)
空間 O(1)
不穩(wěn)定排序
思路
選排的思路和插排相反，插排是搜索有序序列找到合適的位置桌吃，選排則是搜索剩余的無(wú)序序列選擇出其中最大（或最兄煳帧）的，并將這個(gè)被選擇的數(shù)放到無(wú)序序列的首部茅诱。
需要注意的是逗物。將這個(gè)數(shù)放到首部時(shí)，用的是交換的方法瑟俭。因?yàn)闊o(wú)論如何都要遍歷完子序列翎卓，所以時(shí)間復(fù)雜度至少是O(N^2)
public class SelectionSort<T extends Comparable> {
public T[] sort(T[] array) {
T[] a = array;
T tmp;
int minIndex;
for (int i = 0; i < a.length; i++) {
minIndex = i;
// 在剩余無(wú)序序列中找到一個(gè)最小的
for (int j = i; j < a.length; j++) {
if (a[minIndex].compareTo(a[j]) > 0)
minIndex = j;
}
// 將這個(gè)最小的交換到無(wú)序序列的首部
if (minIndex != i) {
tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}
return a;
}
}
歸并排序
復(fù)雜度
最優(yōu) O(NlogN)
最差 O(NlogN)
平均 O(NlogN)
空間 O(N)
穩(wěn)定排序
思路
歸并排序是典型的分治法《保基本思路是將一個(gè)較長(zhǎng)數(shù)組一分為二莲祸，我們將它的左右兩半部分分別排好序，然后將這有序的兩部分合并起來(lái)椭迎，這樣較長(zhǎng)數(shù)組也是有序的了锐帜。
因?yàn)閮砂氩糠侄际怯行虻模院喜⒅恍枰瑫r(shí)遍歷一下兩半部分畜号，看誰(shuí)較薪裳帧（大）就把誰(shuí)先塞進(jìn)數(shù)組就可以了。根據(jù)這個(gè)思路简软，我們不停的二分蛮拔、二分述暂，這樣二分到
盡頭肯定只有一個(gè)數(shù)的數(shù)組，那它肯定是有序的建炫，然后我們將兩個(gè)只有一個(gè)數(shù)的數(shù)組合并畦韭，只要比較下這兩個(gè)數(shù)就行了。這樣就返回了一個(gè)有兩個(gè)數(shù)的有序數(shù)組肛跌，然后
再一直合并艺配、合并、直到合并出整個(gè)數(shù)組衍慎。不過(guò)转唉，在合并兩個(gè)子數(shù)組時(shí)，要先用一個(gè)臨時(shí)數(shù)組存放稳捆，否則會(huì)修改兩個(gè)子數(shù)組的數(shù)據(jù)（因?yàn)閮蓚€(gè)子數(shù)組實(shí)際上是原數(shù)組的
兩個(gè)子部分）赠法。
public class Mergesort<T extends Comparable<? super T>> {
private static <T extends Comparable<? super T>> T[] sort(T[] array, T[] tmp, int left, int right){
if(left<right){
// 計(jì)算二分中點(diǎn)位置
int center = (left+right)/2;
// 將左半部分排序
sort(array,tmp,left,center);
// 將右半部分排序
sort(array,tmp,center+1,right);
// 將左右兩半部分合并
merge(array,tmp,left,center+1,right);
}
return array;
}
public static <T extends Comparable<? super T>> T[] sort(T[] a){
T[] tmp = (T[]) new Comparable[a.length];
return sort(a,tmp,0,a.length-1);
}
private static <T extends Comparable<? super T>> void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd){
int leftEnd=rightPos-1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos +1;
// 將兩個(gè)有序數(shù)組的元素比較大小后合并成一個(gè)數(shù)組，存入一個(gè)臨時(shí)數(shù)組中
while(leftPos<=leftEnd && rightPos<=rightEnd){
if(a[leftPos].compareTo(a[rightPos])<0)
tmpArray[tmpPos++]=a[leftPos++];
else
tmpArray[tmpPos++]=a[rightPos++];
}
// 如果左半部分沒(méi)有合并完（說(shuō)明右半部分的數(shù)較星呛弧）砖织，將其合并進(jìn)去
while(leftPos<=leftEnd){
tmpArray[tmpPos++]=a[leftPos++];
}
// 如果右半部分沒(méi)有合并完（說(shuō)明左半部分的數(shù)較小）驯嘱，將其合并進(jìn)去
while(rightPos<=rightEnd){
tmpArray[tmpPos++]=a[rightPos++];
}
// 將這個(gè)臨時(shí)數(shù)組拷貝回原數(shù)組
for(int i = 0;i<numElements;i++,rightEnd--){
a[rightEnd]=tmpArray[rightEnd];
}
}
}
快速排序
復(fù)雜度
最優(yōu) O(NlogN)
最差 O(N^2)
平均 O(NlogN)
空間 O(logN)
不穩(wěn)定排序
思路
快速排序也是分治的思想镶苞，它先選取一個(gè)樞紐值pivot，將整個(gè)數(shù)組按照樞紐值的大小重新排列鞠评，比樞紐值小的放在左邊茂蚓，比樞紐值大的放在右邊。
然后剃幌，我們?cè)俜謩e對(duì)這左半部分和右半部分進(jìn)行同樣的操作聋涨，這里半個(gè)部分不一定有半個(gè)數(shù)組的元素，要看具體有多少元素大于或小于樞紐值负乡。
一般情況下我們都選擇子數(shù)組的第一個(gè)值作為樞紐牍白，簡(jiǎn)化實(shí)現(xiàn)。最好還是能寫(xiě)個(gè)隨機(jī)選擇樞紐值的函數(shù)抖棘。最差的情況下茂腥，每次選到的樞紐值都是
最小（最大）的切省，所以每次分割出來(lái)的子數(shù)組都只比當(dāng)前整個(gè)數(shù)組小1的長(zhǎng)度最岗，就會(huì)導(dǎo)致O(N^2)的復(fù)雜度。
public class Quicksort {
public <T extends Comparable<? super T>> T[] sort(T[] a){
return sort(a,0,a.length);
}
private <T extends Comparable<? super T>> T[] sort(T[] a, int left, int right){
if(left==right-1) return null;
//Partition into two part first
int k=partition(a,left,right);
//Recurse on front part
sort(a,left,k);
//Recurse on rear part
sort(a,k,right);
return a;
}
private <T extends Comparable<? super T>> int partition(T[] a, int left, int right){
T p = a[left];
int i = left, j =right;
// 先找到右邊第一個(gè)小于樞紐值的數(shù)
do{
j--;
}while(a[j].compareTo(p)>0 && j>i);
//Swap a[i] and a[j] to partition
while(i<j){
// 將右邊那個(gè)小于樞紐值的數(shù)和左邊那個(gè)大于樞紐值的數(shù)交換（第一次交換的是樞紐值本身）
swap(a,i,j);
// 找到下一對(duì)可以交換的元素
do{
i++;
}while(a[i].compareTo(p)<0);
do{
j--;
}while(a[j].compareTo(p)>0);
}
//Elements before j+1 are partitioned, so we need to partition next part start from j+1
return j+1;
}
private <T extends Comparable<? super T>> void swap(T[] a, int i, int j){
T tmp = a[j];
a[j] = a[i];
a[i] = tmp;
}
}
外部排序
例題:
假設(shè)我們有1TB的數(shù)據(jù)需要排序朝捆，但是只有一臺(tái)1GB內(nèi)存的機(jī)器般渡，請(qǐng)問(wèn)如何排序？
思路
外部排序基于歸并排序的理念，以該題為例驯用，為了計(jì)算方便我們假設(shè)TB/GB/MB是以1000換算的脸秽，而且內(nèi)存也有1.001G空間：
將1TB數(shù)據(jù)分1000次讀入內(nèi)存中，每次對(duì)1GB的數(shù)據(jù)進(jìn)行排序蝴乔，每次排序完將其作為一個(gè)區(qū)塊結(jié)果存入磁盤(pán)中记餐。
在內(nèi)存中劃分1000個(gè)通道，每個(gè)通道讀入每個(gè)區(qū)塊前1MB的數(shù)據(jù)薇正，可知每個(gè)1MB都是有序的剥扣。
對(duì)這1000個(gè)有序的1MB數(shù)據(jù)進(jìn)行歸并。將結(jié)果存入一個(gè)1MB的緩存當(dāng)中铝穷，每當(dāng)這1MB緩存滿的時(shí)候，將這1MB緩存存入磁盤(pán)并清空佳魔。
每當(dāng)任何一個(gè)1MB通道空時(shí)曙聂，我們將對(duì)應(yīng)區(qū)塊的下1MB數(shù)據(jù)讀入這個(gè)通道。
持續(xù)執(zhí)行步驟3直到所有區(qū)塊的數(shù)據(jù)都被讀完鞠鲜，這時(shí)候磁盤(pán)中就是1TB有序的數(shù)據(jù)了宁脊。