例题 排序数组

题目说明

给你一个整数数组 nums，请你将该数组升序排列。

  • 1 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

示例

例1

1
2
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

例2

1
2
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

笔者理解

此题是一道经典的排序问题。

解法

本次我们用经典八大排序算法中的选择排序来做这个题，选择排序的原理就是每次遍历一遍数组，挑选出相较最小的一个数，然后交换到前面去，前面已经排好序的元素不受后面的影响，所以实际上他需要比较的次数就是1+2+3+…+(n-1)，也就是*[n(n+1)]/2，但是他需要交换元素的次数最坏的情况为n-1**，所以选择排序适合元素交换代价较大的问题。

实现

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
public int[] sortArray(int[] nums) {
        int n = nums.length;
        if(n==1) { return nums; }
        //只有一个元素时，直接返回原数组

        int minId;
        //标记最小值的id

        int temp;
        //用来交换的中间值

        for(int i = 0; i < n; i++) {
            minId = i;
            //每次都将minId重置一下，因为i前面的元素代表已经排好序了

            for(int j = i; j < n; j++) {
                if(nums[j] < nums[minId]) {
                    minId = j;
                    //当前元素比最小值小，就将最小值认定为当前元素
                }
            }
            temp = nums[minId];
            nums[minId] = nums[i];
            nums[i] = temp;
            //交换两数
        }
        return nums;
    }

本题是一道经典排序题，感兴趣的朋友都可以去尝试一下，此题还有其他的解法，朋友们可以自己逐一尝试。