主要思想：分治
关键步骤：
- 确定分界点：创建一个数组q,在数组中选一个基准数（通常为数组第一个）,x=q[left],q[(left+right)/2],q[right].
2.调整区间：把比基数(x)小的数放在左边，比基数大的数放在右边。
3.递归处理左右两段，不断递归直至排序完成。
例如：1. 6为基准数，设i，j为两哨兵，目前指向首尾两个数（加粗部分），6 1 2 7 9 3 4 5 10 8
2. 两哨兵分别走向对方，直到遇到交换条件，并做交换。
6 1 2 7 9 3 4 5 10 8
6 1 2 5 9 3 4 7 10 8
3. 此时来观察交换后的队列，除去基准数，是不是哨兵走过的位置都已部分有序了呢？ 左边1 2 5都比基准数小，右边7 10 8都比基准数大。
4. 然后继续执行，直至左右两边相遇。
6 1 2 5 9 3 4 7 10 8
6 1 2 5 4 3 9 7 10 8
6 1 2 5 4 3 9 7 10 8
3 1 2 5 4 6 9 7 10 8
5. 当i等于j时，交换两数,之后基准数两边不断递归就排序完成。
`
C++代码如下：
include
using namespace std;
//根据题目要求设置数组大小
const int N=1e5;
int p[N];
void quick_sort(int p[],int l,int r)
{
//设置基准数x,左边的哨兵i，右边的哨兵j；
int x=p[l],i=l-1,j=r+1;
//如果左边大于等于右边说明数只有一个或者没有；
if(l>=r) return;
while(i<j){
do i++;while(p[i]<x); //左边不断向右，跟基准数比较
do j--;while(p[j]>x); //右边边不断向左，跟基准数比较
if(i<j) swap(p[i],p[j]); //两数进行交换，这里用到了swap函数。也可以写成
//if(i<j)
//{ int temp =p[i];
// p[i]=p[j];
// p[j]=temp;
//}
}
//基数左，右两边的数不断递归，直至i等于j时停止递归；
quick_sort(p,l,j);
quick_sort(p,j+1,r);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&p[i]);
}
//将数传入quick_sort函数中；
quick_sort(p,0,n-1);
for(i=0;i<n;i++){
//排完序后打表输出；
printf("%d ",p[i]);
}
return 0;
}
`
另一种方法利用qsort
C代码如下：
`
include<stdio.h>
include<stdlib.h>
int cmp(const void* a, const void* b)
{
return (int)a - (int)b;
}
int main()
{
long int n, arr[100000], i;
scanf("%ld", &n);
for (i = 0; i < n; i++) {
scanf("%ld", &arr[i]);
}
qsort(arr, n, sizeof(arr[0]), cmp);
for (i = 0; i < n; i++) {
printf("%ld ", arr[i]);
}
}
`
本人蒟蒻，如有错误或者不当的地方还望指点，感谢观看我的博客