C++11标准模板（STL）- 算法 - 对一个范围内的拥有一定未指定类型的元素排序（qsort, qsort_s）

定义于头文件 <stdlib.h>

算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意范围定义为 [first, last) ，其中 last 指代要查询或修改的最后元素的后一个元素。

对一个范围内的拥有一定未指定类型的元素排序

qsort, 
qsort_s

1) 对 ptr 所指向的数组以升序排序。数组包含 count 个长度为 size 字节的元素。用 comp 所指向的函数比较对象。

2) 同 (1) ，除了传递给 comp 附加环境参数 context ，还会在运行时检测下列错误，并调用当前安装的制约处理函数：

• count 或 size 大于 RSIZE_MAX
• key 、 ptr 或 comp 是空指针（除非 count 为零）

同所有边界检查函数， qsort_s 仅若实现定义了 __STDC_LIB_EXT1__ ，且用户在包含 stdlib.h 前定义 __STDC_WANT_LIB_EXT1__ 为整数常量 1 才保证可用。

若 comp 指示两元素相等，则它们排序后的结果是未指定的。

参数

返回值

1) （无）

2) 成功时为零，若检测到运行时制约违规，则为非零

注意

与名称无关，C 和 POSIX 标准都未要求此函数用快速排序实现，也未保证任何复杂度或稳定性。

与其他边界检查函数不同， qsort_s 不将零大小数组视作运行时强制违规，而是不修改数组并成功返回（另一个接受零大小数组的函数是 bsearch_s ）。

在 qsort_s 之前，qsort 的用户通常用全局变量来将附加语境传递给比较函数。

调用示例

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
#include <time.h>

using namespace std;

struct Cell
{
    int x;
    int y;

    Cell &operator +=(const Cell &cell)
    {
        x += cell.x;
        y += cell.y;
        return *this;
    }

    bool operator <(const Cell &cell) const
    {
        if (x == cell.x)
        {
            return y < cell.y;
        }
        else
        {
            return x < cell.x;
        }
    }

    bool operator >(const Cell &cell) const
    {
        if (x == cell.x)
        {
            return y > cell.y;
        }
        else
        {
            return x > cell.x;
        }
    }
};

int compare_Cells_less(const void* a, const void* b)
{
    Cell arg1 = *(const Cell*)a;
    Cell arg2 = *(const Cell*)b;

    if (arg1 < arg2)
    {
        return -1;
    }
    if (arg1 > arg2)
    {
        return 1;
    }
    return 0;

    // return (arg1 > arg2) - (arg1 < arg2); // 可行的简写
    // return arg1 - arg2; // 错误的简写（若给出 INT_MIN 则会失败）
}

int compare_Cells_greater(const void* a, const void* b)
{
    Cell arg1 = *(const Cell*)a;
    Cell arg2 = *(const Cell*)b;

    if (arg1 < arg2)
    {
        return 1;
    }
    if (arg1 > arg2)
    {
        return -1;
    }
    return 0;
}

std::ostream &operator<<(std::ostream &os, const Cell &cell)
{
    os << "{" << cell.x << "," << cell.y << "}";
    return os;
}

int main()
{
    srand((unsigned)time(NULL));;

    std::cout.setf(std::ios_base::boolalpha);

    auto func1 = []()
    {
        int n = std::rand() % 10 + 100;
        Cell cell{n, n};
        return cell;
    };

    Cell cells[] = {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}};
    std::generate(std::begin(cells), std::end(cells), func1);
    std::cout << "cells :               ";
    std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;

    std::cout << "is_sorted:            " << std::is_sorted(std::begin(cells), std::end(cells));
    std::cout << std::endl << std::endl;

    qsort(cells, std::distance(std::begin(cells), std::end(cells)), sizeof(Cell), compare_Cells_less);
    std::cout << "cells :               ";
    std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;
    std::cout << "is_sorted:            " << std::is_sorted(std::begin(cells), std::end(cells));
    std::cout << std::endl << std::endl;

    auto is_sortf = [](const Cell & a, const Cell & b)
    {
        if (a.x == b.x)
        {
            return a.y > b.y;
        }
        return a.x > b.x;
    };

    std::generate(std::begin(cells), std::end(cells), func1);
    std::cout << "cells :               ";
    std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;

    std::cout << "is_sorted:            " << std::is_sorted(std::begin(cells), std::end(cells), is_sortf);
    std::cout << std::endl << std::endl;

    qsort(cells, std::distance(std::begin(cells), std::end(cells)), sizeof(Cell), compare_Cells_greater);
    std::cout << "cells :               ";
    std::copy(std::begin(cells), std::end(cells), std::ostream_iterator<Cell>(std::cout, " "));
    std::cout << std::endl;
    std::cout << "is_sorted:            " << std::is_sorted(std::begin(cells), std::end(cells), is_sortf);
    std::cout << std::endl << std::endl;

    return 0;
}

输出

cells :               {109,109} {106,106} {107,107} {106,106} {108,108}
is_sorted:            false

cells :               {106,106} {106,106} {107,107} {108,108} {109,109}
is_sorted:            true

cells :               {103,103} {105,105} {108,108} {109,109} {108,108}
is_sorted:            false

cells :               {109,109} {108,108} {108,108} {105,105} {103,103}
is_sorted:            true