分而治之是設(shè)計高效算法的一個重要思想。本文主要總結(jié)一下分治思想在排序算法中的運用。
排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計算中有著重要的地位，它能夠應(yīng)用于事物處理妆档、組合優(yōu)化、天體物理學(xué)借杰、分子動力學(xué)过吻、語言學(xué)进泼、基因組學(xué)蔗衡、天氣預(yù)報和很多其它領(lǐng)域∪槿疲——《算法》绞惦。
發(fā)展至今，已經(jīng)出現(xiàn)過很多的排序算法洋措。如選擇排序济蝉，插入排序，希爾排序菠发，堆排序王滤，歸并排序，快速排序滓鸠。這里主要總結(jié)下后面種雁乡，這種也是目前運用最廣和最高效的（雖然在某些特殊情況下，前面一些算法的效率更加高糜俗，但這里主要是針對一般情況下）踱稍，這2種排序是分治思想的典型運用（分治思想也就是把大問題轉(zhuǎn)化為小問題，然后分別去解決悠抹，最后整體歸并）珠月。
一、歸并排序
歸并楔敌，即將2個有序的數(shù)組歸并成一個更大的有序數(shù)組啤挎。而不管是歸并排序還是快速排序都是基于歸并進行操作的。
1.自頂向下的歸并排序卵凑。
具體思想是先將左半邊排序庆聘，然后將右半邊排序旺韭，最后將排序好的結(jié)果歸并起來。
如下
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,0,mid,hi); // 將排序好的結(jié)果歸并
}
注意進行歸并操作時掏觉，需要使用一個輔助數(shù)組区端。首先把需要排序的所有元素放入到一個輔助數(shù)組中，歸并時需要進行4個判斷:如果左半邊的元素取完就取右半邊的元素澳腹；如果右半邊的元素取完就取左半邊的元素织盼；如果右半邊的當(dāng)前元素小于左半邊
的當(dāng)前元素則取右半邊的元素；如果左半邊的當(dāng)前元素大于右半邊的當(dāng)前元素則取左半邊的元素酱塔。
最后看總體代碼
public class MergeSort {
// 定義一個輔助數(shù)組
private static Comparable[] aux;
public static void sort(Comparable[] a) {
// 分配輔助數(shù)組所需的空間
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,0,mid,hi); // 將排序好的結(jié)果歸并
}
public static void merge(Comparable[] a,int lo,int mid,int hi) {
int i=lo,j=mid+1;
// 將元素復(fù)制到輔助數(shù)組
for (int k=lo;k<=hi;k++) {
aux[k] = a[k];
}
// 對應(yīng)上面所述的4個判斷
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++];
}
}
}
// 元素v < w則返回true
public static boolean less(Comparable v,Comparable w) {
return v.compareTo(w) < 0;
}
}
2.自底向上的歸并排序
當(dāng)需要歸并的數(shù)組較小時沥邻，可以考慮另一種歸并排序方法，自底向上發(fā)散羊娃。首先將數(shù)組中的每個元素都想像成一個大小為1的數(shù)組唐全，然后兩兩歸并。把歸并后的結(jié)果想象成大小為2的數(shù)組蕊玷，繼續(xù)進行四四歸并邮利，接著八八歸并......以此類推，歸并完后的數(shù)組就是已經(jīng)排好序的數(shù)組垃帅。
代碼如下
public class MergeBU {
// 定義一個輔助數(shù)組
private static Comparable[] aux;
public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz=1;sz<N;sz=2*sz) { // sz：子數(shù)組大小
for (int lo=0;lo<N-sz;lo+=2*sz) { // lo:子數(shù)組索引
merge(a,lo,lo+sz-1,Math.min(lo+2*sz-1,N-1));
}
}
}
public static void merge(Comparable[] a,int lo,int mid,int hi) {
int i=lo,j = mid+1;
if (hi <= lo) return;
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++];
}
}
}
public static boolean less(Comparable v,Comparable w) {
return v.compareTo(w) < 0;
}
}
注意merge()方法中傳入的第4個參數(shù)延届，使用了Math中的min方法，因為這里涉及到邊界問題贸诚，對于一個數(shù)組我們不能確定它的大小是否剛好是2的多少次冪方庭。
二、快速排序
快速排序是被譽為二十世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一酱固，正因為它在處理不同數(shù)據(jù)方面平均情況下比其它排序算法都要快得多械念，所以它也目前是應(yīng)用最廣泛的排序算法了，快速排序和歸并排序是互補的运悲，快速排序是當(dāng)2個子數(shù)組都有序時龄减，整個數(shù)組也就有序了。
1.基本的快速排序
快速排序中扇苞，選定一個切分元素v 欺殿，然后分遍歷左右兩邊的元素，如果v左邊的元素小于v,則進行遞增操作鳖敷；繼續(xù)遍歷右邊脖苏，右邊元素大于v則進行遞減操作；其它情況下就把v左右兩邊的元素進行交換定踱，直到遍歷完整個數(shù)組棍潘。最后保證v左邊的元素都小于v，v右邊的元素都大于v。最終得到的切分元素v作為下一次進行排序的部分數(shù)組的邊界亦歉，用同樣的方式進行遞歸排序恤浪。
代碼如下
public class QuickSort {
public static void sort(Comparable[] a) {
StdRandom.shuffle(a); //消除對輸入的依賴
sort(a,0,a.length-1);
}
private static void sort(Comparable[] 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 static int partition(Comparable[] a,int lo,int hi) {
int i = lo,j = hi+1; // 定義左右掃描指針
Comparable v = a[lo]; // 初始化切分元素
/** 當(dāng)i和j相遇時退出循環(huán)
* a[i]小于v時增大i,a[j]大于v時減小j
* 然后交換a[i]和a[j],當(dāng)指針相遇時交換lo和j,切分結(jié)束
*/
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;
}
private static boolean less(Comparable v,Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a,int i,int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
2.三路快速排序
當(dāng)需要進行排序的數(shù)組出現(xiàn)大量重復(fù)的元素時，按理來說重復(fù)的元素應(yīng)該不必進行排序了肴楷，但是之前那種快速排序還是會對它們進行切分水由，所以這里快速排序有很大的改進空間。那就是把元素劃分為三部分赛蔫，對應(yīng)小于砂客、等于、大于切分元素的部分呵恢。如下圖
如圖所示鞠值，這里分別維護三個指標(biāo)lt、i渗钉、gt彤恶。
如果a[i]小于v，則將a[lt]和a[i]進行交換鳄橘，并且將i和lt都遞增声离；如果a[i]大于v,將a[i]和a[gt]進行交換，并且將gt遞減挥唠；如果a[i]等于v抵恋，將i遞增焕议，然后繼續(xù)往后遍歷宝磨。
這樣一來就很好的解決了有大量相等元素時仍然進行切分并且重復(fù)遍歷的問題。
最后看下代碼
public class Quick3waySort {
private static void sort(Comparable[] a,int lo,int hi) {
int lt=lo,i=lo+1,gt=hi; // 定義三個指針
if (hi <= lo) return;
Comparable v = a[lo];
while (i <= gt) {
int temp = a[i].compareTo(v);
if (temp < 0) {
exch(a,lt++,i++);
} else if (temp > 0) {
exch(a,i,gt--);
} else {
i++;
}
}
sort(a,lo,lt-1);
sort(a,gt+1,hi);
}
private static void exch(Comparable[] a,int i,int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
最后盅安，寫這篇東西是復(fù)習(xí)一下唤锉。建議有興趣的朋友去讀下Robert Sedgewick和Kevin Wayne的《算法》。
