1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
Random rand = new Random();
public int[] sortArray(int[] nums) {
int low = 0;
int high = nums.length - 1;
sort(nums, low, high);
return nums;
}
public void sort(int[] nums, int low, int high){
QuickSort(nums, low, high);
}
public void QuickSort(int[] nums, int low, int high){
if(low < high){
int pivot = Partition(nums, low, high);
QuickSort(nums, low, pivot - 1);
QuickSort(nums, pivot + 1, high);
}
}
public int Partition(int[] nums,int low, int high){
int index = rand.nextInt(high - low + 1);
int pivot = nums[index];
pivot = nums[low];
while(low < high){
while(low < high && nums[high] >= pivot) high--;
nums[low] = nums[high];
while(low < high && nums[low] <= pivot) low++;
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
}
|