算法思想：分治
时间复杂度:O(nlogn)
第一步：在这段数上随便选取一个作为随机值（最好是中点）
第二步:用两个指针，一个从头开始，一个从尾开始，扫描这段数
只要小于这个随机值
i
i
i 就
+
1
+1
+1 ，直到某个数大于这个随机值
只要大于这个随机值
j
j
j 就
−
1
-1
−1 ，直到某个数小于这个随机值
接下来交换指针所指的两个数，继续做下去 直到
i
>
=
j
i >= j
i>=j
最后可以保证
j
j
j 左边的数都是小于等于随机值的，
i
i
i 右边的数都是大于等于随机值的
第三步：再分别对 [ l , j ] [l,j] [l,j] 和 [ j + 1 , r ] [j + 1,r] [j+1,r] 这两段进行排序
void qsort(int q[],int l,inr r)
{
if(l >= r) return;
int x = q[l + r >> 1],i,j;
i = l - 1,j = r + 1;
while(i < j)
{
while(q[++i] < x);
while(q[--j] > x);
if(i < j) swap(q[i],q[j]);
}
qsort(q,l,j);
qsort(q,j + 1,r);
}
