给定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
本文作者:特里扬舒。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
来源:
https://www.srcmini02.com/68567.html