MENU

模板:快速排序算法

March 9, 2022 • 算法

快速排序算法,原理讲解参考:https://blog.csdn.net/qq_28584889/article/details/88136498

代码模板:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

const int N = 1e6 + 10;
const int M = 1e9 + 10;
const int INF = 0x3f3f3f3f;

int a[N];

void quickSort(int l, int r) {
    int mid = a[(l + r) >> 1];
    int i = l, j = r;
    while (i < j) {
        while (a[i] < mid) {
            i++;
        }

        while (a[j] > mid) {
            j--;
        }

        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (l < j) {
        quickSort(l, j);
    }

    if (i < r) {
        quickSort(i, r);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    quickSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}
作者:NorthCity1984
出处:https://grimoire.cn/algorithm/quick-sort.html
版权:本文《模板:快速排序算法》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任