关于昨天和前天写的 冒泡排序和选择排序的测试
生成10W个随机数据，来进行测试，循环十次，看看我的写法和常见的写法所使用的时间。为了准确性，两个数组所使用的数据是一模一样的，当然我会放出代码，如果你敢兴趣的话，可以自己运行。
常见的写法是 sort1， 我的写法是 sort2。
先给出选择排序的截图( 截图只有6次对比，但是应该已经能看到差别了 ):
程序代码：#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ET;
void sort2( ET *array, int l, int r );//我的写法
void sort1( ET *array, int l, int r );//常见的写法
int main( void )
{
ET a[ 100000 ], b[ 100000 ];
ET t;
int ix, i;
time_t tm1, tm2;
srand( ( unsigned )time( NULL) );
printf("sort1 sort2\n");
for( ix = 0; ix < 10; ++ix )
{
for( i = 0; i < 100000; ++i )
{
t = rand() % 10000;
a[ i ] = t;
b[ i ] = t;
}
tm1 = time( NULL );
sort1( a, 0, 100000 );
tm2 = time( NULL );
printf( "%.2f ", difftime( tm2, tm1 ) );
tm1 = time( NULL );
sort2( b, 0, 100000 );
tm2 = time( NULL );
printf( "%.2f\n", difftime( tm2, tm1 ) );
}
return 0;
}
void sort1( ET *array, int l, int r )
{
ET t;
int ix, i;
int min;
for( ix = l; ix < r; ++ix )
{
for( i = ix + 1; i < r; ++i )
min = array[ ix ] > array[ i ] ? i : ix ;
t = array[ min ];
array[ min ] = array[ ix ];
array[ ix ] = t;
}
}
void sort2( ET *array, int l, int r )
{
int minix, maxix;
ET min, max;
int i;
int t;
while( l < r )
{
for( minix = l, maxix = l, i = l + 1; i < r; ++i )
{
minix = array[ minix ] < array[ i ] ? minix : i;
maxix = array[ maxix ] > array[ i ] ? maxix : i;
}
if( minix == r - 1 || maxix == l )
{
if( minix == r - 1 )
{
t = maxix;
max = array[ r - 1 ];
array[ r - 1 ] = array[ maxix ];
array[ maxix ] = max;
min = array[ t ];
array[ t ] = array[ l ];
array[ l ] = min;
}
else
{
t = minix;
min = array[ l ];
array[ l ] = array[ minix ];
array[ minix ] = min;
max = array[ t ];
array[ t ] = array[ r - 1 ];
array[ r - 1 ] = max;
}
}
else
{
min = array[ l ];
array[ l ] = array[ minix ];
array[ minix ] = min;
max = array[ r - 1 ];
array[ r - 1 ] = array[ maxix ];
array[ maxix ] = max;
}
++l;
--r;
}
}
冒泡排序：
程序代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ET;
void sort2( ET *array, int l, int r );//我的写法
void sort1( ET *array, int l, int r );//常见的写法
int main( void )
{
ET a[ 100000 ], b[ 100000 ];
ET t;
int ix, i;
time_t tm1, tm2;
srand( ( unsigned )time( NULL) );
printf("sort1 sort2\n");
for( ix = 0; ix < 10; ++ix )
{
for( i = 0; i < 100000; ++i )
{
t = rand() % 10000;
a[ i ] = t;
b[ i ] = t;
}
tm1 = time( NULL );
sort1( a, 0, 100000 );
tm2 = time( NULL );
printf( "%.2f ", difftime( tm2, tm1 ) );
tm1 = time( NULL );
sort2( b, 0, 100000 );
tm2 = time( NULL );
printf( "%.2f\n", difftime( tm2, tm1 ) );
}
return 0;
}
void sort1( ET *array, int l, int r )
{
int i,j;
ET t;
for( i = l; i < r; ++i)
for( j = i + 1; j < r; ++j )
if( array[ i ] > array[ j ] )
{
t = array[ i ];
array[ i ] = array[ j ];
array[ j ] = t;
}
}
void sort2( ET *array, int l, int r )
{
int minix, maxix;
int R;
ET temp;
for( ; l < r; ++l, --r )
{
for( minix = l + 1, maxix = r - 2, R = r - 1; minix <= R; ++minix, --maxix )
{
if( array[ l ] > array[ minix ] )
{
temp = array[ l ];
array[ l ] = array[ minix ];
array[ minix ] = temp;
}
if( array[ R ] < array[ maxix ] )
{
temp = array[ R ];
array[ R ] = array[ maxix ];
array[ maxix ] = temp;
}
}
}
}
