912. 排序数组

题目

给定一个整数数组 nums,将该数组升序排列。

示例1:

1
2
输入:[5,2,3,1]
输出:[1,2,3,5]

示例2:

1
2
输入:[5,2,3,1]
输出:[1,2,3,5]

示例3:

1
2
Input: nums = [1], index = [0]
Output: [1]

提示:

  • 1 <= A.length <= 10000
  • -50000 <= A[i] <= 50000

解法

解法一:

使用库函数

JAVA

1
2
3
4
public int[] sortArray(int[] nums) {
Arrays.sort(nums);
return nums;
}

解法二:

手写快排

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
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}

private int partition(int[] nums, int left, int right) {
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];

while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}

private void quickSort(int[] nums, int left, int right) {
if (left < right) {
int index = partition(nums, left, right);
quickSort(nums, left, index - 1);
quickSort(nums, index + 1, right);
}
}

解法三:

计数排序.

在LeetCode上提交之后发现比解法二中的快排还快了1ms。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] sortArray(int[] nums) {
countSort(nums);
return nums;
}

private void countSort(int[] nums) {
int[] count = new int[100001];
for (int num : nums) {
count[num + 50000]++;
}

int index = 0;
for (int i = 0;i < count.length;i++) {
if (0 != count[i]) {
int temp = count[i];
while (temp > 0) {
nums[index++] = i - 50000;
temp--;
}
}
}
}

排序方法有很多种,但在实际场景中,快排的效率是最好的,因此,本文就手写一个快排,其他的如堆排序,归并排序就不考虑了。

0%