给定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)时间对列表进行排序基数排序。在一个典型的基数排序在实现上, 我们首先按最后一位排序, 然后再按最后一位排序, 依此类推。强烈建议先通过基数排序来了解此方法。在此方法中, 我们按以下顺序排序:
- 首先使用计数排序按天排序
- 然后使用计数排序按月排序
- 最后, 使用计数排序按年份排序
以下是上述想法的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;
}
输出如下
Sorted Dates
18 11 2000
3 12 2000
9 7 2005
25 3 2010
20 1 2014
19 4 2015
【如何有效地对20年代的大列表日期进行排序】本文作者:特里扬舒。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- 如何在cmd(命令行)上执行C#程序()
- Python如何使用Pandas实现vLookup(代码实例)
- 如何使用PHP将HTML标签显示为纯文本
- 编译mate-control-center(error: required directory ./help does not exist)
- 生产制造业如何谋求数字化转型(需要哪些信息化系统做支撑?)
- No package ‘gtk+-3.0‘ found
- No package ‘libpeas-1.0‘ found/No package ‘libpeas-gtk-1.0‘
- undefined reference to `gdk_monitor_get_scale_factor/gtk_widget_get_scale_factor‘
- 无法定位软件包dbus-glib-1