算法程序设计-快速排序

快速排序采用---分治策略

L |------x-------------| R

第一步确定分界点：q[l],q[(l+r)/2],q[r]随机

第二步调整范围：L |--------<=x|>=x------------| R

第三步递归处理左右两端

两种做法：

第一种：暴力解决

另外定义两个数组a[],b[]

判断q中的数组元素与x进行比较，小于x的放进a，大于x的放进b

最后将a，b放进数组q中，可以实现，左边的均小于x，右面的均大于x。

时间复杂度为o（n），可以考虑

优雅的做法：

在头部和尾部分别定义两个指针，两个指针同时往中间走，

左面的指针先走，当左面指针对应的数据小于x时，继续往后走，当左面指针对应的数据大于x时，i就停下来，则去移动j指针，同理当j大于x时，指针向左移动，当j小于x时，指针停止。

当两个指针都停止时，进行swap交换，那么交换完，继续按照以上步骤执行直到i和j相遇，那么左面的数据均小于x，右面的数据均大于x。

边界问题背算法

#include<iostream>
using namespace std;const int N=1e6+10;
int n;
int q[N];void quick_sort(int q[],int l,int r){if(l>=r)return;int x=q[(l+r) / 2],i=l-1,j=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]);}}quick_sort(q,l,j);quick_sort(q,j+1,r);}int main(){scanf("%d",&n);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]);}}

注意边界值要取中间值，边界值容易死循环