给定一个整数数组
nums，将该数组升序排列。
示例 1：
输入：[5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= A.length <= 10000
-50000 <= A[i] <= 50000
用归并排序解决此题，时间复杂度为 nlogn
class Solution {
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] array, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
// 获取最中间的元素索引
int middleIndex = (startIndex + endIndex) / 2;
// 左半边排序
mergeSort(array, startIndex, middleIndex);
// 右半边排序
mergeSort(array, middleIndex + 1, endIndex);
// 合并左右排序结果
merge(array, startIndex, endIndex);
}
public void merge(int[] array, int startIndex, int endIndex) {
// 零时数组用来存放排好序的元素，因此归并排序的空间复杂度为 O（n）
int[] tmp = new int[endIndex - startIndex + 1];
int middleIndex = (startIndex + endIndex) / 2;
int i = startIndex;
int j = middleIndex + 1;
int k = 0;
while (i <= middleIndex && j <= endIndex) {
// 从此处可以看出归并排序为原地排序，不会打乱本来的顺序
if (array[i] <= array[j]) {
tmp[k++] = array[i++];
} else {
tmp[k++] = array[j++];
}
}
int start = i;
int end = middleIndex;
if (i > middleIndex) {
start = j;
end = endIndex;
}
while (start <= end) {
tmp[k++] = array[start++];
}
// 将零时数组中的元素转入原数组
for (int m = 0; m < tmp.length; m++, startIndex++) {
array[startIndex] = tmp[m];
}
}
}
归并排序图解
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于