解法一:随机快排
随机快排。
class Solution {
private int[] arr;
public int[] sortArray(int[] nums) {
arr = nums.clone();
sort();
return arr;
}
public void sort() {
_sort(0, arr.length - 1);
}
private void _sort(int left, int right) {
if (left >= right) {
return;
}
int mid = partition(left, right);
_sort(left, mid - 1);
_sort(mid + 1, right);
}
private int partition(int left, int right) {
int index = new Random().nextInt(right - left + 1) + left;
int temp = arr[index];
arr[index] = arr[left];
arr[left] = temp;
int mid = arr[left];
while (left < right) {
while ((left < right) && (arr[right] >= mid)) {
--right;
}
arr[left] = arr[right];
while ((left < right) && (arr[left] <= mid)) {
++left;
}
arr[right] = arr[left];
}
arr[left] = mid;
return left;
}
}