给你一个整数数组 nums,请你将该数组升序排列。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例 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 <= 50000
-50000 <= nums[i] <= 50000
解决方案
快排。思路参见《啊哈!算法》第1章第3节:最常用的排序——快速排序。
class Solution {
private int[] array;
public int[] sortArray(int[] nums) {
array = nums;
quickSort(0, nums.length - 1);
return nums;
}
private void quickSort(int begin, int end) {
if (begin >= end) {
return ;
}
int middle = partition(begin, end);
quickSort(begin, middle - 1);
quickSort(middle + 1, end);
}
private int partition(int begin, int end) {
int pivot = array[begin];
int ptr1 = begin, ptr2 = end;
while (ptr1 < ptr2) {
while (ptr1 < ptr2 && array[ptr2] >= pivot) {
ptr2 -= 1;
}
while (ptr1 < ptr2 && array[ptr1] <= pivot) {
ptr1 += 1;
}
if (ptr1 < ptr2) {
int tmp = array[ptr1];
array[ptr1] = array[ptr2];
array[ptr2] = tmp;
}
}
array[begin] = array[ptr1];
array[ptr1] = pivot;
return ptr1;
}
}