快排（分治思想）
约 805 字大约 3 分钟
快排（分治思想）
前言：二分
查找查找需要基于排序好的集合。排序算法是排序，查找是查找 勿混淆！https://www.acwing.com/solution/content/16777/
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想
class Solution {
public void moveZeroes(int[] nums) {
//二分
quickSort(nums,0,nums.length-1);
}
void quickSort(int[] arr, int l, int r){
if(l >= r) return;
int mid = arr[l+r >> 1];
int i = l-1, j = r+1;
while(i < j){
// 等效于do while
// 当数值小于分界值时持续遍历，直到找到第一个大于等于分界值的索引
// 如果是逆序则调整两个while循环
while(arr[++i] < mid);
while(arr[--j] > mid);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, l, j);
quickSort(arr,j+1, r);
return;
}
}- index 0 作为中间点
快速排序当我们把基准值设置在左边时，为什么要从右边先开始找？
当基准值位于左边时，我们希望先从右边开始查找。这是因为我们需要找到一个比基准值小的元素，以便将其放到基准值左边的子数组中。如果我们从左边开始查找，可能会导致在找到比基准值小的元素之前，错过了一些比基准值大的元素，从而破坏了划分的准确性（XD: 想象要确保基准点左边都是小的 右边是大于的）
也可以像下面这样，无所谓左边出发右边出发了应该！ 具体看acwing 实测while这里这么写不行：Time Limit Exceeded
void quickSort(int q[], int l, int r){
if (l >= r) return; //l >= r 看个人习惯都是可以的 l == r 也行
int i = l, j = r, x = q[l + r >> 1]; //这里取中间点，避免了下面while多层判断
while (i < j){
while (q[i] < x) i++;
while (q[j] > x) j--;
if (i < j) swap(q,i, j);
}
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
void swap(int[] nums, int i, int mid){
nums[i] ^= nums[mid];
nums[mid] ^= nums[i];
nums[i] ^= nums[mid];
}必须修改成下面这样，为什么？？？ 这里 i j 先走谁都行
int i=l-1,j=r+1, x = q[l + r >> 1]; //这里取中间点，避免了下面while多层判断
while (i < j){
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q,i, j);
}TODO 未完成，无法聚焦思路捋顺
代码一： int i = l, j = r, x = q[l + r >> 1]; //这里取中间点，避免了下面while多层判断 while (i < j){ while (q[i] < x) i++; while (q[j] > x) j--; if (i < j) swap(q,i, j); }
代码二： int i = l - 1, j = r + 1, x = q[l + r >> 1]; while(i < j) { do i++; while(q[i] < x); do j--; while(q[j] > x); if(i < j) swap(q[i], q[j]); }
他们的区别是什么，为什么代码一会超时 代码二不会。这代码是快速排序的部分代码
DP
问题建模（求解关键）
- 定义状态-读题问什么 [最长递增子序列] （长度）
- 状态转移 （if 怎么走，保证求解的过程形成一个逻辑上的有向无环图）