Сортировка связанного списка по своей природе будет либо O (N ^ 2), либо задействует внешнее хранилище с произвольным доступом.
Векторы имеют хранилище с произвольным доступом. Как и массивы. Сортировка может быть O (NlogN).
При 1000 элементах вы начнете видеть разницу между O (N ^ 2) и O (NlogN). На 1 000 000 элементов вы обязательно заметите разницу!
В очень особых ситуациях можно получить сортировку O (N). (Например: сортировка колоды игральных карт. Мы можем создать функцию (карту), которая отображает каждую карту в ее отсортированном положении.)
Но в целом O (NlogN) так же хорош, как и получает. Так что вы могли бы также использовать sort () STL!
Просто добавьте # include
Все, что вам нужно добавить, это оператор <(). Или сортировочный функтор. </p>
Но одно предложение: ради бога, если вы собираетесь отсортировать дату, либо закодируйте ее как длинное целое, представляющее секунды с момента эпохи (mktime?), Или, по крайней мере, используйте "год / месяц / день-час: минута: секунда. Фракция" формат. (И УБЕДИТЕСЬ, что все 2 (или 4) цифры с ведущими нулями!) Сравнение «6/22 / 2008-4: 34» и «12/5 / 2007-14: 54» потребует анализа! Сравнивать "2008/06 / 22-04: 34" с "2007/12 / 05-14: 54" гораздо проще. (Хотя все еще намного менее эффективно, чем сравнение двух целых чисел!)
Рич написал:
другие ответы, похоже, больше входят в синтаксис, чего мне действительно не хватает.
Ok. С базовым типом int мы имеем:
#define PRINT(DATA,N) for(int i=0; i<N; i++) { cout << (i>0?", ":"") << DATA[i]; } cout << endl;
int
main()
{
// Creating and Sorting a stack-based array.
int d [10] = { 1, 4, 0, 2, 8, 6, 3, 5, 9, 7 };
PRINT(d,10);
sort( d, d+10 );
PRINT(d,10);
cout << endl;
// Creating a vector.
int eData [10] = { 1, 4, 0, 2, 8, 6, 3, 5, 9, 7 };
vector<int> e;
for(int i=0; i<10; i++ )
e.push_back( eData[i] );
// Sorting a vector.
PRINT(e,10);
sort(e.begin(), e.end());
PRINT(e,10);
}
С вашим собственным типом мы имеем:
class Data
{
public:
string m_PackLine;
string m_FileDateTime;
int m_NumberDownloads;
/* Lets simplify creating Data elements down below. */
Data( const string & thePackLine = "",
const string & theDateTime = "",
int theDownloads = 0 )
: m_PackLine ( thePackLine ),
m_FileDateTime ( theDateTime ),
m_NumberDownloads ( theDownloads )
{ }
/* Can't use constructor with arrays */
void set( const string & thePackLine,
const string & theDateTime,
int theDownloads = 0 )
{
m_PackLine = thePackLine;
m_FileDateTime = theDateTime;
m_NumberDownloads = theDownloads;
}
/* Lets simplify printing out down below. */
ostream & operator<<( ostream & theOstream ) const
{
theOstream << "PackLine=\"" << m_PackLine
<< "\" fileDateTime=\"" << m_FileDateTime
<< "\" downloads=" << m_NumberDownloads;
return theOstream;
}
/*
* This is IT! All you need to add to use sort()!
* Note: Sort is just on m_FileDateTime. Everything else is superfluous.
* Note: Assumes "YEAR/MONTH/DAY HOUR:MINUTE" format.
*/
bool operator< ( const Data & theOtherData ) const
{ return m_FileDateTime < theOtherData.m_FileDateTime; }
};
/* Rest of simplifying printing out down below. */
ostream & operator<<( ostream & theOstream, const Data & theData )
{ return theData.operator<<( theOstream ); }
/* Printing out data set. */
#define PRINT(DATA,N) for(int i=0; i<N; i++) { cout << "[" << i << "] " << DATA[i] << endl; } cout << endl;
int
main()
{
// Creating a stack-based array.
Data d [10];
d[0].set( "Line 1", "2008/01/01 04:34", 1 );
d[1].set( "Line 4", "2008/01/04 04:34", 4 );
d[2].set( "Line 0", "2008/01/00 04:34", 0 );
d[3].set( "Line 2", "2008/01/02 04:34", 2 );
d[4].set( "Line 8", "2008/01/08 04:34", 8 );
d[5].set( "Line 6", "2008/01/06 04:34", 6 );
d[6].set( "Line 3", "2008/01/03 04:34", 3 );
d[7].set( "Line 5", "2008/01/05 04:34", 5 );
d[8].set( "Line 9", "2008/01/09 04:34", 9 );
d[9].set( "Line 7", "2008/01/07 04:34", 7 );
// Sorting a stack-based array.
PRINT(d,10);
sort( d, d+10 );
PRINT(d,10);
cout << endl;
// Creating a vector.
vector<Data> e;
e.push_back( Data( "Line 1", "2008/01/01 04:34", 1 ) );
e.push_back( Data( "Line 4", "2008/01/04 04:34", 4 ) );
e.push_back( Data( "Line 0", "2008/01/00 04:34", 0 ) );
e.push_back( Data( "Line 2", "2008/01/02 04:34", 2 ) );
e.push_back( Data( "Line 8", "2008/01/08 04:34", 8 ) );
e.push_back( Data( "Line 6", "2008/01/06 04:34", 6 ) );
e.push_back( Data( "Line 3", "2008/01/03 04:34", 3 ) );
e.push_back( Data( "Line 5", "2008/01/05 04:34", 5 ) );
e.push_back( Data( "Line 9", "2008/01/09 04:34", 9 ) );
e.push_back( Data( "Line 7", "2008/01/07 04:34", 7 ) );
// Sorting a vector.
PRINT(e,10);
sort(e.begin(), e.end());
PRINT(e,10);
}