05 August 2008
Given an array of integers 1
nums
Example 1:
1
2
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:
1
2
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Constraints:
1
1 <= nums.length <= 50000
1
-50000 <= nums[i] <= 50000
Quick sort和Merge Sort
快排 模板
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
class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public int[] sortArray(int[] nums) {
// write your code here
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = partition(nums, start, end);
quickSort(nums, start, mid - 1);
quickSort(nums, mid + 1, end);
}
private int partition(int[] nums, int start, int end) {
int pivot = nums[start];
int i = start + 1;
int j = end;
while (i <= j) {
while (i <= j && nums[i] <= pivot) {
i++;
}
while (i <= j && nums[j] > pivot) {
j--;
}
if (i > j) {
break;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j--;
i++;
}
nums[start] = nums[j];
nums[j] = pivot;
return j;
}
}
归并 模板
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
class Solution {
public int[] sortArray(int[] nums) {
// use a shared temp array, the extra memory is O(n) at least
int[] temp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
}
private void mergeSort(int[] nums, int start, int end, int[] temp) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
mergeSort(nums, start, mid, temp);
mergeSort(nums, mid + 1, end, temp);
merge(nums, start, mid, end, temp);
}
private void merge(int[] nums, int start, int mid, int end, int[] temp) {
int left = start;
int right = mid + 1;
int index = start;
// merge two sorted subarrays in A to temp array
while (left <= mid && right <= end) {
if (nums[left] < nums[right]) {
temp[index++] = nums[left++];
} else {
temp[index++] = nums[right++];
}
}
while (left <= mid) {
temp[index++] = nums[left++];
}
while (right <= end) {
temp[index++] = nums[right++];
}
// copy temp back to A
for (index = start; index <= end; index++) {
nums[index] = temp[index];
}
}
}