首页 > 后端开发 > C++ > 正文

如何在C中高效地对多列数组进行排序?

Mary-Kate Olsen
发布: 2024-11-04 15:54:02
原创
278 人浏览过

How to Sort Multi-Column Arrays in C   Efficiently?

C 语言中的多列数组排序

与 Java 的内置功能相比,C 语言中的多列数组排序是一个挑战。一种有效的方法是利用经典的 std::qsort 函数,该函数擅长对固定数组进行排序。

比较器实现

为了实现排序,我们将比较器定义为qsort 函数中的三元字符串表达式。该比较器通过顺序比较值来进行多列排序。下面是代码片段:

<code class="cpp">[](const void *arg1, const void *arg2) -> int
{
    int const *lhs = static_cast<int const *>(arg1);
    int const *rhs = static_cast<int const *>(arg2);
    return (lhs[0] < rhs[0]) ? -1
        : ((rhs[0] < lhs[0]) ? 1
        : (lhs[1] < rhs[1] ? -1
        : ((rhs[1] < lhs[1] ? 1 : 0))));
}
登录后复制

在三元表达式中,我们首先比较第一列值(lhs[0] 和 rhs[0])。如果它们相等,我们继续比较第二列值(lhs[1] 和 rhs[1])。结果为负数、零或正数,分别指示第一个数组是否应放置在第二个数组之前、相同位置或之后。

示例实现

考虑一个大小为 10x2 的二维数组 ar,其中填充了随机数据。我们可以使用 std::qsort 和自定义比较器按第一列值对数组进行排序:

<code class="cpp">int ar[10][2];

// Populate array with random data
...

// Sort the array using qsort
std::qsort(ar, 10, sizeof(*ar),
    [](const void *arg1, const void *arg2) -> int
    {
        int const *lhs = static_cast<int const *>(arg1);
        int const *rhs = static_cast<int const *>(arg2);
        return (lhs[0] < rhs[0]) ? -1
            : ((rhs[0] < lhs[0]) ? 1
            : (lhs[1] < rhs[1] ? -1
            : ((rhs[1] < lhs[1] ? 1 : 0))));
    });</code>
登录后复制

复杂度分析

最坏情况时间复杂度std::qsort 和自定义比较器的复杂度为 O(n log n),其中 n 是二维数组中的行数。然而,对于特定场景,例如当数组接近排序时,平均时间复杂度可以显着降低。

结论

通过利用 std::qsort 和自定义比较器,我们可以在 C 中有效地对多列二维数组进行排序。虽然不如 Java 的内置排序功能那么方便,但此方法为数据排序应用程序提供了强大且高性能的解决方案。

以上是如何在C中高效地对多列数组进行排序?的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!