Bagaimana Mengisih Tatasusunan Berbilang Lajur dalam C dengan Cekap?

Isih Tatasusunan Berbilang Lajur dalam C

Isih tatasusunan berbilang lajur memberikan cabaran dalam C berbanding dengan keupayaan terbina dalam Java. Satu kaedah yang cekap melibatkan penggunaan fungsi std::qsort klasik, yang cemerlang dalam menyusun tatasusunan tetap.

Pelaksanaan Pembanding

Untuk mencapai pengisihan, kami mentakrifkan pembanding sebagai ungkapan rentetan ternary dalam fungsi qsort. Pembanding ini menjalankan isihan berbilang lajur dengan membandingkan nilai secara berurutan. Di bawah ialah coretan kod:

<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))));
}

Dalam ungkapan ternary, kami mula-mula membandingkan nilai lajur pertama (lhs[0] dan rhs[0]). Jika ia adalah sama, kami meneruskan untuk membandingkan nilai lajur kedua (lhs[1] dan rhs[1]). Hasilnya ialah negatif, sifar atau positif, menunjukkan sama ada tatasusunan pertama harus diletakkan sebelum, pada kedudukan yang sama, atau selepas tatasusunan kedua, masing-masing.

Contoh Pelaksanaan

Pertimbangkan tatasusunan 2D bersaiz 10x2, diisi dengan data rawak. Kita boleh menggunakan std::qsort dan pembanding tersuai untuk mengisih tatasusunan mengikut nilai lajur pertama:

<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>

Analisis Kerumitan

Kerumitan masa kes terburuk daripada std::qsort dan pembanding tersuai ialah O(n log n), dengan n ialah bilangan baris dalam tatasusunan 2D. Walau bagaimanapun, untuk senario tertentu, seperti apabila tatasusunan hampir diisih, purata kerumitan masa boleh menjadi lebih rendah dengan ketara.

Kesimpulan

Dengan menggunakan std::qsort dan pembanding tersuai, kita boleh menyusun tatasusunan 2D berbilang lajur dengan cekap dalam C . Walaupun tidak semudah keupayaan pengisihan terbina dalam Java, kaedah ini menyediakan penyelesaian yang mantap dan berprestasi untuk aplikasi pesanan data.

Atas ialah kandungan terperinci Bagaimana Mengisih Tatasusunan Berbilang Lajur dalam C dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!