如何有效地对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 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<<"\nSorted Dates\n" ;
     printArr(dates, n);
     return 0;
}

输出如下

Sorted Dates
18 11 2000 
3 12 2000 
9 7 2005 
25 3 2010 
20 1 2014 
19 4 2015

本文作者：特里扬舒。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。