acwing::acwing785_408 命名空间参考

1. 快速排序

更多...

函数
int	main (istream &cin, ostream &cout)
void	qs (vector< int > &vec, int l, int r)
	TEST (acwing785_408, case1)
	TEST (acwing785_408, case2)

详细描述

1. 快速排序

函数说明

main()

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

在文件 acwing408.cpp 第 1354 行定义.

                                              {
            int n;
            cin >> n;
            vector<int> vec(n);
            for(int i = 0; i < n; i++) {
                cin >> vec[i];
            }
            qs(vec, 0, n - 1);
            for(int i = 0; i < n; i++) {
                cout << vec[i] << ' ';
            }
            return 0;
        }

引用了 qs() , 以及 pat::a::a7_2::vec.

被这些函数引用 TEST().

qs()

void acwing::acwing785_408::qs	(	vector< int > &	vec,
		int	l,
		int	r
	)

在文件 acwing408.cpp 第 1335 行定义.

                                                {
            if(l >= r)
                return;
            int pivot = vec[(l + r) / 2];
            int lp    = l - 1;
            int rp    = r + 1;
            while(lp < rp) {
                while(vec[++lp] < pivot)
                    ;
                while(vec[--rp] > pivot)
                    ;
                if(lp < rp) {
                    swap(vec[lp], vec[rp]);
                }
            }
            qs(vec, l, rp);
            qs(vec, rp + 1, r);
        }

引用了 qs() , 以及 pat::a::a7_2::vec.

被这些函数引用 main() , 以及 qs().

TEST() [1/2]

acwing::acwing785_408::TEST	(	acwing785_408	,
		case1
	)

在文件 acwing408_test.cpp 第 1663 行定义.

                                   {
            istringstream in("5\n"
                             "3 1 2 4 5");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("1 2 3 4 5 ",
                      ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing785_408::TEST	(	acwing785_408	,
		case2
	)

在文件 acwing408_test.cpp 第 1673 行定义.

                                   {
            istringstream in("30\n"
                             "128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("6 8 11 60 67 67 83 90 98 116 128 133 133 153 160 160 164 175 181 196 216 232 233 238 241 248 260 291 294 295 ",
                      ans);
        }

引用了 main().