acwing::acwing818类 参考

AcWing 818. 数组排序 更多...

#include <acwing.h>

静态 Public 成员函数
static int	main (istream &cin, ostream &cout)
static void	sort (int a[], int l, int r)

详细描述

AcWing 818. 数组排序

在文件 acwing.h 第 1492 行定义.

成员函数说明

main()

int acwing::acwing818::main ( istream &  cin, ostream &  cout  )

static

在文件 acwing.cpp 第 4742 行定义.

                                                   {
        int n;
        int l;
        int r;
        cin >> n >> l >> r;
        auto *a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, l, r);
        for(int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        delete[] a;
        return 0;
    }

被这些函数引用 acwing::TEST().

sort()

void acwing::acwing818::sort ( int  a[], int  l, int  r  )

static

在文件 acwing.cpp 第 4759 行定义.

                                             {
        if(l == r) {
            return;
        }
        if(l + 1 == r) {
            if(a[l] < a[r]) {
                return;
            }
            const int tmp = a[l];
            a[l]          = a[r];
            a[r]          = tmp;
        }
        const int m = a[(l + r) / 2];
        deque<int> dq;
        int cursor = l;
        dq.push_back(m);
        for(int i = l; i <= r; i++) {
            if(i != (l + r) / 2) {
                if(a[i] <= m) {
                    dq.push_front(a[i]);
                    cursor++;
                } else {
                    dq.push_back(a[i]);
                }
            }
        }
        for(int i = l; i <= r; i++) {
            a[i] = dq[i - l];
        }
        if(l <= cursor - 1) {
            sort(a, l, cursor - 1);
        }
        if(r >= cursor + 1) {
            sort(a, cursor + 1, r);
        }
    }

---

该类的文档由以下文件生成:

• acwing.h
• acwing.cpp