LeetCode_排序_中等_912.排序数组

1.题目

给你一个整数数组 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 <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-an-array

2.思路

（1）调用 API
直接调用 Java 中的 Arrays.sort() 方法即可。但本题的考察点显然不是 API 的调用，所以下面正好来复习一下那些经典的排序算法。

排序算法通常可以分成以下两大类：
① 比较类排序：通过比较来决定元素的相对次序，由于其平均时间复杂度不能低于 O(nlog₂n)，所以也称为非线性时间比较类排序。
② 非比较类排序：不通过比较来决定元素间的相对次序，可以以线性时间运行，因此也称为线性时间非比较类排序。

① 在基数排序的复杂度中，r 代表关键字的基数，d 代表关键字的长度，n 代表关键字的个数
② 在计数排序和桶排序的复杂度中，k 指的是待排序整数的范围。

（2）冒泡排序

（3）快速排序

（4）直接插入排序

（5）折半插入排序

（6）希尔排序

（7）简单/直接选择排序

（8）堆排序

（9）二路归并排序

（10）基数排序

（11）计数排序

（12）桶排序

3.代码实现（Java）

3.1.调用 API

//思路1————调用 API
class Solution {
    public int[] sortArray(int[] nums) {
        Arrays.sort(nums);
        return nums;
    }
}
1
2
3
4
5
6
7

3.2.冒泡排序

//思路2————冒泡排序
class Solution {
    public int[] bubbleSort(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = length - 1; j > i; j--) {
                if (nums[j] < nums[j - 1]) {
                	//交换 nums[j - 1] 和 nums[j]
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
                }
            }
        }
        return nums;
    }
}

//改进后的冒泡排序
class Solution {
    public int[] improvedBubbleSort(int[] nums) {
        int length = nums.length;
        boolean isExchange;
        for (int i = 0; i < length - 1; i++) {
            isExchange = false;
            for (int j = length - 1; j > i; j--) {
                if (nums[j] < nums[j - 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
                    //本趟发生了交换
                    isExchange = true;
                }
            }
            //如果本趟没有发生交换，则说明数组 nums 已经排好序，可直接返回 nums
            if (!isExchange) {
                return nums;
            }
        }
        return nums;
    }
}
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

3.3.快速排序

//思路3————快速排序
class Solution {
    Random random = new Random();
    
    public void quickSort(int[] nums, int left, int right) {
        int i;
        if (left < right) {
            i = randomPartition(nums, left, right);
            quickSort(nums, left, i - 1);
            quickSort(nums, i + 1, right);
        }
    }
    
    public int randomPartition(int[] nums, int left, int right) {
        int i = random.nextInt(right - left + 1) + left;
        int tmp = nums[i];
        nums[i] = nums[right];
        nums[right] = tmp;
        return partition(nums, left, right);
    }
    
    public int partition(int[] nums, int left, int right) {
        int i = left, j = right;
        //以 nums[left] 为基准
        int benchmark = nums[left];
        while (i < j) {
            //从右向左扫描，找到一个小于 benchmark 的元素 nums[j]
            while (i < j && nums[j] >= benchmark) {
                j--;
            }
            nums[i] = nums[j];
            //从左向右扫描，找到一个大于 benchmark 的元素 nums[i]
            while (i < j && nums[i] <= benchmark) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = benchmark;
        return i;
    }
}
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

3.4.直接插入排序

//思路4————直接插入排序
class Solution {
	public int[] insertSort(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            if (nums[i] < nums[i - 1]) {
                int tmp = nums[i];
                int j = i - 1;
                //查找 nums[i] 应该插入的位置
                do {
                    nums[j + 1] = nums[j];
                    j--;
                } while (j >= 0 && nums[j] > tmp);
                //在下标为 j + 1 的位置上插入 nums[i]
                nums[j + 1] = tmp;
            }
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.5.折半插入排序

//思路5————折半插入排序
class Solution {
    public int[] binaryInsertSort(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            if (nums[i] < nums[i - 1]) {
                int tmp = nums[i];
                int left = 0;
                int right = i - 1;
                //在 nums[left...right] 中查找 nums[i] 应该插入的位置
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (nums[mid] > tmp) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                //几种将元素进行后移
                for (int j = i - 1; j >= right + 1; j--) {
                    nums[j + 1] = nums[j];
                }
                //在下标为 right + 1 的位置上插入 nums[i]
                nums[right + 1] = tmp;
            }
        }
        return nums;
    }
}
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

3.6.希尔排序

//思路6————希尔排序
class Solution {
    public int[] shellSort(int[] nums) {
        int length = nums.length;
        int d = length / 2;
        while (d > 0) {
            //对相隔 d 个位置的一组数据使用直接插入排序
            for (int i = d; i < length; i++) {
                int tmp = nums[i];
                int j = i - d;
                while (j >= 0 && tmp < nums[j]) {
                    nums[j + d] = nums[j];
                    j -= d;
                }
                nums[j + d] = tmp;
            }
            //减小增量
            d /= 2;
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.7.简单/直接选择排序

//思路7————简单/直接选择排序
class Solution {
    public int[] selectSort(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {
            int k = i;
            for (int j = i + 1; j < length; j++) {
                if (nums[j] < nums[k]) {
                    k = j;
                }
            }
            if (k != i) {
                int tmp = nums[k];
                nums[k] = nums[i];
                nums[i] = tmp;
            }
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.8.堆排序

获取包含 n 个元素的大顶堆中的最小值，最多需要查找 n / 2 次。

//思路8————堆排序
class Solution {
    public int[] sortArray(int[] nums) {
        int length = nums.length - 1;
        //建立初始堆
        for (int i = length / 2; i >= 0; i--) {
            sift(nums, i, length);
        }
        for (int i = length; i >= 0; i--) {
            //将最后一个元素与根 nums[1] 交换
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            //对 nums[0...i - 1] 进行筛选，得到 i 个节点的堆
            sift(nums, 0, i - 1);
        }
        return nums;
    }
    
    public void sift(int[] nums, int left, int right) {
        // nums[j] 是 nums[i] 的左孩子
        int i = left;
        int j;
        if (i == 0) {
            j = 1;
        } else {
            j = 2 * i;
        }
        int tmp = nums[i];
        while (j <= right) {
            //如果右孩子更大，则将 j 指向右孩子
            if (j < right && nums[j] < nums[j + 1]) {
                j++;
            }
            //根节点小于最大孩子节点
            if (tmp < nums[j]) {
                nums[i] = nums[j];
                i = j;
                if (i == 0) {
                    j = 2;
                } else {
                    j = 2 * i;
                }
            } else {
                break;
            }
            nums[i] = tmp;
        }
    }
}
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

3.9.二路归并排序

//思路9————二路归并排序
class Solution {
    public int[] mergeSort(int[] nums) {
        int length = nums.length;
        for (int mergeLen = 1; mergeLen < length; mergeLen *= 2) {
            mergePass(nums, mergeLen);
        }
        return nums;
    }
    
    //对整个排序序列进行一趟归并
    public void mergePass(int[] nums, int mergeLen) {
        int length = nums.length;
        int i;
        //归并长度为 mergeLen 的两相邻子表
        for (i = 0; i + 2 * mergeLen - 1 < length; i = i + 2 * mergeLen) {
            merge(nums, i, i + mergeLen - 1, i + 2 * mergeLen - 1);
        }
        //余下两个子表，后者的长度小于 mergeLen
        if (i + mergeLen - 1 < length - 1) {
            merge(nums, i, i + mergeLen - 1, length - 1);
        }
    }
    
    //对 nums[left...mid] 和 nums[mid + 1...right] 中的元素进行归并
    public void merge(int[] nums, int left, int mid, int right) {
        int[] p = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                p[k++] = nums[i++];
            } else {
                p[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            p[k++] = nums[i++];
        }
        while (j <= right) {
            p[k++] = nums[j++];
        }
        //将 p 中的元素复制到 nums[left...right]
        for (k = 0, i = left; i <= right; k++, i++) {
            nums[i] = p[k];
        }
    }
}
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

3.10.基数排序

如果待排序的整数中存在负数和 0，那么基数排序则无法进行排序，下面代码的主要解决方法是：
① 将所有的数加一个正数，使得所有的数变为正数之后再进行基数排序；
② 排序完之后，通过将所有的数减去之前加的正数进行还原；

注意：待排序的整数中的最大值和最小值之差不能超过 Integer.MAX_VALUE，否则 ① 中的操作出现整数溢出的情况！此时可以将待排序的整数由 int 类型转换为 long 类型之后再进行基数排序，由于本题的整数取值范围为 [-5 * 10⁴, 5 * 10⁴]，所以不会出现上述情况。

//思路10————基数排序
class Solution {
	public int[] radixSort(int[] nums) {
        int length = nums.length;
        // flag 为 false 表示数组 nums 中不存在 0 或者负数
        boolean flag = false;
        int minNum = Integer.MAX_VALUE;
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            if (num <= 0) {
                flag = true;
            }
        }
        if (flag) {
            //将数组 nums 中的所有数都加上 1 - minNum
            for (int i = 0; i < length; i++) {
                nums[i] += 1 - minNum;
            }
        }

        //最低位优先法(Least Significant Digit first, LSD)

        // d 表示当前比较的位数，d = 1 表示比较个位，d = 2 表示比较十位，以此类推
        long d = 1;
        // maxD 表示数组 nums 中元素的最高位数
        int maxD = Arrays.stream(nums).max().getAsInt();
        //数组 buf 保存基数排序中一趟分配和收集后的整数
        int[] buf = new int[length];
        while (maxD >= d) {
            //目前 total[i] = j 表示当前位数下值为 i 的整数的个数为 j
            int[] total = new int[10];
            for (int i = 0; i < length; i++) {
                int digit = (nums[i] / (int) d) % 10;
                total[digit]++;
            }
            //目前 total[i] = j 表示当前位数下的值 ≤ i 的整数的个数为 j
            for (int i = 1; i < 10; i++) {
                total[i] += total[i - 1];
            }
            for (int i = length - 1; i >= 0; i--) {
                // digit 表示 nums[i] 的 d 位数上的值
                int digit = (nums[i] / (int) d) % 10;
                //将 nums[i] 存入数组 buf 中下标为为 total[digit] - 1 的位置
                buf[total[digit] - 1] = nums[i];
                total[digit]--;
            }
            //将数组 buf 拷贝到数组 nums 中
            System.arraycopy(buf, 0, nums, 0, length);
            d *= 10;
        }
        if (flag) {
            //将数组 nums 中的所有数都减去 minNum + 1
            for (int i = 0; i < length; i++) {
                nums[i] -= 1 - minNum;
            }
        }
        return nums;
    }
}
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

3.11.计数排序

计数排序的基本思想是对于给定的输入序列中的每一个元素 x，确定该序列中值小于 x 的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将 x 直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有 17 个元素的值小于 x 的值，则 x 可以直接存放在输出序列的第 18 个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。（来自百度百科）

//思路11————计数排序
class Solution {
    public static int[] countSort(int[] nums) {
        // maxNum 和 minMax 分别是数组 nums 中的最大值和最小值
        int maxNum = nums[0], minNum = nums[0];
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
            minNum = Math.min(minNum, num);
        }
        // k 是待排序的数的范围大小
        int k = maxNum - minNum + 1;
        //sortedNums 保存排序后的元素
        int[] sortedNums = new int[nums.length];
        // numRange[i] 待排序的整数中小于整数 i 的个数
        int[] numRange = new int[k];
        for (int num : nums) {
            numRange[num - minNum] += 1;
        }
        for (int i = 1; i < numRange.length; ++i) {
            numRange[i] = numRange[i] + numRange[i - 1];
        }
        for (int i = nums.length - 1; i >= 0; --i) {
            //按存取的方式取出 numRange 中的元素
            sortedNums[--numRange[nums[i] - minNum]] = nums[i];
        }
        return sortedNums;
    }
}
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

3.12.桶排序

桶排序可以看作是计数排序的升级版，其基本思想是：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。

//思路12————桶排序

1
2