-
Notifications
You must be signed in to change notification settings - Fork 1
/
SortAnArray.java
68 lines (61 loc) · 1.65 KB
/
SortAnArray.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.hncboy;
/**
* @author hncboy
* @date 2020/3/31 22:13
* @description 912.排序数组
*
* 给你一个整数数组 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 <= 50000
* -50000 <= nums[i] <= 50000
*/
public class SortAnArray {
private int[] sortArray(int[] nums) {
sort(nums, 0, nums.length - 1);
return nums;
}
private static void sort(int[] nums, int left, int right) {
if (right <= left) {
return;
}
int p = partition(nums, left, right);
sort(nums, left, p - 1);
sort(nums, p + 1, right);
}
private static int partition(int[] nums, int left, int right) {
int i = left;
int j = right + 1;
// 选取 nums[left] 作为切分元素
int num = nums[left];
while (true) {
// 从数组左端开始扫描,找到第一个大于等于 num 的元素
while (nums[++i] < num && i != right) {
}
// 从数组右端开始扫描,找到第一个小于等于 num 的元素
while (nums[--j] > num && j != left) {
}
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, left, j);
return j;
}
private static void swap(int[] nums, int i, int j) {
if (i != j) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
}