int i;
for(int i ;i<10;i++)
为啥这样写会报错啊
因为2个变量重名了,编译器不知道你写i代表哪一个。
参考GPT和自己的思路:在这段代码中,第一行已经定义了一个整型变量i,但是在for循环的括号中,又使用int关键字再次定义了一个同名的变量i,这属于重复定义。因此,会导致编译错误。解决办法是不要在for循环的括号中再次定义i,直接使用已经定义好的i即可。例如:int i; for(i=0; i<10; i++) 。
不要重复定义i,一般建议放在循环里面
快排属于分治算法
基本思想:当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。
总结下来即三步:
分成子问题
递归处理子问题
子问题合并
快排的具体实现
确定分界点x,这里取 x = q[l + r >> 1]。
划分区间:我们将一堆数分为两堆,左边分为<=x的,右边分为>=x。
递归处理左右两堆。
难点在于第2点,我们如何优雅而又简单的划分区间。这里我们可以使用双指针算法(不需要开辟额外空间)。
下面画图举例:
具体代码实现:
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];//这里 i = l - 1,j = r + 1,
//为什么要这样,是因为下面的 ++i,--j。
// >> 1 <=> /2
// << 1 <=> *2
//(运算效率:移位 > 赋值 > 大小比较 > 加法 > 减法 > 乘法 > 取模 > 除法。)
while(i<j){
while(q[++ i]<x);//当前值<x,指针就继续往右走,直到当前值>=x。
while(q[-- j]>x);//当前值>x,指针就继续往左走,直到当前值<=x。
//交换两个值 => 达到左边都是小于x的值,右边都是大于x的值。
//异或 ^ 骚操作(不使用额外变量)
if(i<j){
q[i] = q[i] ^ q[j];
q[j] = q[i] ^ q[j];
q[i] = q[i] ^ q[j];
}
}
//递归处理(l,j) (j + 1, r)。
//边界问题建议背过。
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
快速排序的额外空间复杂度:最好O(logN),最坏O(N),平均的额外空间复杂度,求一个概率累加:O(logN)
这里额外的空间主要指:递归的时候,我们要记录下每一次的分界点,这样递归完左边部分,才知道右边部分递归哪里。
最好:每次分界点都取到中间值
最坏:每次分界点都取到最大值或者最小值
快速排序的时间复杂度:最好O(N * logN),最坏O(N^2),平均时间复杂度,求一个概率累加:O(N * logN)
最好:每次分界点都取到中间值
最坏:每次分界点都取到最大值或者最小值