基本原理运行过程代码实现
基本原理1、找到一个基准值key，作为数组元素的比较对象，一般是取数组的第一个元素。
2、从后往前遍历，找到比基准值小的数字a和下标i。
3、从前往后遍历，找到比基准值大的数字b和下标j，调换a和b的位置。继续第2，第3步。
4、若只找到a没找到b，那么将基准值和a调换位置，以调换后的下标i为分割点，生成前后两部分新数组，两个数组继续执行第1步。
5、若没找到a，那么就以基准值之后的部分作为新数组，执行第1步。
6、新数组只包含一个元素或者没有元素时，结束排序。
运行过程基础数组为[10, 8, 5, 7, 1, 4, 3, 9, 2, 6]，执行第一步，找到基准值为下标为0的值key=10。
执行第二步，找到值a=6,下标i=9。
执行第三步，找不到比10大的值。
执行第四步，将key=10和a=6调换位置，结果为[6, 8, 5, 7, 1, 4, 3, 9, 2, 10]，将它以i=9分割之后得到两个新的数组[6, 8, 5, 7, 1, 4, 3, 9, 2]和[]，两个数组都执行第一步。
当空数组执行第一步时，直接来到第六步，该空数组结束排序。
然后继续执行。
调换前[6, 8, 5, 7, 1, 4, 3, 9, 2, 10]
执行2、3步，2和8进行调换
调换位置结果为[6, 2, 5, 7, 1, 4, 3, 9, 8, 10]
执行2、3步，3和7进行调换
调换位置结果为[6, 2, 5, 3, 1, 4, 7, 9, 8, 10]
执行2、4步，4和6进行调换
调换位置结果为[4, 2, 5, 3, 1, 6, 7, 9, 8, 10]
执行2、3步，1和5进行调换
调换位置结果为[4, 2, 1, 3, 5, 6, 7, 9, 8, 10]
执行2、4步，3和4进行调换
调换位置结果为[3, 2, 1, 4, 5, 6, 7, 9, 8, 10]
执行2、4步，1和3进行调换
调换位置结果为[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]
执行2、4步，8和9进行调换
调换位置结果为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
public static void main(String[] args) {
int[] array={10, 8, 5, 7, 1, 4, 3, 9, 2, 6};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int arr[],int left,int right){
//因为会遇到排序的那一部分只有一个数，即left=right,arr={x},直接返回
//或者该部分没有数,即left>right,arr={},直接返回。递归调用传参时，可能会出现这种情况。
if(left>=right){
return;
}
//left和right在循环过程中值会改变，所以用其余两个变量先记录，在递归时需要传递初始值
int leftIndex=left;
int rightIndex=right;
//总是取当前部分数组的第一个元素作为基准值
int key=arr[leftIndex];
//从后往前遍历
for(int i=right;i>=left;i--){
//找到比基准值小的数字arr[i]
if(arr[i]key){
//找到的话，就替换arr[i]和arr[j]的位置，同时将j赋给left
//表示下次继续寻找比基准值大的数字时，从下标j开始
left=j;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
System.out.println(Arrays.toString(arr));
//替换之后就应该跳出从前往后的这个循环，继续从后往前找比基准值小的，然后再来执行该循环
break;
}
//如果没找到，则表示当前数组部分后面有比基准值小的，前面却没有比基准值大的数字，无法调换位置
//例如{8, 5, 7, 1},那么此时就应该将arr[i]和基准值换位置
if(j==i){
arr[leftIndex]=arr[i];
arr[i]=key;
System.out.println(Arrays.toString(arr));
//调换过后，基准值到了下标为i的位置，以该位置为准，继续排它前面部分和后面部分
quickSort(arr,leftIndex,i-1);
quickSort(arr,i+1,rightIndex);
return;
}
}
}
//若找不到，则代表基准值在该部分数组中就是最小
if(i==left){
//因为基准值总是取部分数组的第一个值，所以这里只需要对基准值之后的继续排序
quickSort(arr,leftIndex+1,rightIndex);
}
}
return;
}
