一、快速排序（递归）
// left right为数组第0个和最后一个索引
public int[] quicksort(int[] nums, int left, int right){
if(left > right) return nums;
int i = left ;
int j = right ;
int tmp = nums[left];
// 找到数组中小于tmp和大于tmp的下标索引
while(i != j){
// 先从右向左查找小于tmp的下标索引
while(i < j && nums[j] >= tmp) j--;
// 先从左向右查找大于tmp的下标索引
while(i < j && nums[i] <= tmp) i++;
if(i < j){
int tp = nums[i];
nums[i] = nums[j];
nums[j] = tp;
}
}
// 查找成功后,分治处理tmp左右两部分
nums[left] = nums[i];
nums[i] = tmp;
quicksort(nums, left, i - 1);
quicksort(nums, i + 1, right);
return nums;
}
思考：
- 为什么先从右向左（先从左向右怎样写）？
- 为什么nums[j] >= tmp和nums[i] <= tmp需要等号？
