问题描述
LeetCode 912. 排序数组 (opens in a new tab)，难度中等。
给你一个整数数组 nums，请你将该数组升序排列。
示例 1
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
题解
快排
题解：常规的快排过不了所有实例，我选择了【优化基准值 —— 随机选择法】，还是过不了所有实例，后面可以试试三数取中法，即选择数组的首元素、尾元素和中间元素的中位数作为基准值。这种方法可以在一定程度上避免最坏情况的发生，尤其是对于部分有序的数组。
Solution.java
public class Solution {
public int partitionArray(int[] nums, int low, int high) {
if (low >= high) return -1;
int pivot = low, l = pivot + 1, r = high;
while (l <= r) {
if (nums[l] < nums[pivot]) ++l;
else if (nums[r] >= nums[pivot]) --r;
else swap(nums, l, r);
}
swap(nums, pivot, r);
return r;
}
public void quickSort(int[] nums, int low, int high) {
if (low >= high) return;
Random random = new Random();
swap(nums, low + random.nextInt(high - low + 1, low);
int pivot = partitionArray(nums, low, high);
quickSort(nums, low, pivot);
quickSort(nums, pivot + 1, high);
}
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
}堆排序
题解：由于上面实现的快排过不了所有实例，所以我选择了堆排序过了，借助优先队列实现（真正面试的时候还是要自己写堆排序哦
Solution.java
class Solution {
public int[] sortArray(int[] nums) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i : nums) {
pq.add(i);
}
for (int i = 0; i < nums.length; ++i) {
nums[i] = pq.poll();
}
return nums;
}
}