public void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int key = nums[left];
int i = left;
int j = right;
while (i < j) {
while (nums[j] >= key && i < j) {
j--;
}
while (nums[i] <= key && i < j) {
i++;
}
//(如果左右指针还没有重合的话，即i!=j)此时，左指针指向的值一定是大于key的，右指针指向的值一定是小于key的，交换这两个值
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
//最初选左边第一个元素为key，然后是从右边开始遍历找小于key的值，所以
//左右指针重合位置的元素一定是小于基准值key的，将该元素与key交换，即完成一次排序，左边元素都小于key，右边元素都大于key
nums[left] = nums[i]; //相当于是完成最后一次交换，把基准值放到当前左右指针重合位置
nums[i] = key;
quickSort(nums, left, i-1); //递归左边部分
quickSort(nums, i+1, right); //递归右边部分
}
2、降序版
public void quickSort2(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int key = nums[left];
int i = left;
int j = right;
while (i < j) {
while (nums[j] <= key && i < j) {
j--;
}
while (nums[i] >= key && i < j) {
i++;
}
//(如果左右指针还没有重合的话，即i!=j)此时，左指针指向的值一定是小于于key的，右指针指向的值一定是大于key的，交换这两个值
if (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
//最初选左边第一个元素为key，然后是从右边开始遍历找大于key的值，所以
//左右指针重合位置的元素一定是大于基准值key的，将该元素与key交换，即完成一次排序，左边元素都大于key，右边元素都小于key
nums[left] = nums[i]; //相当于是完成最后一次交换，把基准值放到当前左右指针重合位置
nums[i] = key;
quickSort2(nums, left, i-1); //递归左边部分
quickSort2(nums, i+1, right); //递归右边部分
}
分析
注意！
这种写法是最后才把基准值交换到左右指针重合的位置，（如果选左边第一个元素为基准值，但从左边开始遍历，有可能出现最后左右指针重合位置元素大于基准值，但被交换到了左边）所以：
如果选左边第一个元素为基准值，则必须从右边开始遍历
选右边第一个元素为基准值，则必须从左边开始遍历还有一种写法是把基准值所在位置看成是空位置（会新建一个变量把基准值保存起来），如果选左边第一个元素为基准值，从右边开始选小于基准值的值放到左边空位置，（此时右边那个位置又成为新的空位置），然后从左边选大于基准值的值放到右边空位置。依次循环最后左右指针会在空位置重合，将基准值放入该空位置即完成一次排序。然后递归左半部分，递归右半部分，直到整体完成排序
试错举例（此处以升序版为例）：交换一下两个while语句（这里展示的是交换前的，测试时自行交换），最终排序结果有误
错误原因：选的是左边第一个元素为基准值，但从左边开始遍历，有可能出现最后左右指针重合位置元素大于基准值，但被交换到了左边
while (nums[j] >= key && i < j) {
j--;
}
while (nums[i] <= key && i < j) {
i++;
}
注意2：
升序和降序区别：
升序：将右边小于基准值key的值放到左边，将左边大于key的值放到右边
降序：反过来即可：将右边大于key的值放到左边，将左边小于key的值放到右边
对于升序和降序 递归左半部和递归右半部这里是一样的，核心在于第一次取基准值key后小于（或大于）key的值是在左半边还是在右半边
递归的次数是log(n) 每次递归while循环的次数是n,因此时间复杂度是n*log(n).另外快排是不稳定的排序算法.
