快速排序采用“分而治之”的思想废累，把大的拆分為小的虑绵，小的再拆分為更小的。原理：
對于一組給定的記錄蚀之，通過一趟排序后蝗敢，將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小足删，然后再依次對前后兩部分的記錄進(jìn)行快速排序寿谴，遞歸該過程。
步驟：
- 分解失受。將輸入的序列array[m...n]劃分成兩個非空子序列array[m..k]和array[k+1...n]拭卿，使array[m...k]中任一元素的值不大于array[k+1...n]中任一元素的值。
- 遞歸求解贱纠。通過遞歸調(diào)用快速排序算法分別對array[m...k]和array[k+1...n]進(jìn)行排序峻厚。
- 合并。由于對分解出的兩個子序列的排序是就地進(jìn)行的谆焊，所以在array[m...k]和array[k+1...n]都排好序后不需要執(zhí)行任何計(jì)算array[m...n]就已排好序惠桃。
public static void sort(int []a, int low, int high){
int i,j;
int index;
if(low >= high){
return;
}
i = low;
j = high;
index = a[i]; //數(shù)組的第一個作為中軸基準(zhǔn)數(shù)
while(i < j){
while(i < j && a[j] >= index){
j--;
}
if(i<j){
a[i++] = a[j]; //比中軸小的記錄移到低端
}
while(i < j && array[i] < index){
i++;
}
if(i < j){
a[j--] = a[i]; //比中軸大的記錄移到高端
}
}
a[i] = index;
sort(a,low,i-1);
sort(a,i+1,high);
}
