题目
给你一个整数数组 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
基本概念
-
稳定性
如果待排序数组中两个相等的值，在排序后相对位置不对，我们就说这种排序算法是稳定的排序算法。反之，则不是一种稳定的排序算法。比如数组 [2(a), 2(b), 1]（为了方便解释，我给两个 2 加上标志，以便区分），在排序后，两个 2 的相对位置是否改变，即排序后的数组是 [1, 2(a), 2(b)]，还是 [1, 2(b), 2(a)]。
如果是稳定的排序算法，排序后得到的应是 [1, 2(a), 2(b)]。 -
原地排序
原地排序算法，即空间复杂度为 O(1) 的算法。
解法 1：冒泡排序
- 解题思路
冒泡排序是一种稳定的、原地排序算法，时间复杂度为 O(n^2)。它每次对相邻的两个数进行比较，如果不是有序的，则交换位置。如果一次 for 循环后，没有发生数据交换，则说明数组已经完全有序，可以提前退出 for 循环。
代码
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return nums;
}
for (int i = 0; i < nums.length; i++) {
// 提前退出循环标志位
boolean flag = false;
// 这里多一个-1是因为冒泡排序每次都是比较相邻的两个数，比如3个数实际只需要两次比较，因此-1
// 也可以简单理解为，比较的时候是nums[j]和nums[j+1]比较，如果不-1的话，会数组越界
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
// 交换位置
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = true;
}
}
// 如果没有数据交换，说明已经完全有序，提前退出循环
if (!flag) {
break;
}
}
return nums;
}
}
解法 2：选择排序
- 解题思路
选择排序是一种不稳定的、原地排序算法（比如数组 [2, 2, 1] 排序后，两个 2 的顺序发生改变），时间复杂度为 O(n^2)。它将数组中的数据分为已排序区间和未排序区间，每次都在未排序区间中选择一个最小值，放到已排序区间的后面（通过交换位置实现）。
代码
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return nums;
}
//记录最小值的索引
int min = 0;
//遍历 n-1 轮，最后一个数不用遍历比较
for (int i = 0; i < nums.length - 1; i++) {
min = i;
// 左边是排好序，只需要遍历初始最小值后的所有数
for (int j = i + 1; j < nums.length; j++) {
if (nums[min] > nums[j]) {
min = j;
}
}
if (min != i) {
int tmp = nums[min];
nums[min] = nums[i];
nums[i] = tmp;
}
}
return nums;
}
}
解法 3：插入排序
- 解题思路
插入排序是一种稳定的原地排序算法，时间复杂度为 O(n^2)。它将数组中的数据分为已排序区间和未排序区间，默认数组中的第一个数为已排序区间。每次从未排序区间中取数，在已排序区间中找到合适的位置插入，直到未排序区间为空。因为数组实现插入的代价较高，在具体实现中，用数据移动的方式实现插入。
代码
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return nums;
}
for (int i = 1; i < nums.length; i++) {
int tmp = nums[i];
int j = i - 1;
for (; j >= 0; j--) {
if (nums[j] > tmp) {
// 数据移动
nums[j + 1] = nums[j];
} else {
// 因为左边是已排序区间，因此如果nums[j]<=tmp，没必要继续比较，提前退出
break;
}
}
// 插入值
// for循环时，j多经历了一次j--，所以要+1
// 比如第一次循环时，j到这里，值为-1
nums[j + 1] = tmp;
}
return nums;
}
}
解法 4：归并排序
- 解题思路
归并排序是不是一种稳定的排序算法，具体要看 merge() 函数的实现，示例代码中的归并排序是一种稳定的、非原地排序算法，时间复杂度为 O(nlogn)。
归并排序利用的是分治思想，将一个大数组分成 2 个小数组，小数组排好序后再合并成一个大数组，以此递归，直至数组不能再划分成小数组。
代码
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return nums;
}
mergerSort(nums, 0, nums.length - 1);
return nums;
}
private void mergerSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
// 利用分治思想，将要排序的数组分解成两个小数组，分别排序
int mid = (start + end) / 2;
mergerSort(nums, start, mid);
mergerSort(nums, mid + 1, end);
// 合并排好序的小数组
merger(nums, start, end);
}
private void merger(int[] nums, int start, int end) {
int[] tmp = new int[end - start + 1];
int mid = (start + end) / 2;
int i = start;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) {
tmp[index++] = nums[i++];
} else {
tmp[index++] = nums[j++];
}
}
// 判断哪个数组还有剩余数据，将之放到临时数组中
int tmpStart = i;
int tmpEnd = mid;
if (j <= end) {
tmpStart = j;
tmpEnd = end;
}
while (tmpStart <= tmpEnd) {
tmp[index++] = nums[tmpStart++];
}
// 将临时数组中的内容放回nums数组中
if (end - start + 1 >= 0) {
System.arraycopy(tmp, 0, nums, start, end - start + 1);
}
}
}
解法 5：快速排序
- 解题思路
快速排序是一种不稳定的、原地排序算法，时间复杂度为 O(nlogn)。它与归并排序都是利用分治思想进行排序，但快速排序的实现思路和归并排序完全不同。
快速排序是在待排序数组中任意选择一个分区点（一般选择数组的第一个元素或最后一个元素），小于分区点的元素放到分区点左边，大于分区点的放到分区点右边，以此递归待排序数组不能再细分（start>=end）。
代码
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return nums;
}
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
// 获取分区点
int q = partition(nums, 0, end);
quickSort(nums, start, q - 1);
quickSort(nums, q + 1, end);
}
private int partition(int[] nums, int start, int end) {
// 默认拿数组最后一个值作为分区点
int pivot = nums[end];
int i = start;
for (int j = start; j < end; j++) {
if (nums[j] < pivot) {
if (i == j) {
i++;
} else {
// 交换i和j
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
}
}
}
if (i < end) {
int tmp = nums[i];
nums[i] = nums[end];
nums[end] = tmp;
}
return i;
}
}
网友评论