一、核心思想
基本思想：从数组中选取一个元素f作为排序的参照物，除f之外的元素与f做比较，如果元素大于f，则将元素放到f后面，如果元素小于f，则将元素放到f前面。
参照物为f的排序完成后，将f之前、之后的元素作为新数组并按照上述基本思想进行同样的排序；
可以发现：每轮排序之后都可以确定一个元素的所属位置
二、过程分析
int[] nums={7,5,3,9,6,8,4};
将第0个元素作为参照物f，同时需要确定的是大于f元素与小于f的元素的边界lt（即lt表示小于f的元素的最右边的元素，lt的右边即为大于f的元素）；
初始情况f=nums[0]=7；lt=0
从i=1开始遍历数组与参照物f作比较，如果nums[i]<f则lt右移一位，如果i与lt不等，则交换i位置的元素与lt位置的元素（i与lt不相等是因为遍历过程中出现过大于f的元素，而lt表示的是小于f的元素的最右边的元素；将lt加一并交换lt与i位置的元素同样是因为lt表示的是小于f的元素的最右边的元素）；此过程遍历完成后的结果为：lt及lt之前的元素是小于f的，f之后的元素都是大于f的
以上遍历完成之后对f之前的数组及f之后的数组做同样的操作即可
三、代码
@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){
// 当前元素小于f，则将lt右移，保证lt是小于f的最右侧的元素
lt++;
// i与lt不相等是因为遍历过程中出现过大于f的元素，lt经过自增之后指向大于f的第一个元素
if (lt!=i){
// 交换lt与i位置的元素，保证lt指向小于f的最右侧元素
swap(nums,lt,i);
}
}
}
swap(nums,left,lt);
return lt;
}
