如何对一个元素只有0和1的数组进行排序？第1页

ke-meng-90 网友的相关建议:

只有0和1了还swap毛啊,从头到尾数一下有几个1然后前面zeromem后面全刷1就行了.

//----------------- 更新 -----------------------

挺早以前回的这个问题了,当时只是随口一答,题主在下面留言说只是用0和1举个例子而已,并非真的只有0和1,我就没再引申开去了. 结果昨天这个答案又给顶上来了,我本也没想再回复,

可是我一看,发现有人觉得这样更慢... 这种优化方面,术业有专攻,没概念没关系,可是你好歹在吐槽我之前先撸点代码自己试试啊. 光看复杂度? 数据结构与算法学的这么教条我也是开了眼了.

诚然,现在程序的运行效率是不如以前重要了,但是一段代码多循环一遍给一段内存擦零擦一,和每次循环都要做分支跳转和swap哪个速度快,这些基础优化的效率心里得有数啊!!!

别的也不多说了,上代码,写了10分钟,可能有bug,但是无伤大雅,sort1是前后swap的方法,sort2是我答案里的方法,比前后swap的方法快7倍:

然后,因为只存储0和1,可以换成char存储以便直接使用memset来写1,

把存储结构改成char,这回快了25倍:

以下是两个例子的代码:

       #define _CRT_SECURE_NO_WARNINGS  //fuck msvc   #include <random> #include <iostream> #include <chrono> #include <ctime>  #define SIZE 19999999*2  using namespace std;  typedef chrono::time_point<chrono::system_clock> fuck_std_time;  int* genNumbers() {     int* k = new int[SIZE];     for( int i = 0; i < SIZE; ++i )     {         int m = rand() % 2;         k[i] = m == 0 ? 0 : 1;     }     return k; }  //题主的方法 void sort1( int* k ) {     int* f = &k[0];     int* b = &k[SIZE - 1];     for( ; f != b ; )     {         //可能有bug,懒得想了         while( *f != 1 && f != b ) ++f;         while( *b != 0 && f != b ) --b;         swap( *f , *b );     } }  //我的方法 void sort2( int* k ) {      int counter = 0;     for( int i = 0; i < SIZE; ++i )     {         counter += k[i]; //数一遍1     }     memset( k , 0 , ( SIZE - counter )*sizeof( int ) );//全刷0     for( int i = ( SIZE - counter ); i < SIZE; ++i )     {         k[i] = 1; //全刷1     } }  void count_sort1( int* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort1( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort1 elapsed time: " << elapsed_seconds.count() << "s
"; }  void count_sort2( int* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort2( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort2 elapsed time: " << elapsed_seconds.count() << "s
"; }  int main() {     int* k = genNumbers();     int* k2 = new int[SIZE];     memcpy( k2 , k , sizeof( int )*SIZE );     count_sort1( k );     delete[] k;     count_sort2( k2 );     delete[] k2;     system( "PAUSE" );     return 0; }

这个是换成char的:

       #define _CRT_SECURE_NO_WARNINGS   #include <random> #include <iostream> #include <chrono> #include <ctime>  #define SIZE 19999999*2  using namespace std;  typedef chrono::time_point<chrono::system_clock> fuck_std_time;  char* genNumbers() {     char* k = new char[SIZE];     for( int i = 0; i < SIZE; ++i )     {         char m = rand() % 2;         k[i] = m == 0 ? 0 : 1;     }     return k; }  //题主的方法 void sort1( char* k ) {     char* f = &k[0];     char* b = &k[SIZE - 1];     for( ; f != b ; )     {         while( *f != 1 && f != b ) ++f;         while( *b != 0 && f != b ) --b;         swap( *f , *b );     } }  //我的方法 void sort2( char* k ) {      char counter = 0;     for( int i = 0; i < SIZE; ++i )     {         counter += k[i];     }     memset( k , 0 , ( SIZE - counter )*sizeof( char ) );     memset( k + SIZE - counter , 1 , counter*sizeof( char ) ); }  void count_sort1( char* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort1( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort1 elapsed time: " << elapsed_seconds.count() << "s
"; }  void count_sort2( char* k ) {     fuck_std_time start , end;     start = chrono::system_clock::now();     sort2( k );     end = chrono::system_clock::now();     chrono::duration<double> elapsed_seconds = end - start;     cout << "sort2 elapsed time: " << elapsed_seconds.count() << "s
"; }  char main() {     char* k = genNumbers();     char* k2 = new char[SIZE];     memcpy( k2 , k , sizeof( char )*SIZE );     count_sort1( k );     delete[] k;     count_sort2( k2 );     delete[] k2;     system( "PAUSE" );     return 0; }

如何对一个元素只有0和1的数组进行排序？的其他答案点击这里

前一个讨论

C/C++ 数组的下标为何要从 0 开始，而不从 1 开始?

下一个讨论

为何微软放弃了对w3c支持更好的tasman引擎，而继续发展对w3c不友好的trident引擎？

如何对一个元素只有0和1的数组进行排序？第1页

相关话题

前一个讨论

下一个讨论

相关的话题

如何对一个元素只有0和1的数组进行排序？ 第1页

相关话题

前一个讨论

下一个讨论

相关的话题

如何对一个元素只有0和1的数组进行排序？第1页