

DS排序--快速排序

时间限制: 1 Sec 内存限制: 128 MB

题目描述

给出一个数据序列，使用快速排序算法进行从小到大的排序

--程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求

输入

第一行输入t，表示有t个测试示例

第二行输入n，表示第一个示例有n个数据

第三行输入n个数据，都是正整数，数据之间用空格隔开

以此类推

输出

每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。

样例输入

2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222

样例输出

55 22 6 111 333 444
6 22 55 111 333 444
6 22 55 111 333 444
6 22 55 111 333 444

1 33 77 555 444 77 666 2222
1 33 77 555 444 77 666 2222
1 33 77 77 444 555 666 2222
1 33 77 77 444 555 666 2222
1 33 77 77 444 555 666 2222

提示

解决方案

#include <iostream>
#include <vector>

void quickSort(std::vector<int> &vector, int begin, int end);
int partition(std::vector<int> &vector, int begin, int end);

int main() {
    int ctrl;
    std::cin >> ctrl;

    while (ctrl--) {
        int size;
        std::cin >> size;
        std::vector<int> vector(static_cast<size_t >(size));
        for (int i = 0; i < size; ++i) {
            std::cin >> vector[i];
        }
        quickSort(vector, 0, static_cast<int>(vector.size() - 1));
        std::cout << std::endl;
    }

    return 0;
}

void quickSort(std::vector<int> &vector, int begin, int end) {
    if (begin < end) {
        int pivot = partition(vector, begin, end);
        std::cout << vector.front();
        for (int i = 1; i < vector.size(); ++i) {
            std::cout << ' ' << vector[i];
        }
        std::cout << std::endl;
        quickSort(vector, begin, pivot - 1);
        quickSort(vector, pivot + 1, end);
    }
}
int partition(std::vector<int> &vector, int begin, int end) {
    int key = vector[begin];
    while (begin < end) {
        while (begin < end && vector[end] >= key) {
            end -= 1;
        }
        std::swap(vector[begin], vector[end]);
        while (begin < end && vector[begin] <= key) {
            begin += 1;
        }
        std::swap(vector[begin], vector[end]);
    }
    return begin;
}

评论