使用递归。顺序设为从小到大。
完整代码见文章最后。
函数设置为
public static void QuickSort(int[] arr, int L, int R)
每次取一个值作为标准值(可取左边界的值)
同时需要有两个参数即当前处理分组的左右边界。设为L和R。
(第一次调用则为0和length-1)
int temp = arr[L];
int left = L;
int right = R;
已经取这个left位置的值，所以此时可以将arr[left]存的数据视为空。只是人为视为空。
从右向左遍历寻找 arr[right] < temp。如果此时right仍在left右侧，即大于left
即可将arr[left] = arr[right]。
while(arr[right] >= temp && right > left)
right--;
if (right > left)
arr[left] = arr[right];
此时可以将right存的值视为空，开始寻找arr[left] > temp。
当arr[left] > temp时，arr[right] = arr[left]
// 开始找左边即比temp大的值
while(arr[left] < temp && left < right)
left++;
// 同理需要先判定left是否仍小于right
if (left < right)
arr[right] = arr[left];
判断left和right是否重合，如果重合则将重合位置设为temp
if (left >= right)
arr[left] = temp;
重复上述操作直到left和right重合。
可将上述操作放入一个循环中。
while(true){
// 先比较right， 直到找到比temp小的数据
while(arr[right] > temp && right > left)
right--;
// 先判断right 是否仍大于 left，如果true则表示已经找到比temp小的数据
if (right > left)
arr[left] = arr[right];
// 开始找左边即比temp大的值
while(arr[left] < temp && left < right)
left++;
// 同理需要先判定left是否仍小于right
if (left < right)
arr[right] = arr[left];
// 这一步即left和right已重合
if (left == right)
arr[left] = temp;
break;
}
一次排序已经排完。
这时在left与right重合点左侧的值均小于 temp，右侧大于temp。
之后分别对左侧和右侧的数据再次按照上述排序。
直到传入的left在right右侧或重合(left>=right)，说明这次最多只有一个数据，已经完成排序
// left right 重合 左<temp 右>temp
// 再对左右执行上述过程
QuickSort(arr, L, left - 1);
QuickSort(arr, left + 1, R);
在本函数进行循环前加上判断是否只有一个数据
// 如果L已经大于等于R了则直接返回
if (L>=R)
return;
完整代码
public static void QuickSort(int[] arr, int L, int R){
// 如果L已经大于等于R了则直接返回
if (L>=R)
return;
// 从小到大。
int temp = arr[L];
int left = L;
int right = R;
while(true){
// 先比较right， 直到找到比temp小的数据
while(arr[right] >= temp && right > left)
right--;
// 先判断right 是否仍大于 left，如果true则表示已经找到比temp小的数据
if (right > left)
arr[left] = arr[right];
// 开始找左边即比temp大的值
while(arr[left] < temp && left < right)
left++;
// 同理需要先判定left是否仍小于right
if (left < right)
arr[right] = arr[left];
// 这一步即left和right已重合
if (left == right){
arr[left] = temp;
break;
}
}
// left right 重合 左<temp 右>temp
// 再对左右执行上述过程
QuickSort(arr, L, left - 1);
QuickSort(arr, left + 1, R);
}
