Cara menggunakan algoritma pengisihan mengira dalam C++

Cara menggunakan algoritma isihan mengira dalam C++

Algoritma isihan mengira ialah algoritma isihan yang agak mudah dan cekap, sesuai untuk senario di mana urutan integer diisih. Idea asasnya ialah untuk menentukan berapa banyak elemen sebelum setiap elemen lebih kecil daripadanya, dengan itu menentukan kedudukannya dalam tatasusunan tertib.

Langkah-langkah algoritma isihan mengira adalah seperti berikut:

1. Cari nilai maksimum dalam tatasusunan untuk diisih bagi menentukan panjang tatasusunan pengiraan.
2. Buat tatasusunan kiraan dengan panjang nilai maksimum tambah satu dan mulakannya kepada 0.
3. Lintas tatasusunan untuk diisih, kira bilangan kejadian setiap elemen dan simpan keputusan statistik ke tatasusunan kiraan.
4. Ubah tatasusunan kiraan supaya nilai setiap kedudukan adalah sama dengan jumlah nilai kedudukan sebelumnya.
5. Buat tatasusunan sementara dengan panjang yang sama dengan tatasusunan yang hendak diisih untuk menyimpan hasil pengisihan.
6. Lintas tatasusunan untuk diisih dari belakang ke hadapan, tentukan kedudukan setiap elemen dalam hasil yang diisih berdasarkan tatasusunan kiraan dan simpan elemen dalam tatasusunan sementara.
7. Salin hasil tatasusunan sementara kembali ke tatasusunan untuk diisih bagi melengkapkan pengisihan.

Berikut ialah contoh kod algoritma pengisihan mengira yang dilaksanakan dalam bahasa C++:

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = temp[i];
    }
}

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

    cout << "排序后的数组：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Dalam kod di atas, kami menggunakan tatasusunan pengiraan tambahan untuk mengira bilangan kejadian setiap elemen, dan kemudian mengira bilangan kejadian setiap elemen melalui ubah bentuk Kedudukan dalam keputusan yang disusun. Akhir sekali, kami menyalin hasil yang diisih kembali ke tatasusunan asal.

Melalui kod contoh di atas, kita boleh melihat proses pelaksanaan algoritma pengisihan mengira Kerumitan masanya ialah O(n+k), dengan n ialah panjang jujukan yang hendak diisih, dan k ialah jumlah bagi. nilai elemen maksimum dan nilai elemen minimum Perbezaannya adalah tambah satu.

Untuk meringkaskan, algoritma isihan mengira ialah algoritma isihan yang mudah tetapi cekap sesuai untuk senario di mana urutan integer diisih. Dengan menggunakan struktur data dan algoritma yang sesuai, kami boleh menyelesaikan tugas pengisihan dengan lebih baik.

Atas ialah kandungan terperinci Cara menggunakan algoritma pengisihan mengira dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!