資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究基數排序的 C 程式
**排序演算法**是一種將列表中的元素按照特定順序排列的演算法。最常用的順序是數字順序和字典順序。
**基數**排序是一種非比較排序演算法。基數排序演算法是針對無序列表的首選演算法。
它首先透過對相同位值個位數字進行分組來對元素進行排序。基數排序的思想是按位進行排序， *從最低有效位(LSD)到最高有效位(MSD)*，並根據其升序/降序排列。基數排序是一種小方法，在對大型姓名列表進行字母排序時多次使用。具體來說，姓名列表首先根據每個姓名的第一個字母進行排序，即姓名被組織到 26 個類別中。
讓我們回顧一下下面的示例，以清楚地瞭解基數排序演算法的工作原理。顯然，傳遞/迭代次數取決於最高個位數的大小。
在上面的例子中，第一列是輸入。其餘列顯示在對越來越重要的數字位置進行連續排序後的列表。
基數排序的複雜度分析為 O(m.n)。
但是，如果我們看看這兩個值，與鍵的數量相比，鍵的大小相對較小。例如，如果我們有六位鍵，我們可能總共有 1,000,000 條不同的記錄。
在這裡，我們看到鍵的大小並不重要，並且此演算法具有線性複雜度 O(n)
演算法
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
示例
這是一個用於實現基數排序的 C 程式。
#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 ("
");
}
}
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 ("
");
return 0;
}輸出
Enter number of items to be sorted 6 Enter items:567 789 121 212 563 562 After pass 1 : 121 212 562 563 567 789 After pass 2 : 212 121 562 563 567 789 After pass 3 : 121 212 562 563 567 789 Sorted items : 121 212 562 563 567 789
更新於: 2019-12-24
13K+ 次檢視
廣告