这个 基于比较的排序算法的下界 （合并排序、堆排序、快速排序等）是Ω（nLogn），即它们不能比nLogn做得更好。
null
计数排序 是一种线性时间排序算法，当元素在1到k范围内时，它按O（n+k）时间排序。
如果元素在 这个 范围从1到n 2. ? 我们不能使用计数排序，因为计数排序需要O（n） 2. )这比基于比较的排序算法更糟糕。我们能用线性时间对这样的数组进行排序吗？
基数排序 这就是答案。基数排序的思想是从最低有效位到最高有效位进行逐位排序。基数排序使用计数排序作为子例程进行排序。
基数排序算法
- 对每个数字i执行以下操作，其中i从最低有效位变化到最高有效位。
- 根据第i位使用计数排序（或任何稳定排序）对输入数组进行排序。
例子：
Original, unsorted list:170, 45, 75, 90, 802, 24, 2, 66Sorting by least significant digit (1s place) gives: [*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]170, 90, 802, 2, 24, 45, 75, 66Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]802, 2, 24, 45, 66, 170, 75, 90Sorting by the most significant digit (100s place) gives:2, 24, 45, 66, 75, 90, 170, 802
基数排序的运行时间是多少？ 让输入整数中有d个数字。基数排序需要O（d*（n+b））时间，其中b是表示数字的基数，例如，对于十进制系统，b是10。d的值是多少？如果k是最大可能值，那么d就是O（log B （k） ）。所以总的时间复杂度是O（（n+b）*log B （k） ）。这看起来比基于比较的排序算法的时间复杂度更大。让我们首先限制k。让k<=n C 其中c是常数。在这种情况下，复杂性变成O（nLog） B （n） ）。但它仍然无法击败基于比较的排序算法。 如果我们把b的值放大呢？。要使时间复杂度线性化，b的值应该是多少？如果我们把b设为n，我们得到的时间复杂度为O（n）。换句话说，我们可以对1到n范围内的整数数组进行排序 C 如果数字以n为基数（或每个数字都取对数 2. （n） 位）。
基数排序的应用：
- 在一台典型的计算机中，这是一台顺序随机存取机器，其中记录由多个字段键入，使用基数排序。例如，你想按三个键进行排序，即月、日和年。你可以比较一年中的两项记录，然后比较一个月中的一项，最后比较一个日期。或者，可以使用基数排序法对数据进行三次排序，先按日期排序，然后按月份排序，最后按年份排序。
- 它被用于有80列的卡片分拣机中，在每列中，机器只能在12个位置打孔。然后对分拣机进行编程，根据卡片穿孔的位置对卡片进行分拣。然后，操作员用它来收集打孔了第一行、第二行的卡片，依此类推。
与基于比较的排序算法（如快速排序）相比，基数排序更可取吗？ 如果我们有日志 2. 对于每个数字n位，对于大范围的输入数字，基数的运行时间似乎优于快速排序。对于基数排序，渐近符号中隐藏的常数因子更高，而快速排序更有效地使用硬件缓存。此外，基数排序使用计数排序作为子例程，计数排序占用额外的空间对数字进行排序。
基数排序的实现
下面是基数排序的一个简单实现。为简单起见，假设d的值为10。我们建议你去看看 计数排序 有关下面代码中countSort（）函数的详细信息。
C++
// C++ implementation of Radix Sort #include <iostream> using namespace std; // A utility function to get maximum value in arr[] int getMax( int arr[], int n) { int mx = arr[0]; for ( int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. void countSort( int arr[], int n, int exp ) { int output[n]; // output array int i, count[10] = { 0 }; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp ) % 10]++; // Change count[i] so that count[i] now contains actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp ) % 10] - 1] = arr[i]; count[(arr[i] / exp ) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort void radixsort( int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that instead // of passing digit number, exp is passed. exp is 10^i // where i is current digit number for ( int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp ); } // A utility function to print an array void print( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver Code int main() { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof (arr) / sizeof (arr[0]); // Function Call radixsort(arr, n); print(arr, n); return 0; } |
JAVA
// Radix sort Java implementation import java.io.*; import java.util.*; class Radix { // A utility function to get maximum value in arr[] static int getMax( int arr[], int n) { int mx = arr[ 0 ]; for ( int i = 1 ; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. static void countSort( int arr[], int n, int exp) { int output[] = new int [n]; // output array int i; int count[] = new int [ 10 ]; Arrays.fill(count, 0 ); // Store count of occurrences in count[] for (i = 0 ; i < n; i++) count[(arr[i] / exp) % 10 ]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1 ; i < 10 ; i++) count[i] += count[i - 1 ]; // Build the output array for (i = n - 1 ; i >= 0 ; i--) { output[count[(arr[i] / exp) % 10 ] - 1 ] = arr[i]; count[(arr[i] / exp) % 10 ]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0 ; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort static void radixsort( int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for ( int exp = 1 ; m / exp > 0 ; exp *= 10 ) countSort(arr, n, exp); } // A utility function to print an array static void print( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } /*Driver Code*/ public static void main(String[] args) { int arr[] = { 170 , 45 , 75 , 90 , 802 , 24 , 2 , 66 }; int n = arr.length; // Function Call radixsort(arr, n); print(arr, n); } } /* This code is contributed by Devesh Agrawal */ |
Python3
# Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len (arr) # The output array elements that will have sorted arr output = [ 0 ] * (n) # initialize count array as 0 count = [ 0 ] * ( 10 ) # Store count of occurrences in count[] for i in range ( 0 , n): index = arr[i] / / exp1 count[index % 10 ] + = 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range ( 1 , 10 ): count[i] + = count[i - 1 ] # Build the output array i = n - 1 while i > = 0 : index = arr[i] / / exp1 output[count[index % 10 ] - 1 ] = arr[i] count[index % 10 ] - = 1 i - = 1 # Copying the output array to arr[], # so that arr now contains sorted numbers i = 0 for i in range ( 0 , len (arr)): arr[i] = output[i] # Method to do Radix Sort def radixSort(arr): # Find the maximum number to know number of digits max1 = max (arr) # Do counting sort for every digit. Note that instead # of passing digit number, exp is passed. exp is 10^i # where i is current digit number exp = 1 while max1 / exp > 1 : countingSort(arr, exp) exp * = 10 # Driver code arr = [ 170 , 45 , 75 , 90 , 802 , 24 , 2 , 66 ] # Function Call radixSort(arr) for i in range ( len (arr)): print (arr[i],end = " " ) # This code is contributed by Mohit Kumra # Edited by Patrick Gallagher |
C#
// C# implementation of Radix Sort using System; class GFG { public static int getMax( int [] arr, int n) { int mx = arr[0]; for ( int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. public static void countSort( int [] arr, int n, int exp) { int [] output = new int [n]; // output array int i; int [] count = new int [10]; // initializing all elements of count to 0 for (i = 0; i < 10; i++) count[i] = 0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current // digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort public static void radixsort( int [] arr, int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for ( int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp); } // A utility function to print an array public static void print( int [] arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver Code public static void Main() { int [] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; // Function Call radixsort(arr, n); print(arr, n); } // This code is contributed by DrRoot_ } |
PHP
<?php // PHP implementation of Radix Sort // A function to do counting sort of arr[] // according to the digit represented by exp. function countSort(& $arr , $n , $exp ) { $output = array_fill (0, $n , 0); // output array $count = array_fill (0, 10, 0); // Store count of occurrences in count[] for ( $i = 0; $i < $n ; $i ++) $count [ ( $arr [ $i ] / $exp ) % 10 ]++; // Change count[i] so that count[i] // now contains actual position of // this digit in output[] for ( $i = 1; $i < 10; $i ++) $count [ $i ] += $count [ $i - 1]; // Build the output array for ( $i = $n - 1; $i >= 0; $i --) { $output [ $count [ ( $arr [ $i ] / $exp ) % 10 ] - 1] = $arr [ $i ]; $count [ ( $arr [ $i ] / $exp ) % 10 ]--; } // Copy the output array to arr[], so // that arr[] now contains sorted numbers // according to current digit for ( $i = 0; $i < $n ; $i ++) $arr [ $i ] = $output [ $i ]; } // The main function to that sorts arr[] // of size n using Radix Sort function radixsort(& $arr , $n ) { // Find the maximum number to know // number of digits $m = max( $arr ); // Do counting sort for every digit. Note // that instead of passing digit number, // exp is passed. exp is 10^i where i is // current digit number for ( $exp = 1; $m / $exp > 0; $exp *= 10) countSort( $arr , $n , $exp ); } // A utility function to print an array function PrintArray(& $arr , $n ) { for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ] . " " ; } // Driver Code $arr = array (170, 45, 75, 90, 802, 24, 2, 66); $n = count ( $arr ); // Function Call radixsort( $arr , $n ); PrintArray( $arr , $n ); // This code is contributed by rathbhupendra ?> |
Javascript
<script> // Radix sort Javascript implementation // A utility function to get maximum value in arr[] function getMax(arr,n) { let mx = arr[0]; for (let i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. function countSort(arr,n,exp) { let output = new Array(n); // output array let i; let count = new Array(10); for (let i=0;i<10;i++) count[i]=0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i]; count[Math.floor(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort function radixsort(arr,n) { // Find the maximum number to know number of digits let m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (let exp = 1; Math.floor(m / exp) > 0; exp *= 10) countSort(arr, n, exp); } // A utility function to print an array function print(arr,n) { for (let i = 0; i < n; i++) document.write(arr[i] + " " ); } /*Driver Code*/ let arr=[170, 45, 75, 90, 802, 24, 2, 66]; let n = arr.length; // Function Call radixsort(arr, n); print(arr, n); // This code is contributed by rag2127 </script> |
下面是使用桶排序技术实现基数排序的另一种方法，在查看代码时可能看起来不简单，但如果您尝试一下，就很容易了解更多关于桶排序的信息，请点击此处 https://www.geeksforgeeks.org/bucket-sort-2 并理解技术背后的逻辑。
C++
// implementation of radix sort using bin/bucket sort #include <bits/stdc++.h> using namespace std; // structure for a single linked list to help further in the // sorting struct node { int data; node* next; }; // function for creating a new node in the linked list struct node* create( int x) { node* temp = new node(); temp->data = x; temp->next = NULL; return temp; } // utility function to append node in the linked list // here head is passed by reference, to know more about this // search pass by reference void insert(node*& head, int n) { if (head == NULL) { head = create(n); return ; } node* t = head; while (t->next != NULL) t = t->next; t->next = create(n); } // utility function to pop an element from front in the list // for the sake of stability in sorting int del(node*& head) { if (head == NULL) return 0; node* temp = head; // storing the value of head before updating int val = head->data; // updation of head to next node head = head->next; delete temp; return val; } // utility function to get the number of digits in the // max_element int digits( int n) { int i = 1; if (n < 10) return 1; while (n > ( int ) pow (10, i)) i++; return i; } void radix_sort(vector< int >& arr) { // size of the array to be sorted int sz = arr.size(); // getting the maximum element in the array int max_val = *max_element(arr.begin(), arr.end()); // getting digits in the maximum element int d = digits(max_val); // creating buckets to store the pointers node** bins; // array of pointers to linked list of size 10 as // integers are decimal numbers so they can hold numbers // from 0-9 only, that's why size of 10 bins = new node*[10]; // initializing the hash array with null to all for ( int i = 0; i < 10; i++) bins[i] = NULL; // first loop working for a constant time only and inner // loop is iterating through the array to store elements // of array in the linked list by their digits value for ( int i = 0; i < d; i++) { for ( int j = 0; j < sz; j++) // bins updation insert(bins[(arr[j] / ( int ) pow (10, i)) % 10], arr[j]); int x = 0, y = 0; // write back to the array after each pass while (x < 10) { while (bins[x] != NULL) arr[y++] = del(bins[x]); x++; } } } // a utility function to print the sorted array void print(vector< int > arr) { for ( int i = 0; i < arr.size(); i++) cout << arr[i] << " " ; cout << endl; } int main() { vector< int > arr = { 573, 25, 415, 12, 161, 6 }; // function call radix_sort(arr); print(arr); return 0; } |
输出
6 12 25 161 415 573
时间复杂度与第一种方法相同，只是通过另一种方法实现。
快照：
基数排序测验
Geeksforgeks/Geeksquick上的其他排序算法：
参考资料： http://en.wikipedia.org/wiki/Radix_sort http://alg12.wikischolars.columbia.edu/file/view/RADIX.pdf 麻省理工学院视频讲座 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
