快速排序:
不稳定
时间复杂度 o(n*logn)
空间复杂度: o(logn)
public class quickSort {
public static void quickSort(int[] nums, int l, int r) {
if (l >= r)
return;
int i = l;
int j = r;
int privot = nums[i];
while (i < j) {
while (i < j && nums[j] >= privot) {
j--;
}
if (i < j)
nums[i++] = nums[j];
while (i < j && nums[i] <= privot) {
i++;
}
if (i < j)
nums[j--] = nums[i];
nums[i] = privot;
}
quickSort(nums, l, i - 1);
quickSort(nums, i + 1, r);
}
public static void main(String[] args) {
int[] nums = new int[]{2, 4, 1, 23, 12, 32, 1};
quickSort(nums, 0, nums.length - 1);
for (int i = 0; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
}
归并排序:
稳定
时间复杂度 o(n*logn)
空间复杂度: o(n)
class Solution {
int[] temp;
public int[] sortArray(int[] nums) {
temp = new int[nums.length];
sort(nums,0,nums.length-1);
return nums;
}
private void sort(int[] nums, int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
sort(nums, left, mid);
sort(nums, mid + 1, right);
merge(nums, left, right);
}
private void merge(int[] nums, int left, int right) {
int k = left;
int i = left;
int mid = left + (right - left) / 2;
int j = mid + 1;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
k = left;
while (left <= right){
nums[left++] = temp[k++];
}
}
}