题目描述
给你一个整数数组 nums
,请你将该数组升序排列。
输入:nums = [5,2,3,1] 输出:[1,2,3,5]
求解思路
代码(快速排序)
class Solution {
public int[] sortArray(int[] nums) {
quicksort(nums,0,nums.length-1);
return nums;
}
void quicksort(int[] nums,int left,int right){
if(left<right){
int j = partion(nums,left,right);
quicksort(nums,left,j-1);
quicksort(nums,j+1,right);
}
}
int partion(int[] nums,int left,int right){
int i = left+1;
int q = right;
int flag = nums[left];
while(i<=q){
while(nums[i]<=flag&&i<right){
i++;
}
while(nums[q]>=flag&&q>left){
q--;
}
if(i<q){
int swap = nums[i];
nums[i] = nums[q];
nums[q] = swap;
i++;
q--;
}else{
break;
}
}
nums[left] = nums[q];
nums[q] = flag;
return q;
}
}