编辑
作者简介：大家好我是小唐同学(๑><๑），为梦想而奋斗的小唐，让我们一起加油！！！
编辑
个人主页：小唐同学(๑><๑）的博客主页
系列专栏：数据结构
博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里
牛客网支持ACM模式哦，刷算法题也很推荐哦！！！
下面上文章------》
目录
快排思想：
快速排序的排序速度是非常快的，效率较高，再加上快速排序思想----分治法和递归也确实实用，
该方法的基本思想是：
1．先从数列中取出一个数作为基准数
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
相对于冒泡排序来说，快速排序是从两边进行判断。
上全代码：
# include <iostream> using namespace std; int a[100010]; void qsortt(int a[],int l,int r) { if(l>=r) { return ; } int pivot=a[l]; int left=l; int right=r; while(left<right) { while(left<right&&a[right]>=pivot) { right--; } if(left<right) //说明 a[right]<pivot 需要移位pivot左边 { a[left]=a[right]; //把最左值覆盖 因为有pivot可以暂存 } while(left<right&&a[left]<=pivot)//进行完右边进行左边 { left++; } if(left<right) //说明 a[left]>pivot 右调 { a[right]=a[left]; // 此时right的值已经调走 } if(left>=right) { a[left]=pivot; } //上边是进行初次排序 //下边是分治 左右 } qsortt(a,l,right-1);//最初位置到 pivot位置的前一个 qsortt(a,right+1,r); // 从pivot位置的下一个到最后 } int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; } qsortt(a,0,n-1); for(int i=0;i<n;i++) { cout<<a[i]<<" "; } }
第一部分：
int pivot=a[l]; int left=l; int right=r;
把基准数进行存储 左右结尾进行赋值
第二部分：
while(left<right) { while(left<right&&a[right]>=pivot) { right--; } if(left<right) //说明 a[right]<pivot 需要移位pivot左边 { a[left]=a[right]; //把最左值覆盖 因为有pivot可以暂存 } while(left<right&&a[left]<=pivot)//进行完右边进行左边 { left++; } if(left<right) //说明 a[left]>pivot 右调 { a[right]=a[left]; // 此时right的值已经调走 } if(left>=right) { a[left]=pivot; } //上边是进行初次排序 //下边是分治 左右 } qsortt(a,l,right-1);//最初位置到 pivot位置的前一个 qsortt(a,right+1,r); // 从pivot位置的下一个到最后 }
题解样例：
题目描述
利用快速排序算法将读入的 NN 个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用
STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）输入格式
第 11 行为一个正整数 NN，第 22 行包含 NN 个空格隔开的正整数 a_iai，为你需要进行排序的数，数据保证了 A_iAi 不超过 10^9109。
输出格式
将给定的 NN 个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
输入 #1复制
5
4 2 4 5 1
输出 #1复制
1 2 4 4 5
说明/提示
对于 20\%20% 的数据，有 N\leq 10^3N≤103；
对于 100\%100% 的数据，有 N\leq 10^5N≤105。
# include <iostream> using namespace std; int a[100010]; void qsort(int a[],int l,int r) { if(l>=r) { return ; } int pivot=a[l]; int left=l; int right=r; while(left<right) { while(left<right&&a[right]>=pivot) { right--; } if(left<right) //说明 a[right]<pivot 需要移位pivot左边 { a[left]=a[right]; //把最左值覆盖 因为有pivot可以暂存 } while(left<right&&a[left]<=pivot)//进行完右边进行左边 { left++; } if(left<right) //说明 a[left]>pivot 右调 { a[right]=a[left]; // 此时right的值已经调走 } if(left>=right) { a[left]=pivot; } //上边是进行初次排序 //下边是分治 左右 } qsort(a,l,right-1);//最初位置到 pivot位置的前一个 qsort(a,right+1,r); // 从pivot位置的下一个到最后 } int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) { cin>>a[i]; } qsort(a,0,n-1); for(int i=0;i<n;i++) { cout<<a[i]<<" "; } }
