基数排序是一种非比较排序算法。这种排序算法通过对共享相同位置和值的数字进行分组来对整数键起作用。基数是数字系统的基础。众所周知,在十进制系统中,基数或基数为10。因此,为了对十进制数字进行排序,我们需要10个位置框来存储数字。
时间复杂度:O(nk)
空间复杂度:O(n + k)
Input: The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output: Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932
radixSort(array, size, maxDigit)
输入-数据数组,数组中的总数,最大数的位数
输出- 排序数组。
Begin define 10 lists as pocket for i := 0 to max -1 do m = 10^i+1 p := 10^i for j := 0 to n-1 do temp := array[j] mod m index := temp / p pocket[index].append(array[j]) done count := 0 for j := 0 to radix do while pocket[j] is not empty array[count] := get first node of pocket[j] and delete it count := count +1 done done End
#include<iostream> #include<list> #include<cmath> using namespace std; void display(int *array, int size) { for(int i = 0; i<size; i++) cout << array[i] << " "; cout << endl; } void radixSort(int *arr, int n, int max) { int i, j, m, p = 1, index, temp, count = 0; list<int> pocket[10]; //radix of decimal number is 10 for(i = 0; i< max; i++) { m = pow(10, i+1); p = pow(10, i); for(j = 0; j<n; j++) { temp = arr[j]%m; index = temp/p; //find index for pocket array pocket[index].push_back(arr[j]); } count = 0; for(j = 0; j<10; j++) { //delete from linked lists and store to array while(!pocket[j].empty()) { arr[count] = *(pocket[j].begin()); pocket[j].erase(pocket[j].begin()); count++; } } } } int main() { int n, max; cout << "Enter the number of elements: "; cin >> n; cout << "Enter the maximum digit of elements: "; cin >> max; int arr[n]; //create an array with given number of elements cout << "Enter elements:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "Data before Sorting: "; display(arr, n); radixSort(arr, n, max); cout << "Data after Sorting: "; display(arr, n); }
输出结果
Enter the number of elements: 10 Enter the maximum digit of elements: 3 Enter elements: 802 630 20 745 52 300 612 932 78 187 Data before Sorting: 802 630 20 745 52 300 612 932 78 187 Data after Sorting: 20 52 78 187 300 612 630 745 802 932