快速排序算法

• 快速排序
• 一、快速排序算法思想
• 二、例题
• • 1.题目描述
  • 2.代码实现
• 总结

（1）确定分界点：一般分界点有三个点可以来取用，左边界 q [ l ] q[l] q[l],右边界 q [ r ] q[r] q[r]，中间值 q [ l + r > > 1 ] q[l + r >> 1] q[l+r>>1];
（2）调整区间：通过 x x x 的值划分为左右两个区间，使得左边区间的的所有数都 ≤ leq ≤ x x x,第二个区间的所有数都 ≥ geq ≥ x x x；
（3）递归处理左右两段：左侧区间的最大值始终 < < < 右侧区间的最小值，递归结束后使得整个区间有序。

该算法中第二步为难点
实现第二步有两种做法：一是暴力做法；二是优美做法。
一、暴力做法：最简单的思路
将 q [ l ∼ r ] q[l sim r] q[l∼r] 中每个字符跟 x x x 比较，如果比 x x x 小则放入 a [ ] a[ ] a[] 中，否则放入 b [ ] b[ ] b[] 中，最后将 a [ ] a[ ] a[] 和 b [ ] b[ ] b[] 合并赋值给 q [ ] q[ ] q[]。
二、优美做法：采用双指针

int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while(q[i] < x);//如果比x的值小，指针则指向下一个数
        do j --; while(q[j] > x);//如果比x的值大，指针则指向前一个数
        if(i < j) swap(q[i], q[j]);//两个位置的数交换
    }

给定你一个长度为 n n n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n n n。
第二行包含 n n n 个整数（所有整数均在 1 ∼ 1 0 9 1∼10^9 1∼109 范围内），表示整个数列。

输出格式
输出共一行，包含 n n n 个整数，表示排好序的数列。

数据范围
1 1 1 ≤ leq ≤ n n n ≤ leq ≤ 100000 100000 100000
输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

代码如下：

#include 

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 >> 1], 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]);
    
    return 0;
}