双边循环法(指针交换法)
public static int[] quickSort(int[] array, int left, int right) {
//递归出口条件
if(left>right) return array;
int temLeft = left, temRight = right, pivot = array[left];
while (temLeft < temRight) {
//从右边开始寻比标准值小的
while (array[temRight] >= pivot && temLeft < temRight) {
temRight--;
}
//从左边开始寻找比标准值大的
while (array[temLeft] <= pivot && temLeft < temRight) {
temLeft++;
}
//交换
int tem = array[temLeft];
array[temLeft] = array[temRight];
array[temRight] = tem;
}
//归位基准值
int tem = array[temLeft];
array[temLeft] = array[left];
array[left] = tem;
//递归重复调用
quickSort(array, temLeft + 1, right);
quickSort(array, left, temRight - 1);
return array;
单边循环法(填坑法)
public static void quickSort2(int[] a, int left, int right) {
if (left >= right) return;
int pivot = a[left], mark = left;
for (int i = left+1; i <= right; i++) {
//寻找小于基准值的,与mark下一个交换
if (a[i] < pivot) {
mark++;
int tem = a[mark];
a[mark] = a[i];
a[i] = tem;
}
}
//将pivot和mark所在位置交换
a[left] = a[mark];
a[mark] = pivot;
quickSort2(a, mark+1, right);
quickSort2(a, left, mark-1);
}
此处评论已关闭