考虑到20年代的一大串日期，如何有效地对这些日期进行排序。
null
例子：
Input: Date arr[] = {{20, 1, 2014}, {25, 3, 2010}, { 3, 12, 2000}, {18, 11, 2001}, {19, 4, 2015}, { 9, 7, 2005}}Output: Date arr[] = {{ 3, 12, 2000}, {18, 11, 2001}, { 9, 7, 2005}, {25, 3, 2010}, {20, 1, 2014}, {19, 4, 2015}}
一个简单的解决方案是使用O（N logn）算法，如 合并排序 还有一个自定义比较器。但是我们可以使用 基数排序 .典型的 基数排序 实现时，我们首先按最后一位数字排序，然后按最后第二位数字排序，依此类推。强烈建议首先通过基数排序来了解此方法。在这种方法中，我们按照以下顺序进行排序：
- 第一次使用计数排序逐日排序
- 然后使用计数排序按月排序
- 最后，使用计数排序按年份排序
由于天数、月数和年数是固定的，所以这三个步骤都需要O（n）时间。因此，总体时间复杂度为O（n）。
下面是C++实现上述思想：
C++
// C++ program to sort an array // of dates using Radix Sort #include <bits/stdc++.h> using namespace std; // Utilitiy function to obtain // maximum date or month or year int getMax( int arr[][3], int n, int q) { int maxi = INT_MIN; for ( int i=0;i<n;i++){ maxi = max(maxi,arr[i][q]); } return maxi; } // A function to do counting sort of arr[] // according to given q i.e. // (0 for day, 1 for month, 2 for year) void sortDatesUtil( int arr[][3], int n, int q) { int maxi = getMax(arr,n,q); int p = 1; while (maxi>0){ //to extract last digit divide // by p then %10 // Store count of occurrences in cnt[] int cnt[10]={0}; for ( int i=0;i<n;i++) { cnt[(arr[i][q]/p)%10]++; } for ( int i=1;i<10;i++) { cnt[i]+=cnt[i-1]; } int ans[n][3]; for ( int i=n-1;i>=0;i--) { int lastDigit = (arr[i][q]/p)%10; // Build the output array for ( int j=0;j<3;j++) { ans[cnt[lastDigit]-1][j] =arr[i][j]; } cnt[lastDigit]--; } // Copy the output array to arr[], // so that arr[] now // contains sorted numbers // according to current digit for ( int i=0;i<n;i++) { for ( int j=0;j<3;j++) { arr[i][j] = ans[i][j]; } } // update p to get // the next digit p*=10; maxi/=10; } } // The main function that sorts // array of dates // using Radix Sort void sortDates( int dates[][3], int n) { // First sort by day sortDatesUtil(dates, n, 0); // Then by month sortDatesUtil(dates, n, 1); // Finally by year sortDatesUtil(dates, n, 2); } // A utility function to print an array void printArr( int arr[][3], int n) { for ( int i=0;i<6;i++) { for ( int j=0;j<3;j++) { cout<<arr[i][j]<< " " ; } cout<<endl; } } // Driver Code int main() { int dates[][3] = {{20, 1, 2014}, {25, 3, 2010}, { 3, 12, 2000}, {18, 11, 2000}, {19, 4, 2015}, { 9, 7, 2005}}; int n = sizeof (dates)/ sizeof (dates[0]); // Function Call sortDates(dates,n); cout<< "Sorted Dates" ; printArr(dates,n); return 0; } |
JAVA
// Java program to sort an array // of dates using Radix Sort import java.util.*; class GFG{ // Utilitiy function to obtain // maximum date or month or year static int getMax( int arr[][], int n, int q) { int maxi = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { maxi = Math.max(maxi, arr[i][q]); } return maxi; } // A function to do counting sort of arr[] // according to given q i.e. // (0 for day, 1 for month, 2 for year) static void sortDatesUtil( int arr[][], int n, int q) { int maxi = getMax(arr,n,q); int p = 1 ; while (maxi > 0 ) { // to extract last digit divide // by p then %10 // Store count of occurrences in cnt[] int []cnt = new int [ 10 ]; for ( int i = 0 ; i < n; i++) { cnt[(arr[i][q]/p) % 10 ]++; } for ( int i = 1 ; i < 10 ; i++) { cnt[i] += cnt[i - 1 ]; } int [][]ans = new int [n][ 3 ]; for ( int i = n - 1 ; i >= 0 ; i--) { int lastDigit = (arr[i][q]/p) % 10 ; // Build the output array for ( int j = 0 ; j < 3 ; j++) { ans[cnt[lastDigit]- 1 ][j] =arr[i][j]; } cnt[lastDigit]--; } // Copy the output array to arr[], // so that arr[] now // contains sorted numbers // according to current digit for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < 3 ; j++) { arr[i][j] = ans[i][j]; } } // update p to get // the next digit p *= 10 ; maxi /= 10 ; } } // The main function that sorts // array of dates // using Radix Sort static void sortDates( int dates[][], int n) { // First sort by day sortDatesUtil(dates, n, 0 ); // Then by month sortDatesUtil(dates, n, 1 ); // Finally by year sortDatesUtil(dates, n, 2 ); } // A utility function to print an array static void printArr( int arr[][], int n) { for ( int i = 0 ; i < 6 ; i++) { for ( int j = 0 ; j < 3 ; j++) { System.out.print(arr[i][j] + " " ); } System.out.println(); } } // Driver Code public static void main(String[] args) { int dates[][] = {{ 20 , 1 , 2014 }, { 25 , 3 , 2010 }, { 3 , 12 , 2000 }, { 18 , 11 , 2000 }, { 19 , 4 , 2015 }, { 9 , 7 , 2005 }}; int n = dates.length; // Function Call sortDates(dates,n); System.out.print( "Sorted Dates" ); printArr(dates,n); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to sort an array # of dates using Radix Sort import sys # Utilitiy function to obtain # maximum date or month or year def getMax(arr, n, q): maxi = sys.maxsize; for i in range (n): maxi = max (maxi, arr[i][q]); return maxi; # A function to do counting sort of arr # according to given q i.e. # (0 for day, 1 for month, 2 for year) def sortDatesUtil(arr, n, q): maxi = getMax(arr, n, q); p = 1 ; while (maxi > 0 ): # to extract last digit divide # by p then %10 # Store count of occurrences in cnt cnt = [ 0 for i in range ( 10 )]; for i in range (n): cnt[(arr[i][q] / / p) % 10 ] + = 1 ; for i in range ( 1 , 10 ): cnt[i] + = cnt[i - 1 ]; ans = [[ 0 for i in range ( 3 )] for j in range (n)]; for i in range (n - 1 , - 1 , - 1 ): lastDigit = (arr[i][q] / / p) % 10 ; # Build the output array for j in range ( 3 ): ans[cnt[lastDigit] - 1 ][j] = arr[i][j]; cnt[lastDigit] - = 1 ; # Copy the output array to arr, # so that arr now # contains sorted numbers # according to current digit for i in range (n): for j in range ( 3 ): arr[i][j] = ans[i][j]; # update p to get # the next digit p * = 10 ; maxi = maxi / / 10 ; # The main function that sorts # array of dates # using Radix Sort def sortDates(dates, n): # First sort by day sortDatesUtil(dates, n, 0 ); # Then by month sortDatesUtil(dates, n, 1 ); # Finally by year sortDatesUtil(dates, n, 2 ); # A utility function to print an array def printArr(arr, n): for i in range ( 6 ): for j in range ( 3 ): print (arr[i][j], end = " " ); print (); # Driver Code if __name__ = = '__main__' : dates = [[ 20 , 1 , 2014 ],[ 25 , 3 , 2010 ],[ 3 , 12 , 2000 ],[ 18 , 11 , 2000 ],[ 19 , 4 , 2015 ], [ 9 , 7 , 2005 ]] ; n = len (dates); # Function Call sortDates(dates, n); print ( "Sorted Dates" ); printArr(dates, n); # This code is contributed by gauravrajput1 |
C#
// C# program to sort an array // of dates using Radix Sort using System; public class GFG { // Utilitiy function to obtain // maximum date or month or year static int getMax( int [,]arr, int n, int q) { int maxi = int .MinValue; for ( int i = 0; i < n; i++) { maxi = Math.Max(maxi, arr[i,q]); } return maxi; } // A function to do counting sort of []arr // according to given q i.e. // (0 for day, 1 for month, 2 for year) static void sortDatesUtil( int [,]arr, int n, int q) { int maxi = getMax(arr,n,q); int p = 1; while (maxi > 0) { // to extract last digit divide // by p then %10 // Store count of occurrences in cnt[] int []cnt = new int [10]; for ( int i = 0; i < n; i++) { cnt[(arr[i,q]/p) % 10]++; } for ( int i = 1; i < 10; i++) { cnt[i] += cnt[i - 1]; } int [,]ans = new int [n,3]; for ( int i = n - 1; i >= 0; i--) { int lastDigit = (arr[i,q]/p) % 10; // Build the output array for ( int j = 0; j < 3; j++) { ans[cnt[lastDigit]-1,j] =arr[i,j]; } cnt[lastDigit]--; } // Copy the output array to []arr, // so that []arr now // contains sorted numbers // according to current digit for ( int i = 0; i < n; i++) { for ( int j = 0; j < 3; j++) { arr[i,j] = ans[i,j]; } } // update p to get // the next digit p *= 10; maxi /= 10; } } // The main function that sorts // array of dates // using Radix Sort static void sortDates( int [,]dates, int n) { // First sort by day sortDatesUtil(dates, n, 0); // Then by month sortDatesUtil(dates, n, 1); // Finally by year sortDatesUtil(dates, n, 2); } // A utility function to print an array static void printArr( int [,]arr, int n) { for ( int i = 0; i < 6; i++) { for ( int j = 0; j < 3; j++) { Console.Write(arr[i, j] + " " ); } Console.WriteLine(); } } // Driver Code public static void Main(String[] args) { int [,]dates = {{20, 1, 2014}, {25, 3, 2010}, { 3, 12, 2000}, {18, 11, 2000}, {19, 4, 2015}, { 9, 7, 2005}}; int n = dates.GetLength(0); // Function Call sortDates(dates,n); Console.Write( "Sorted Dates" ); printArr(dates,n); } } // This code is contributed by aashish1995. |
Javascript
<script> // javascript program to sort an array // of dates using Radix Sort // Utilitiy function to obtain // maximum date or month or year function getMax(arr , n , q) { var maxi = Number.MIN_VALUE; for ( var i = 0; i < n; i++) { maxi = Math.max(maxi, arr[i][q]); } return maxi; } // A function to do counting sort of arr // according to given q i.e. // (0 for day, 1 for month, 2 for year) function sortDatesUtil(arr , n , q) { var maxi = getMax(arr, n, q); var p = 1; while (maxi > 0) { // to extract last digit divide // by p then %10 // Store count of occurrences in cnt var cnt = Array(10).fill(0); for ( var i = 0; i < n; i++) { cnt[parseInt((arr[i][q] / p)) % 10]++; } for ( var i = 1; i < 10; i++) { cnt[i] += cnt[i - 1]; } var ans = Array(n).fill().map(()=>Array(3).fill(0)); for ( var i = n - 1; i >= 0; i--) { var lastDigit = parseInt((arr[i][q] / p) % 10); // Build the output array for ( var j = 0; j < 3; j++) { ans[cnt[lastDigit] - 1][j] = arr[i][j]; } cnt[lastDigit]--; } // Copy the output array to arr, // so that arr now // contains sorted numbers // according to current digit for ( var i = 0; i < n; i++) { for ( var j = 0; j < 3; j++) { arr[i][j] = ans[i][j]; } } // update p to get // the next digit p *= 10; maxi = parseInt(maxi/10); } } // The main function that sorts // array of dates // using Radix Sort function sortDates(dates , n) { // First sort by day sortDatesUtil(dates, n, 0); // Then by month sortDatesUtil(dates, n, 1); // Finally by year sortDatesUtil(dates, n, 2); } // A utility function to print an array function printArr(arr , n) { for ( var i = 0; i < 6; i++) { for ( var j = 0; j < 3; j++) { document.write(arr[i][j] + " " ); } document.write( "<br/>" ); } } // Driver Code var dates = [ [ 20, 1, 2014 ], [ 25, 3, 2010 ], [ 3, 12, 2000 ], [ 18, 11, 2000 ], [ 19, 4, 2015 ], [ 9, 7, 2005 ] ]; var n = dates.length; // Function Call sortDates(dates, n); document.write( "Sorted Dates" ); printArr(dates, n); // This code is contributed by gauravrajput1 </script> |
输出
Sorted Dates18 11 2000 3 12 2000 9 7 2005 25 3 2010 20 1 2014 19 4 2015
本文由 tpriyanshu 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
