Program C untuk jenis radix

Isih algoritma ialah algoritma yang menyusun komponen senarai dalam susunan tertentu. Pesanan yang paling biasa digunakan ialah susunan berangka dan susunan kamus.

radix Isih ialah algoritma pengisihan bukan perbandingan. Algoritma isihan radix ialah algoritma pilihan untuk senarai yang tidak diisih.

Ia mengisih elemen dengan mulanya mengumpulkan nombor individu dengan nilai tempat yang sama. Idea isihan radix adalah untuk mengisih sedikit demi sedikit daripada digit paling ketara (LSD) kepada digit paling ketara (MSD) dalam susunan meningkat/berkurang. Isih Radix ialah kaedah kecil yang digunakan berkali-kali apabila mengisih senarai nama yang sangat besar mengikut abjad. Secara khusus, senarai nama pada mulanya diisih mengikut huruf pertama setiap nama, iaitu, nama-nama itu disusun ke dalam dua puluh enam kategori.

Mari kita semak ilustrasi di bawah untuk mendapatkan pemahaman yang jelas tentang cara algoritma isihan radix berfungsi. Jelas sekali, bilangan pas/lelaran bergantung pada saiz nombor individu tertinggi.

Dalam contoh di atas, lajur utama dimasukkan. Lajur yang tinggal menunjukkan Senarai kedudukan berangka yang disusun mengikut urutan yang semakin penting.

Analisis kerumitan jenis radix O(m.n).

Namun, jika kita melihat kepada kedua-dua nilai ini, saiz kekunci adalah agak kecil berbanding bilangan kekunci. Sebagai contoh, jika kita mempunyai kunci enam digit, kita boleh mempunyai 1,000,000 rekod yang berbeza sama sekali.

Di sini kita cenderung untuk melihat bahawa saiz kekunci tidak penting dan algoritma adalah kualiti linear O(n) 🎜#Contoh

Ini ialah program C yang melaksanakan jenis radix.

Demonstrasi langsung

Radix_sort (list, n)
shift = 1
for loop = 1 to keysize do
   for entry = 1 to n do
   bucketnumber = (list[entry].key / shift) mod 10
   append (bucket[bucketnumber], list[entry])
list = combinebuckets()
shift = shift * 10

Output

#include<stdio.h>
int get_max (int a[], int n){
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   return max;
}
void radix_sort (int a[], int n){
   int bucket[10][10], bucket_cnt[10];
   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
   lar = get_max (a, n);
   while (lar > 0){
      NOP++;
      lar /= 10;
   }
   for (pass = 0; pass < NOP; pass++){
      for (i = 0; i < 10; i++){
         bucket_cnt[i] = 0;
      }
      for (i = 0; i < n; i++){
         r = (a[i] / divisor) % 10;
         bucket[r][bucket_cnt[r]] = a[i];
         bucket_cnt[r] += 1;
      }
      i = 0;
      for (k = 0; k < 10; k++){
         for (j = 0; j < bucket_cnt[k]; j++){
            a[i] = bucket[k][j];
            i++;
         }
      }
      divisor *= 10;
      printf ("After pass %d : ", pass + 1);
      for (i = 0; i < n; i++)
         printf ("%d ", a[i]);
      printf ("</p><p>");
   }
}
int main (){
   int i, n, a[10];
   printf ("Enter the number of items to be sorted: ");
   scanf ("%d", &n);
   printf ("Enter items: ");
   for (i = 0; i < n; i++){
      scanf ("%d", &a[i]);
   }
   radix_sort (a, n);
   printf ("Sorted items : ");
   for (i = 0; i < n; i++)
      printf ("%d ", a[i]);
   printf ("</p><p>");
   return 0;
}

Atas ialah kandungan terperinci Program C untuk jenis radix. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!