HJ101.输入整型数组和排序标识,对其元素按照升序或降序进行排序

#include <iostream>
#include <vector>

int part(std::vector<int>& vec, int l, int r, int order) {
    int d = vec[l];
    while (l < r) {
        while (l < r && (order ? vec[r] <= d : vec[r] >= d)) {
            --r;
        }
        vec[l] = vec[r];
        while (l < r && (order ? vec[l] >= d : vec[l] <= d)) {
            ++l;
        }
        vec[r] = vec[l];
    }
    vec[l] = d;
    return l;
}

void q_sort(std::vector<int>& vec, int l, int r, int order = 0) {
    if (l < r) {
        int d = part(vec, l, r, order);
        q_sort(vec, l, d - 1, order);
        q_sort(vec, d + 1, r, order);
    }
}

int main() {
    int num = 0, order = 0, tmp = 0;
    std::vector<int> vec {};
    std::cin >> num;
    for (int i = 0; i < num; ++i) {
        std::cin >> tmp;
        vec.emplace_back(tmp);
    }
    std::cin >> order;
    int sz = (int)vec.size();
    q_sort(vec, 0, sz - 1, order);
    for (int i = 0; i < sz; ++i) {
        std::cout << vec[i] << (i == sz - 1 ? "" : " ");
    }
    return 0;
}

解题思路:

难点1:排序题,题目标为入门,,,可能指的是考察会不会用算法库吧,手撕快排应该怎么也不能叫入门级别。前两天背的快排又lu了一遍;

难点2:快排是不稳定的排序算法,比较的时候要记得用“<=”或者“>=”;

难点3:想用函数指针实现比较顺序的,后来作罢;

知识点:

知识点1:函数指针的声明

typedef bool (*pF)(int, int);

bool up(int a, int b) {
    return a <= b;
}

bool down(int a, int b) {
    return a >= b;
}

void q_sort(std::vector<int>& vec, int l, int r, pF cmp) {
    if (l < r) {
        int d = part(vec, l, r, cmp);
        q_sort(vec, l, d - 1, cmp);
        q_sort(vec, d + 1, r, cmp);
    }
}