问题1:
问题二:
代码
//l:左值下标
//r:右值下标
//q:区分值
int[] partition(int[] arr, int l, int r, int p)
{
int less = l - 1; //<区的右边界 下标 初始值
int more = r + 1; //>区的左边界 下标 初始值
while (l < more) //l 当前数的下标
{
if (arr[l] < p) //1.<区分值
{
swap(arr, ++less, l++);
}
else if (arr[l] > p) //2.>区分值
{
swap(arr, --more, l);
}
else //3.==
{
l++;
}
}
return new int[] { less + 1, more - 1 };
}
//++a
返回值 a+1
自身值 +1
int a=4
int b=++a
//b=5 a=5
//a++
返回值 a
自身值 +1
int a=4
int b=a++;
//b=4,a=5
快排:
void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1); //<区
quickSort(arr, p[1] + 1, r); //>区
}
}
int[] partition(int[] arr, int l, int r) {
int less = l - 1; //<区边界
int more = r; //>区边界
while (l < more) { //l 当前值
if (arr[l] < arr[r]) //1.当前值 < 区分值
{
swap(arr, ++less, l++);
}
else if (arr[l] > arr[r]) //2.当前值 > 区分值
{
swap(arr, --more, l);
}
else //3.当前值 == 区分值
{
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}