高效的分治排序
????快速排序是冒泡排序的改進(jìn)版葵硕，是目前已知的最快的排序方法问拘。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 該排序算法的基本思想是：
1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)凯沪。
2．分區(qū)過程鸠儿，將比這個(gè)數(shù)大的數(shù)全放到它的右邊献丑，小于或等于它的數(shù)全放到它的左邊涛贯。
3．再對(duì)左右區(qū)間重復(fù)第二步诽嘉，直到各區(qū)間只有一個(gè)數(shù)。
優(yōu)點(diǎn)：極快弟翘，數(shù)據(jù)移動(dòng)少含懊；
? ? ? ? 缺點(diǎn)：不穩(wěn)定。
算法實(shí)現(xiàn)
假設(shè)我們現(xiàn)在要對(duì){5,7,2,1,9,10,4,6,3,8}這個(gè)數(shù)組進(jìn)行快速排序衅胀，我們應(yīng)該怎么怎么做呢岔乔？
1.立Flag
? ? Flag就是我們之前提到的基準(zhǔn)數(shù)，為了將數(shù)據(jù)分區(qū)滚躯，立Flag是第一步也是最關(guān)鍵的一步雏门。在這里我們將數(shù)組的第一個(gè)數(shù)設(shè)為基準(zhǔn)數(shù)嘿歌。
2.探測(cè)
? ? 對(duì)于{5,7,6,1,9,10,4,2,3,8}這個(gè)數(shù)組，第一次排序我們的Flag是5茁影，我們分別從數(shù)組的左右兩端開始“探測(cè)”宙帝。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
我們定義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ù)探測(cè)或颊、交換，探測(cè)传于、交換......
4.Flag落位
第二次交換結(jié)束后數(shù)組變?yōu)閧5,3,2,1,4,10,9,6,7,8}囱挑。
j指向9的位置，i指向4的位置沼溜，j繼續(xù)向左移動(dòng)平挑，直到i的位置才找到小于5的值。
此時(shí)i=j盛末，我們只需將Flag落在這個(gè)位置：將5和4的值交換。數(shù)組變?yōu)閧4,3,2,1,5,10,9,6,7,8}否淤。
至此悄但，5這個(gè)Flag完成了它的歷史使命，第一輪交換結(jié)束石抡。
數(shù)組被劃分為兩個(gè)區(qū)檐嚣，F(xiàn)lag左邊是小于Flag的{4,3,2,1}，F(xiàn)lag右邊是大于Flag的{10,9,6,7,8}啰扛。
5.遞歸
我們?cè)俜謩e對(duì)這兩個(gè)區(qū)進(jìn)行第二輪交換嚎京，交換結(jié)果是{1,3,2,4}和{8,9,6,7,10}
對(duì)于{1,3,2}和{8,9,6,7}重復(fù)進(jìn)行以上操作，直至得到不能拆解的單個(gè)數(shù)字隐解，排序完成鞍帝！
下面用圖展示整個(gè)排序過程：
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]);
????????}
????}
}
