912. 排序数组

Posted on | In
Words count in article: 357 | Reading time ≈ 1

题目

给定一个整数数组 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%