目录
前言
1 题目描述
2 分析
2.1 第一步
2.2 第二步
2.3 第三步
3 代码及结果分析
3.1 第3个版本
3.1.1 只有j--重复数据超时的代码
3.1.2 单纯i++的代码
代码
结果分析
3.1.2 改进后AC的代码
3.2 第2个版本的AC代码
3.3第1个版本的AC代码
前言
该内容纯属个人理解，虽然现在看来我自己也觉得有点多余，可能过段时间自己就忘了，但是总算也是搞明白一个思路，记录一下，欢迎大家批评指正
1 题目描述
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1e9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
2 分析
按照快排的分治思想，根据选定的中间值key，把整个数组分成两个区间，左边区间的所有数是小于等于key的，右边区间的所有数是大于等于key的，然后递归排序即可，因为我刚开始看快排模板不是很明白，模板里面的有些操作或者边界确实没自己实践，自己没什么头绪，所以自己分析了一下。
按照快排思路和自己的理解，下面是详细介绍
2.1 第一步
首先将把双指针i=low-1，j=high+1；换成i=low，j=high；因为按我理解一般就是直接从两端开始，没有放到外面，怕忘记，当然指针在两侧是为了后面的步骤服务，我自己后面也能看懂快排模板。
2.2 第二步
其次把do while或者while[a[i++]>key]；换成while(a[j>key])j--；因为在这里我自己的思路是觉得在这两个while是用来找大于和小于key的数的，就正常找到之后再+-的，当然这样可能很多余，这只是我自己的想法。
2.3 第三步
最后在if(i
3 代码及结果分析
3.1 第3个版本
在这里先给出第3个版本，是因为我详细分析了，第2个版本是让gpt修改了的，那时候是单纯写的i++，后面我想通了之后也看懂了初始版本，就是gpt修改了的。
3.1.1 只有j--重复数据超时的代码
这个代码其他测试用例都没问题，就是最后一个样例，当n=10000，所有数据都一样大时会超时
#include
#include
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn];
int m;
void Qsort(int a[],int low,int high) {
if(low>=high)return;
int i=low,j=high,key=a[(low+high)>>1];
// cout<<"low:"< for(int x=0;x cout< } // for(int x=low;x<=high;x++){ // cout< // } // cout<<"\n"; while(i while(a[j]>key)j--; while(a[i] if(i swap(a[i],a[j]); j--; // i++; // if(i+1 // if(i==j)i--; // if(i==j) } } // cout<<"key:"< // for(int x=0;x // cout< // if(x==j)cout<<"\n"; // } // cout<<"\n\n"; Qsort(a,low,j); Qsort(a,j+1,high); } /* 5 3 1 2 4 5 10 49 59 88 37 98 97 68 54 31 3 30 128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216 50 397 134 241 336 282 257 267 47 408 294 219 356 419 203 294 356 90 88 477 256 373 314 36 202 131 251 119 232 385 100 377 342 354 375 7 457 487 160 369 92 402 85 234 98 375 412 232 444 367 100 */ int main() { int i; cin>>m; for(i=0; i scanf("%d",&a[i]); } Qsort(a,0,m-1); for(i=0; i return 0; } 3.1.2 单纯i++的代码 代码 这个中间代码是为了解决，最后一个重复样例超时的问题，写的，但是结果会有问题 #include #include using namespace std; const int maxn = 1e6 + 10; int a[maxn]; int m; void Qsort(int a[],int low,int high) { if(low>=high)return; int i=low,j=high,key=a[(low+high)>>1]; // cout<<"low:"< for(int x=0;x cout< } // for(int x=low;x<=high;x++){ // cout< // } // cout<<"\n"; while(i while(a[j]>key)j--; while(a[i] if(i swap(a[i],a[j]); j--; i++; // if(i+1 // if(i==j)i--; // if(i==j) } } // cout<<"key:"< // for(int x=0;x // cout< // if(x==j)cout<<"\n"; // } // cout<<"\n\n"; Qsort(a,low,j); Qsort(a,j+1,high); } /* 5 3 1 2 4 5 10 49 59 88 37 98 97 68 54 31 3 30 128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216 50 397 134 241 336 282 257 267 47 408 294 219 356 419 203 294 356 90 88 477 256 373 314 36 202 131 251 119 232 385 100 377 342 354 375 7 457 487 160 369 92 402 85 234 98 375 412 232 444 367 100 */ int main() { int i; cin>>m; for(i=0; i scanf("%d",&a[i]); } Qsort(a,0,m-1); for(i=0; i return 0; } 单纯i++代码，样例和出现问题的输入，及结果 图1 样例输入 图2 出现错误的输入 结果分析 在上面的代码，只是单纯的i++的换，根据图1，中间输出low和high的数据是每次递归打印的结果，最后一行是结果图2一样，如果输入为5 3 1 2 4 5时，结果是没问题的，根据图2，当输入为5 3 6 2 4 5时，可以看到在第一轮时key为2，j=1，因为j左边的区间值应该都<=key，而打印出来的左边区间是2 6，是有问题的，根据手写分析，可以知道这时候i和j相遇了，但是没像输入为5 3 1 2 4 5时，a[j]=1刚好<=key，此时a[j]=6，出现问题的原因就是简单的i++之后出现了i和j相遇，而最外面的while条件是i 3.1.2 改进后AC的代码 #include #include using namespace std; const int maxn = 1e6 + 10; int a[maxn]; int m; void Qsort(int a[],int low,int high) { if(low>=high)return; int i=low,j=high,key=a[(low+high)>>1]; // cout<<"low:"< for(int x=0;x cout< } // for(int x=low;x<=high;x++){ // cout< // } // cout<<"\n"; while(i while(a[j]>key)j--; while(a[i] if(i swap(a[i],a[j]); j--; // i++; if(i+1 // if(i==j)i--; // if(i==j) } } // cout<<"key:"< // for(int x=0;x // cout< // if(x==j)cout<<"\n"; // } // cout<<"\n\n"; Qsort(a,low,j); Qsort(a,j+1,high); } /* 5 3 1 2 4 5 10 49 59 88 37 98 97 68 54 31 3 30 128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216 50 397 134 241 336 282 257 267 47 408 294 219 356 419 203 294 356 90 88 477 256 373 314 36 202 131 251 119 232 385 100 377 342 354 375 7 457 487 160 369 92 402 85 234 98 375 412 232 444 367 100 */ int main() { int i; cin>>m; for(i=0; i scanf("%d",&a[i]); } Qsort(a,0,m-1); for(i=0; i return 0; } 3.2 第2个版本的AC代码 这里我只给出代码，因为思路是和第3个版本差不多，就是需要保证两指针相遇时元素值的问题，需要注意的是在第3个版本，分界必须是j，如果是i的话需要改成，而第2版本只需要一个是j，一个是i就行了，并且只需要单纯的i++； #include #include using namespace std; const int maxn = 1e6 + 10; int a[maxn]; int m; void Qsort(int a[],int low,int high) { if(low>=high)return; int i=low,j=high,key=a[(low+high)>>1]; // cout<<"low:"< for(int x=0;x cout< } // for(int x=low;x<=high;x++){ // cout< // } // cout<<"\n"; while(i<=j) { while(a[j]>key)j--; while(a[i] if(i<=j) { swap(a[i],a[j]); j--; i++; } } // cout<<"key:"< // for(int x=0;x // cout< // if(x==j)cout<<"\n"; // } // cout<<"\n\n"; Qsort(a,low,j); Qsort(a,i,high); } /* 5 3 1 2 4 5 10 49 59 88 37 98 97 68 54 31 3 30 128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216 50 397 134 241 336 282 257 267 47 408 294 219 356 419 203 294 356 90 88 477 256 373 314 36 202 131 251 119 232 385 100 377 342 354 375 7 457 487 160 369 92 402 85 234 98 375 412 232 444 367 100 */ int main() { int i; cin>>m; for(i=0; i scanf("%d",&a[i]); } Qsort(a,0,m-1); for(i=0; i return 0; } 3.3第1个版本的AC代码 这个代码是根据我在学算法与数据的课程时，有个部分讲来快排，里面本来还有Partition函数的，但是被我整合到Qsort里面的，结合快排模板修改来的，本来我也是按照第二个版本那个思路来的，但是后面发现分割数组一直有问题，就是i和j指针移动的时机有问题，那时候我已经搞懂大致了，但是就是自己试了很多一直不知问题在哪，后面干脆结合了快排模板，每次先移动，并且加上i #include #include using namespace std; const int maxn = 1e6 + 10; int a[maxn]; int m; void Qsort(int a[],int low,int high) { if(low>=high)return; int i=low-1,j=high+1,key=a[(low+high)>>1]; // cout<<"low:"< for(int x=0;x cout< } // for(int x=low; x<=high; x++) { // cout< // } // cout<<"\n"; while(i while(i while(i if(i swap(a[i],a[j]); } } // cout<<"key:"< // for(int x=0; x // cout< // if(x==j)cout<<"\n"; // } // cout<<"\n\n"; Qsort(a,low,j); Qsort(a,j+1,high); } /* 10 49 59 88 37 98 97 68 54 31 3 5 3 1 2 4 5 30 128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216 */ int main() { int i; cin>>m; for(i=0; i scanf("%d",&a[i]); // cin>>a[i]; } Qsort(a,0,m-1); for(i=0; i return 0; } 相关链接
您阅读本篇文章共花了：
发表评论