912. 排序数组
题目描述
给你一个整数数组 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 * 104
-5 * 104 <= nums[i] <= 5 * 104
方法一:快速排序
快速排序是一种高效的排序算法。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
时间复杂度
java
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
quikcSort(0, nums.length - 1);
return nums;
}
private void quikcSort(int l, int r) {
if (l >= r) {
return;
}
int x = nums[(l + r) >> 1];
int i = l - 1, j = r + 1;
while (i < j) {
while (nums[++i] < x) {
}
while (nums[--j] > x) {
}
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
quikcSort(l, j);
quikcSort(j + 1, r);
}
}
cpp
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
function<void(int, int)> quick_sort = [&](int l, int r) {
if (l >= r) {
return;
}
int i = l - 1, j = r + 1;
int x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x) {
}
while (nums[--j] > x) {
}
if (i < j) {
swap(nums[i], nums[j]);
}
}
quick_sort(l, j);
quick_sort(j + 1, r);
};
quick_sort(0, nums.size() - 1);
return nums;
}
};
ts
function sortArray(nums: number[]): number[] {
function quickSort(l: number, r: number) {
if (l >= r) {
return;
}
let i = l - 1;
let j = r + 1;
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
}
python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quick_sort(l, r):
if l >= r:
return
x = nums[randint(l, r)]
i, j, k = l - 1, r + 1, l
while k < j:
if nums[k] < x:
nums[i + 1], nums[k] = nums[k], nums[i + 1]
i, k = i + 1, k + 1
elif nums[k] > x:
j -= 1
nums[j], nums[k] = nums[k], nums[j]
else:
k = k + 1
quick_sort(l, i)
quick_sort(j, r)
quick_sort(0, len(nums) - 1)
return nums
方法二:堆排序
java
class Solution {
public int[] sortArray(int[] nums) {
heapSort(nums);
return nums;
}
private void heapSort(int[] nums) {
int n = nums.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(nums, 0, i);
heapify(nums, i, 0);
}
}
private void heapify(int[] nums, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && nums[left] > nums[largest]) {
largest = left;
}
if (right < n && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums, i, largest);
heapify(nums, n, largest);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
方法三:归并排序
归并排序是一种分治算法,其思想是将待排序的数据序列不断地折半拆分,直到每个数据块只有一个元素为止,然后再按照拆分的顺序将每个数据块两两合并,在合并的过程中进行排序,最终得到一个有序的数据序列。
归并排序是一种稳定的排序算法,时间复杂度为
java
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
mergeSort(0, nums.length - 1);
return nums;
}
private void mergeSort(int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
mergeSort(l, mid);
mergeSort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
int[] tmp = new int[r - l + 1];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l; i <= r; ++i) {
nums[i] = tmp[i - l];
}
}
}
cpp
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
function<void(int, int)> merge_sort = [&](int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
int tmp[r - l + 1];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l; i <= r; ++i) {
nums[i] = tmp[i - l];
}
};
merge_sort(0, nums.size() - 1);
return nums;
}
};
ts
function sortArray(nums: number[]): number[] {
function mergetSort(l: number, r: number) {
if (l >= r) {
return;
}
const mid = (l + r) >> 1;
mergetSort(l, mid);
mergetSort(mid + 1, r);
let [i, j, k] = [l, mid + 1, 0];
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (i = l, j = 0; i <= r; ++i, ++j) {
nums[i] = tmp[j];
}
}
const n = nums.length;
let tmp = new Array(n).fill(0);
mergetSort(0, n - 1);
return nums;
}
python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge_sort(l, r):
if l >= r:
return
mid = (l + r) >> 1
merge_sort(l, mid)
merge_sort(mid + 1, r)
i, j = l, mid + 1
tmp = []
while i <= mid and j <= r:
if nums[i] <= nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
if i <= mid:
tmp.extend(nums[i : mid + 1])
if j <= r:
tmp.extend(nums[j : r + 1])
for i in range(l, r + 1):
nums[i] = tmp[i - l]
merge_sort(0, len(nums) - 1)
return nums