分治-快速排序系列一＞快速排序
目录
- 题目方法：
- 优化方法：
- 代码：
题目方法：
忘记快速排序看这里：链接: link
优化方法：
代码：
public int[] sortArray(int[] nums) {
qsort(nums,0,nums.length-1);
return nums;
}
private void qsort(int[] nums, int L, int r){
if(L >= r) return;
int key = nums[new Random().nextInt(r-L+1)+L];//基准元素
int left = L-1,right = r+1,i = L;//注意这里的left和right会随递归改变，不能写死
while(i < right){
if(key > nums[i]) swap(nums, ++left, i++);
else if(key == nums[i]) i++;
else swap(nums, --right, i);
}
//[L,letf][letf+1,right-1][right,r]
qsort(nums,L,left);
qsort(nums,right,r);
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}