一翠储、核心思想
基本思想：從數(shù)組中選取一個(gè)元素f作為排序的參照物，除f之外的元素與f做比較洞难，如果元素大于f舆吮，則將元素放到f后面，如果元素小于f，則將元素放到f前面歪泳。
參照物為f的排序完成后萝勤，將f之前露筒、之后的元素作為新數(shù)組并按照上述基本思想進(jìn)行同樣的排序呐伞；
可以發(fā)現(xiàn)：每輪排序之后都可以確定一個(gè)元素的所屬位置
二、過程分析
int[] nums={7,5,3,9,6,8,4};
將第0個(gè)元素作為參照物f慎式，同時(shí)需要確定的是大于f元素與小于f的元素的邊界lt（即lt表示小于f的元素的最右邊的元素伶氢，lt的右邊即為大于f的元素）；
初始情況f=nums[0]=7瘪吏；lt=0
從i=1開始遍歷數(shù)組與參照物f作比較癣防，如果nums[i]<f則lt右移一位，如果i與lt不等掌眠，則交換i位置的元素與lt位置的元素（i與lt不相等是因?yàn)楸闅v過程中出現(xiàn)過大于f的元素蕾盯，而lt表示的是小于f的元素的最右邊的元素；將lt加一并交換lt與i位置的元素同樣是因?yàn)閘t表示的是小于f的元素的最右邊的元素）蓝丙；此過程遍歷完成后的結(jié)果為：lt及l(fā)t之前的元素是小于f的级遭，f之后的元素都是大于f的
以上遍歷完成之后對(duì)f之前的數(shù)組及f之后的數(shù)組做同樣的操作即可
三、代碼
@Test
public void test13(){
int[] nums={7,5,3,9,6,8,4};
quickSort(nums,0,nums.length-1);
}
// 交換元素位置
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
public void quickSort(int[] nums,int left,int right){
if (left>=right){
return;
}
int index=partition(nums,left,right);
quickSort(nums,left,index-1);
quickSort(nums,index+1,right);
}
public int partition(int[] nums,int left,int right){
int f=nums[left];
int lt=left;
for (int i=left+1;i<=right;i++){
if (nums[i]<f){
// 當(dāng)前元素小于f渺尘，則將lt右移挫鸽，保證lt是小于f的最右側(cè)的元素
lt++;
// i與lt不相等是因?yàn)楸闅v過程中出現(xiàn)過大于f的元素，lt經(jīng)過自增之后指向大于f的第一個(gè)元素
if (lt!=i){
// 交換lt與i位置的元素鸥跟，保證lt指向小于f的最右側(cè)元素
swap(nums,lt,i);
}
}
}
swap(nums,left,lt);
return lt;
}
