快速排序 c++写法

解题思路:

取左右两边，i，j以及中间数x，分别对两边排序，如果遇到右边的比左边的大的则交换位置(这里是从小到大排序，从大到小可以反着写），直到排序结束。

  快排模板：

void quick_sort(int q[],int l,int r)

{

if(l>=r) return;

    int i=l-1;

    int j=r+1;

    int x=q[(l+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]);

    else break;

}

quick_sort(q,l,j),quick_sort(q,j+1,r);

 } 

注意事项:取N的时候要比要求开大一点，防止溢出

参考代码:

#include<iostream>

using namespace std;

const int N = 1e6+10;

int q[N];

int n;

void quick_sort(int q[],int l,int r)

{

if(l>=r) return;

    int i=l-1;

    int j=r+1;

    int x=q[(l+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]);

    else break;

}

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]);

return 0;

}