快速排序

18:12:57　　2022-01-12

快排属于分治算法，分治算法都有三步：
1. 分成子问题
2. 递归处理子问题
3. 子问题合并

#include<iostream>
#include<algorithm>
#include<cmath>
#include<math.h>
using namespace std;
int a[1000010],n;
void qsort(int i, int j)
{
    int l = i, r = j, mid = a[(i + j) / 2];
    do {　　　　//分成子问题
        while (a[l] < mid)    l++;
        while (a[r] > mid)    r--;
        if (l <= r)
        {
            swap(a[l], a[r]);
            l++, r--;
        }
    } while (l <= r);
    if (l < j)    qsort(l, j);　　　//递归处理子问题
    if (i < r)    qsort(i, r);
　　//递归的终止
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    qsort(1, n);
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
        return 0;  
}

View Code