高效的分治排序
????快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 該排序算法的基本思想是：
1．先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。
2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。
優(yōu)點：極快，數(shù)據(jù)移動少；
? ? ? ? 缺點：不穩(wěn)定。
算法實現(xiàn)
假設(shè)我們現(xiàn)在要對{5,7,2,1,9,10,4,6,3,8}這個數(shù)組進行快速排序，我們應(yīng)該怎么怎么做呢？
1.立Flag
? ? Flag就是我們之前提到的基準(zhǔn)數(shù)，為了將數(shù)據(jù)分區(qū)，立Flag是第一步也是最關(guān)鍵的一步。在這里我們將數(shù)組的第一個數(shù)設(shè)為基準(zhǔn)數(shù)。
2.探測
? ? 對于{5,7,6,1,9,10,4,2,3,8}這個數(shù)組，第一次排序我們的Flag是5，我們分別從數(shù)組的左右兩端開始“探測”。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
我們定義i指向數(shù)組的最左端，定義j指向數(shù)組的最右端。首先將j向左移，直到j(luò)指向的數(shù)小于5；再將i向右移，直到i指向的數(shù)大于5。最終i指向7，j指向3。
3.交換
? ? 將3和7交換，數(shù)組變?yōu)閧5,3,2,1,9,10,4,6,7,8}。第一次交換結(jié)束。
接下來繼續(xù)探測、交換，探測、交換......
4.Flag落位
第二次交換結(jié)束后數(shù)組變?yōu)閧5,3,2,1,4,10,9,6,7,8}。
j指向9的位置，i指向4的位置，j繼續(xù)向左移動，直到i的位置才找到小于5的值。
此時i=j，我們只需將Flag落在這個位置：將5和4的值交換。數(shù)組變?yōu)閧4,3,2,1,5,10,9,6,7,8}。
至此，5這個Flag完成了它的歷史使命，第一輪交換結(jié)束。
數(shù)組被劃分為兩個區(qū)，F(xiàn)lag左邊是小于Flag的{4,3,2,1}，F(xiàn)lag右邊是大于Flag的{10,9,6,7,8}。
5.遞歸
我們再分別對這兩個區(qū)進行第二輪交換，交換結(jié)果是{1,3,2,4}和{8,9,6,7,10}
對于{1,3,2}和{8,9,6,7}重復(fù)進行以上操作，直至得到不能拆解的單個數(shù)字，排序完成！
下面用圖展示整個排序過程：
6.JAVA代碼
public class QuickSort {
? ? public static void quickSort(int[] arr,int low,int high){
? ? ? ? int i,j,temp,t;
? ? ? ? if(low>high){
? ? ? ? ? ? return;????
? ? ? ? }? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? i=low;
? ? ? ? j=high;
? ? ? ? //temp就是基準(zhǔn)位
? ? ? ? temp = arr[low];
? ??????while (i<j){
? ??????//先看右邊，依次往左遞減
? ?????????????????? while (temp<=arr[j]&&i<j){? ?????????
? ????????????? ? ? j--;
? ? ? ? }
? ??????//再看左邊，依次往右遞增
????????????????????while (temp>=arr[i]&&i<j){
? ? ????????????? ? i++;
? ? ? ? }
????????? ?????? //如果滿足條件則交換
? ? ? ? ? ? ? ? if (i<j){? ? ? ? ? ?????????
? ? ? ????????????? ?t=arr[j];
????????????????????arr[j]=arr[i];
? ????????????? ? ? arr[i]=t;
? ? ? ????????? }
????????}
//最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
????????arr[low] = arr[i];
? ? ? ? arr[i] = temp;
? ??????//遞歸調(diào)用左半數(shù)組
????????quickSort(arr, low, j-1);? ?
? ?????? //遞歸調(diào)用右半數(shù)組
????????quickSort(arr, j+1, high);
}
public static void main(String[] args){
????????int[] arr = {6,1,2,7,9,11,4,5,10,8};
????????quickSort(arr, 0, arr.length-1);
????????for (int i = 0; i < arr.length; i++) {
????????????????System.out.println(arr[i]);
????????}
????}
}
