算法基础班 1.快速排序
基础算法：排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并
数据结构：链表与邻接表：树与图的存储、栈与队列：单调队列、单调栈、kmp、Trie、并查集、堆、Hash表
搜索与图论：DFS与BFS、树与图的遍历：拓扑排序、最短路、最小生成树、二分图：染色法、匈牙利算法
数学知识：质数、约数、欧拉函数、快速幂、扩展欧几里得算法、中国剩余定理、高斯消元、组合计数、容斥原理、简单博弈论
动态规划：背包问题、线性DP、区间DP、计数类DP、数位统计DP、状态压缩DP、树形DP、记忆化搜索
贪心
时空复杂度分析
LeetCode 27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 https://leetcode-cn.com/problems/remove-element
class Solution {public:int removeElement(vector<int>& nums, int val) {if(nums.size()==0){return nums.size();}int i=-1,j=0;while(j<nums.size()){i++;while(j<nums.size()&&nums[j]==val){j++;}if(j>=nums.size()){i--;break;}nums[i]=nums[j];j++;}return i+1;}};
// 时间复杂度：O(n)// 空间复杂度：O(1)class Solution {public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}};
给定你一个长度为 n 的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。 输入格式 : 输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。 输出格式 : 输出共一行，包含 n 个整数，表示排好序的数列。 数据范围 : 1≤n≤100000 https://www.acwing.com/problem/content/description/787/
快速排序的理论可以去看之前的推送，这里先放代码，来进行一个大家来找茬，看看代码错在哪。
//以下为错误代码#include <iostream>using namespace std;void quick_sort(int q[],int l,int r){if(l>=r){return;}int i=l-1,j=r+1,x=q[(l+r)>>1];while(i<j){while(q[++i]<x);while(q[--j]>x);if(i<j) swap(q[i],q[j]);}quick_sort(q,l,i-1);quick_sort(q,i,r);}int main(){int n;scanf("%d",&n);int q[n+1];for(int i=0;i<n;i++) scanf("%d",&q[i]);quick_sort(q,0,n-1);for(int i=0;i<n;i++) printf("%d",q[i]);return 0;}
明明模板也是这么写，边界条件也对称，怎么就一直不AC呢？找了很久原因，发现其实是，在这次代码中，我写的是
quick_sort(q,l,i-1);quick_sort(q,i,r);
而上面的pivot选取时，是用x=q[(l+r)>>1]
假如l为0，r为1（实际上在本代码中是-1和2），q[0]=2,q[1]=1，那么x=q[0]=2。
执行后，i为0，j为0，递归（0，-1）和（0, 1），实际上又会重新计算这个结果，进入死循环。
修正的方法很简单，让x=q[(l+r+1)>>1]即可，或者递归改成
quick_sort(q,l,j);quick_sort(q,j+1,r);
我只能说——