class Solution {
public int[] sortArray(int[] nums) {
QuickSort(nums, 0, nums.length - 1);
return nums;
}
void QuickSort(int[] nums, int left, int right) {
if (left < right) {
//返回基准位置
int pos = position(nums, left, right);
QuickSort(nums, left, pos - 1);
QuickSort(nums, pos + 1, right);
}
}
int position(int[] nums, int left, int right) {
//在[left, right]之间随机选择一个下标作为基准
int p = new Random().nextInt(right - left + 1) + left;
//将基准暂时放到left位置上,便于后续遍历
swap(nums, left, p);
int i = left + 1;
int j = right;
while (true) {
while (i <= right && nums[i] < nums[left])
i++;
while (j > left && nums[j] > nums[left])
j--;
if (i > j)
break;
swap(nums, i, j);
i++;
j--;
}
swap(nums, left, j);
return j;
}
void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}