Penjelasan terperinci tentang fungsi pengisihan dalam C++

Fungsi isih dalam C++ ialah fungsi berfungsi yang digunakan untuk mengisih elemen dalam tatasusunan atau bekas. Isih boleh dalam tertib menaik atau menurun, dan pelbagai jenis data seperti integer, titik terapung dan jenis aksara boleh diisih. Bahasa C++ menyediakan pelbagai fungsi pengisihan Artikel ini akan memperkenalkan penggunaan dan ciri-ciri fungsi pengisihan ini secara terperinci.

1. fungsi sort()

fungsi sort() ialah salah satu fungsi pengisihan yang paling biasa digunakan dalam C++ STL Fungsinya adalah untuk menyusun elemen dalam tatasusunan atau bekas. Penggunaan asas fungsi sort() adalah seperti berikut:

sort(begin, end);

di mana permulaan ialah alamat elemen pertama dalam tatasusunan atau bekas, penghujung ialah alamat elemen terakhir + 1, jadi hujung menunjuk ke alamat kosong selepas elemen terakhir. Fungsi sort() diisih dalam tertib menaik secara lalai Jika anda perlu mengisih dalam tertib menurun, anda boleh memasukkan penuding fungsi atau ungkapan lambda sebagai parameter ketiga.

Berikut ialah contoh kod yang menunjukkan cara menggunakan fungsi sort() untuk mengisih tatasusunan integer:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

1 2 3 4 5 6 7 8 9

2. stable_sort() fungsi

_

stable () function dan sort( ) fungsi adalah serupa, tetapi ia memastikan kedudukan relatif elemen dengan nilai yang sama kekal tidak berubah selepas mengisih. Penggunaan fungsi stable_sort() adalah serupa dengan fungsi sort() Anda juga boleh menghantar penunjuk fungsi atau ungkapan lambda sebagai parameter ketiga. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    stable_sort(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

1 2 3 4 5 6 7 8 9

3. partial_sort() function

partial_sort() fungsi boleh mengisih sebahagian elemen dalam tatasusunan atau bekas, iaitu, susun k unsur terkecil teratas dalam tatasusunan di hadapan (atau susun k unsur terbesar di hadapan tatasusunan). Penggunaannya adalah seperti berikut:

partial_sort(begin, middle, end);

di mana bermula ialah alamat elemen pertama dalam tatasusunan atau bekas, hujung ialah alamat elemen terakhir + 1, dan tengah ialah lelaran yang menunjuk ke elemen ke-k. Perlu diingatkan bahawa fungsi partial_sort() hanya menjamin bahawa elemen k pertama disusun, dan susunan elemen yang selebihnya tidak ditentukan. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    partial_sort(arr, arr + k, arr + n);

    for (int i = 0; i < k; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

1 2 3

4. nth_element() function

nth_element() fungsi digunakan untuk memilih elemen kth terkecil (atau kth terbesar) dalam tatasusunan atau bekas, dan Susunkannya pada kedudukan ke-k dalam tatasusunan. Penggunaannya adalah seperti berikut:

nth_element(begin, middle, end);

di mana bermula ialah alamat elemen pertama dalam tatasusunan atau bekas, hujung ialah alamat elemen terakhir + 1, dan tengah ialah lelaran yang menunjuk ke elemen ke-k. Perlu diingatkan bahawa fungsi nth_element() hanya menjamin bahawa elemen k pertama tatasusunan disusun, manakala elemen kth tidak diisih. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    nth_element(arr, arr + k - 1, arr + n);

    cout << "第 " << k << " 小的数是：" << arr[k - 1] << endl;

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

第 3 小的数是：3

5. make_heap() function

make_heap() function boleh menukar tatasusunan atau bekas menjadi timbunan, iaitu, elemen dalam tatasusunan mengikut peraturan timbunan binari Diisih untuk menyokong operasi timbunan. Penggunaannya adalah seperti berikut:

make_heap(begin, end);

di mana bermula ialah alamat elemen pertama dalam tatasusunan atau bekas, dan penghujungnya ialah alamat elemen terakhir + 1. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

9 7 8 6 4 3 5 1 2

6. push_heap() function

push_heap() fungsi boleh memasukkan elemen baru ke dalam timbunan dan melaraskan semula struktur timbunan untuk memenuhi sifat timbunan. Penggunaannya adalah seperti berikut:

push_heap(begin, end);

di mana bermula ialah alamat elemen pertama dalam tatasusunan atau bekas, dan penghujung ialah alamat elemen terakhir. Perlu diingatkan bahawa elemen baru yang dimasukkan harus diletakkan pada kedudukan terakhir timbunan. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    arr[n] = 0;

    push_heap(arr, arr + n + 1);

    for (int i = 0; i < n + 1; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

9 7 8 6 4 3 5 1 2 0

7. pop_heap() function

pop_heap() fungsi digunakan untuk meletuskan elemen atas timbunan dan melaraskan semula struktur timbunan untuk memenuhi sifat timbunan . Penggunaannya adalah seperti berikut:

pop_heap(begin, end);

di mana bermula ialah alamat elemen pertama dalam tatasusunan atau bekas, dan penghujung ialah alamat elemen terakhir. Perlu diingat bahawa selepas memunculkan elemen atas timbunan, saiz timbunan harus dikurangkan sebanyak 1. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    pop_heap(arr, arr + n);

    n--;

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

8 7 5 6 4 3 2 1

8. fungsi sort_heap()

fungsi sort_heap() digunakan untuk mengisih timbunan dan memastikan tatasusunan yang diisih berada dalam tertib menaik. Penggunaannya adalah seperti berikut:

sort_heap(begin, end);

di mana bermula ialah alamat elemen pertama dalam tatasusunan atau bekas, dan penghujung ialah alamat elemen terakhir. Perlu diingatkan bahawa fungsi sort_heap() akan terlebih dahulu memanggil fungsi pop_heap() untuk meletuskan elemen atas timbunan sebelum mengisih timbunan, jadi saiz tatasusunan yang diisih hendaklah dikurangkan sebanyak 1. Berikut ialah contoh kod:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    sort_heap(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Hasil menjalankan kod di atas adalah seperti berikut:

1 2 3 4 5 6 7 8 9

Ringkasan

Artikel ini memperkenalkan secara terperinci fungsi pengisihan biasa dalam C++, termasuk sort(), stable_sort(), partial_sort( ), nth_element(), make_heap (), push_heap(), pop_heap() dan fungsi sort_heap(). Setiap fungsi pengisihan ini mempunyai ciri tersendiri dan boleh memenuhi keperluan pengisihan yang berbeza. Dalam pengaturcaraan sebenar, adalah sangat penting untuk memilih fungsi pengisihan yang sesuai mengikut situasi tertentu.

Atas ialah kandungan terperinci Penjelasan terperinci tentang fungsi pengisihan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!