如何在C中高效率地對多列數組進行排序？

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中文網其他相關文章！