Cara menggunakan algoritma isihan radix dalam C++

Cara menggunakan algoritma isihan radix dalam C++

Algoritma isihan radix ialah algoritma isihan bukan perbandingan yang melengkapkan isihan dengan membahagikan elemen untuk diisih kepada set digit yang terhad. Dalam C++, kita boleh menggunakan algoritma isihan radix untuk mengisih set integer. Di bawah ini kita akan membincangkan secara terperinci cara melaksanakan algoritma isihan radix, dengan contoh kod tertentu.

1. Idea Algoritma
   Idea algoritma pengisihan radix adalah untuk membahagikan elemen untuk diisih kepada set bit digital yang terhad, dan kemudian mengisih elemen pada setiap bit secara bergilir. Selepas pengisihan pada setiap bit selesai, elemen disusun semula mengikut susunan bit itu, dan kemudian pengisihan bit seterusnya diteruskan sehingga semua bit diisih.
2. Langkah pelaksanaan khusus
   (1) Mula-mula, kita perlu menentukan bilangan digit dalam nilai maksimum antara semua elemen untuk diisih. Ini akan menentukan berapa pusingan pengisihan yang perlu kita lakukan.

(2) Kemudian, kita perlu mencipta tatasusunan tambahan dan tatasusunan kiraan. Tatasusunan tambahan digunakan untuk menyimpan hasil sementara semasa proses pengisihan, dan tatasusunan pengiraan digunakan untuk merekodkan bilangan kejadian setiap nombor.

(3) Seterusnya, kita perlu melakukan beberapa pusingan pengisihan. Setiap pusingan pengisihan menyusun semula tatasusunan mengikut saiz bit semasa.

(4) Dalam setiap pusingan pengisihan, kita perlu melintasi tatasusunan untuk diisih, menggunakan nilai bit semasa setiap elemen sebagai indeks dan meletakkan elemen ke dalam baldi yang sepadan.

(5) Kemudian, kita perlu mengira bilangan elemen dalam setiap baldi, yang boleh direkodkan menggunakan tatasusunan mengira.

(6) Seterusnya, kita perlu menentukan kedudukan elemen dalam setiap baldi dalam tatasusunan tambahan dengan mengira tatasusunan. Ini boleh ditentukan dengan mengira jumlah awalan unsur dalam tatasusunan.

(7) Akhir sekali, kami menulis ganti elemen dalam tatasusunan tambahan ke dalam tatasusunan untuk diisih bagi melengkapkan pusingan pengisihan.

(8) Ulang langkah (3) hingga (7) sehingga semua bit diisih.

3. Contoh Kod
   Berikut ialah contoh kod yang menggunakan C++ untuk melaksanakan algoritma isihan radix:

#include <iostream>
#include <vector>

using namespace std;

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    int digit = 1;
    vector<int> temp(arr.size());
    while (maxVal / digit > 0) {
        vector<int> count(10, 0);

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

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

        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

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

        digit *= 10;
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    cout << "排序结果：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Dalam kod contoh di atas, kita mula-mula mencari nilai maksimum dalam tatasusunan untuk diisih bagi menentukan bilangan pusingan pengasingan diperlukan. Kemudian kami mencipta tatasusunan tambahan dan tatasusunan kiraan. Seterusnya, kami melakukan beberapa pusingan pengisihan untuk memasang semula tatasusunan mengikut saiz bit semasa. Akhirnya, kami mengeluarkan hasil yang disusun.

Ringkasan:
Dengan algoritma isihan radix, kita boleh mengisih set integer dalam C++. Idea teras algoritma pengisihan radix adalah untuk membahagikan elemen untuk diisih ke dalam set bit berangka yang terhad, dan kemudian mengisih elemen pada setiap bit secara bergilir-gilir. Algoritma pengisihan bukan perbandingan ini boleh menangani masalah pengisihan set integer dengan berkesan.

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