归并排序
class Solution {
/**
归并排序, merge(left, mid, right)
*/
public int[] sortArray(int[] nums) {
return mergesort(nums, 0, nums.length - 1);
}
public int[] mergesort(int[] arr, int left, int right) {
if(left == right) {
return arr;
}
int mid = (left + right) / 2;
mergesort(arr, left, mid);
mergesort(arr, mid + 1, right);
merge(arr, left, mid, right);
return arr;
}
public void merge(int[] arr, int l, int m, int r) {
int[] left = Arrays.copyOfRange(arr, l, m + 1);
int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
int i = l;
int j = 0;
int k = 0;
while (j < left.length && k < right.length) {
if(left[j] <= right[k]) {
arr[i] = left[j];
j++;
}
else {
arr[i] = right[k];
k++;
}
i++;
}
while (j < left.length) {
arr[i] = left[j];
j++;
i++;
}
while (k < right.length) {
arr[i] = right[k];
k++;
i++;
}
}
}
堆排序
class Solution {
/**
堆排序
*/
public int[] sortArray(int[] nums) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num: nums) {
pq.offer(num);
}
int[] res = new int[nums.length];
int i = 0;
while (!pq.isEmpty()) {
res[i] = pq.poll();
i++;
}
return res;
}
}
快速排序
class Solution {
/**
快速排序
*/
public int[] sortArray(int[] nums) {
quicksort(nums, 0, nums.length - 1);
return nums;
}
public void quicksort(int[] nums, int left, int right) {
if (left < right) {
int mid = partition(nums, left, right);
quicksort(nums, left, mid - 1);
quicksort(nums, mid + 1, right);
}
}
public int partition(int[] nums, int left, int right) {
int tmp = left + (int) (Math.random() * (right - left + 1));
swap(nums, tmp, left);
int i = left;
int j = left + 1;
while (j <= right) {
if (nums[j] < nums[left]) {
swap(nums, j, ++i);
}
j++;
}
swap(nums, left, i);
return i;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}