//快速排序：
//基本思想：（分治）
//先從數(shù)組中取出一個數(shù)作為key值；
//將比這個數(shù)小的數(shù)全部放在它的左邊，
//大于或等于它的數(shù)全部放在它的右邊，
//對左右兩個小數(shù)組重復(fù)上述步驟，直到各個區(qū)間只有1個數(shù)
//輔助理解：(挖坑填數(shù))
//初始時：i=0;j=8;key=6
//由于已經(jīng)將a[0]中的數(shù)保存到key中，可以理解成在數(shù)組a[0]上挖了個坑，可以將其他數(shù)據(jù)填充到這里來。
//從j開始向前查找一個比key小的數(shù)，當(dāng)j=8,符合條件，a[0]=a[8];i++;
//將a[8]挖出再填上一個坑a[0]中。
//這樣一個坑a[0]就被搞定了，單有形成了一個新坑a[8]。
//再找個數(shù)字來天a[8]這個坑，
//這次從i開始向后找一個大于key的數(shù)，當(dāng)i=4,符合條件，a[8]=a[4];j--;將a[4]挖出填到上一個坑中。
//此時i=4;j=8;key=6;
//再重復(fù)上面的步驟，先從后向前找，再從前向后找
//從j開始向前找，當(dāng)j=5時符合條件，將a[5]挖出填到上一個坑中，a[3]=a[5];i++;
//從i開始向后查找，當(dāng)i=5時，由于i==j退出，此時i=j=5,而a[5]剛好是上次挖的坑，將key填入a[5]
//最終可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它，然后再對a[0]到a[4]、a[6]到a[8]這兩個子區(qū)間重復(fù)上述步驟
//注意：key值的選取可以有多重形式，例如中間數(shù)或者隨機數(shù)，分別對算法的復(fù)雜度產(chǎn)生不同的影響。
//平均時間復(fù)雜度:O(nlogn)
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{6,2,4,1,9,3,6,7,0};
System.out.println("排序前=====");
print(arr);
System.out.println("");
System.out.println("排序后=====");
quickSort(arr,0,arr.length-1);
print(arr);
}
public static void quickSort(int[] arr,int left,int right){
if(left>=right)
return ;
int i = left;
int j = right;
int key = arr[left];//選擇第一個數(shù)作為key
while(i<j){
while(i<j && arr[j]>=key)//從右向左找
j--;
if(i<j){
arr[i] = arr[j];
i++;
}
while(i<j && arr[i]<key)//從左向右找
i++;
if(i<j){
arr[j] = arr[i];
j--;
}
}
//i=j
arr[i] = key;
quickSort(arr,left,i-1);//遞歸調(diào)用
quickSort(arr,i+1,right);//遞歸調(diào)用
}
public static void print(int[] arr){
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]+",");
}
}
}
