如何有效地对20年代的大列表日期进行排序

给定20年代的大日期列表, 如何有效地对列表进行排序。
例子：

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 log N)算法, 例如合并排序和自定义比较器但是我们可以使用O(n)时间对列表进行排序基数排序。在一个典型的基数排序在实现上, 我们首先按最后一位排序, 然后再按最后一位排序, 依此类推。强烈建议先通过基数排序来了解此方法。在此方法中, 我们按以下顺序排序：

首先使用计数排序按天排序
然后使用计数排序按月排序
最后, 使用计数排序按年份排序

由于天数, 月数和年数是固定的, 所以所有这三个步骤都需要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 digitdivide //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< < "\nSorted Dates\n" ; printArr(dates, n); return 0; }

输出如下