原题
给定一个整数数组 nums，将该数组升序排列。
示例 1:
输入： [5,2,3,1] 输出： [1,2,3,5]
示例 2:
输入： [5,1,1,2,0,0] 输出： [0,0,1,1,2,5]
提示：
1 <= A.length <= 10000-50000 <= A[i] <= 50000
解法
思想
经典排序问题，解法见十大排序算法与Java实现
代码
计数排序：
class Solution {
public int[] sortArray(int[] nums) {
int[] occur = new int[100001];
for(int num:nums){
occur[num+50000]++;
}
int index = 0;
for(int i = 0;i<100001;i++){
if(occur[i]!=0){
for(int n = 0 ; n < occur[i];n++){
nums[index] = i-50000;
index++;
}
}
}
return nums;
}
}
快速排序，这里每次选取中轴元素都是选取的第一个元素：
class Solution {
public int[] sortArray(int[] nums) {
return quickSort(nums,0,nums.length-1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//获取中轴元素所处的位置
int mid = partition(arr, left, right);
//进行分割
arr = quickSort(arr, left, mid - 1);
arr = quickSort(arr, mid + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
//选取中轴元素
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
// 向右找到第一个小于等于 pivot 的元素位置
while (i <= j && arr[i] <= pivot) i++;
// 向左找到第一个大于等于 pivot 的元素位置
while(i <= j && arr[j] >= pivot ) j--;
if(i >= j)
break;
//交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
// 使中轴元素处于有序的位置
arr[j] = pivot;
return j;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode912-%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84/
