题目给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
代码语言：javascript复制输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。示例 2：
代码语言：javascript复制输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。快排详解快速排序的基本思想快速排序先选择一个元素作为划分的依据，一般来说是随机选择这个区间里的某一个元素
假设当前这个数组，我们选择 4 作为标准，比4小的元素有3 1 2，比4大的有6875
切分切分过程展示
最后交换 6 和 5，完成切分。
如何实现切分？
此时你可能有疑问
最后一定要记得交换left和j，才能达到partition的效果
快速排序第一版代码代码语言：javascript复制class Solution {
public int[] sortArray(int[] nums) {
// 快排是递归进行的
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
// ==说明只有一个元素，那就没必要再排了
if (left >= right) {
return;
}
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
return;
}
public int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int j = left;
// nums[left + 1..j] <= pivot
// nums(j..i) > pivot
for (int i = left + 1; i <= right; i++) {
if (nums[i] <= pivot) {
j++;
swap(nums, j, i);
}
}
swap(nums, left, j);
return j;
}
public void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
}随机选择切分元素上面代码的问题：对于顺序数组或者逆序数组来说，递归树高度增加、递归树倾斜；
比如：
解决方案：破坏顺序性，随机选择 pivot。
代码语言：javascript复制class Solution {
// 使用当前时间的毫秒数作为随机数的种子
private static final Random random = new Random(System.currentTimeMillis());
public int[] sortArray(int[] nums) {
// 快排是递归进行的
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
// ==说明只有一个元素，那就没必要再排了
if (left >= right) {
return;
}
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
return;
}
public int partition(int[] nums, int left, int right) {
// 随机选择基准元素
int randomIndex = left + random.nextInt(right - left + 1);
swap(nums, left, randomIndex);
int pivot = nums[left];
int j = left;
// nums[left + 1..j] <= pivot
// nums(j..i) > pivot
for (int i = left + 1; i <= right; i++) {
if (nums[i] <= pivot) {
j++;
swap(nums, j, i);
}
}
swap(nums, left, j);
return j;
}
public void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
}双路快排上面代码的问题如下：
解决方案：
双路快排避免了递归树倾斜，递归树相对平衡；
双路快排
代码语言：javascript复制class Solution {
// 使用当前时间的毫秒数作为随机数的种子
private static final Random random = new Random(System.currentTimeMillis());
public int[] sortArray(int[] nums) {
// 快排是递归进行的
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
// ==说明只有一个元素，那就没必要再排了
if (left >= right) {
return;
}
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
return;
}
public int partition(int[] nums, int left, int right) {
int randomIndex = left + random.nextInt(right - left + 1);
swap(nums, left, randomIndex);
int pivot = nums[left];
int le = left + 1;
int ge = right;
// nums[left + 1..le] <= pivot
// nums[ge..right] >= pivot
while (true) {
while (le <= ge && nums[le] < pivot) {
le++;
}
while (le <= ge && nums[ge] > pivot) {
ge--;
}
if (le >= ge) {
break;
}
// 我们要达到的效果就是让等于pivot的元素平均的划分到数组的两边
swap(nums, le, ge);
le++;
ge--;
}
swap(nums, left, ge);
return ge;
}
public void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
}解释最后为什么交换 left 与 ge如果我的内容对你有帮助，请辛苦动动您的手指为我点赞，评论，收藏。感谢大家!!