Sort an Array
|
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 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Solution { public int[] sortArray(int[] nums) { if (nums == null || nums.length <= 1) { return nums; } quickSort(nums, 0, nums.length - 1); return nums; } private void quickSort(int[] nums, int start, int end) { if (start >= end) { // no need to sort return; } // step 1: select a pivot Random rand = new Random(); int randPivot = rand.nextInt(end - start + 1); int pivotLocation = start + randPivot; int pivot = nums[pivotLocation]; // step 2: partition swap(nums, pivotLocation, end); int left = start; int right = end - 1; while (left <= right) { while (left <= right && nums[left] <= pivot) { left++; } while (left <= right && nums[right] >= pivot) { right--; } if (left < right) { swap(nums, left, right); } } swap(nums, left, end); quickSort(nums, start, left - 1); quickSort(nums, left + 1, end); return; } public void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } } |