给定一个整形数组要求把其中的零元素移动到数组的末尾 非零元顺序保持不变

以下采用两种方法实现

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>void PrintArr( int arr[], int iSize )
{if( iSize < 0 )return;int i = 0;for( ; i < iSize; i++ ){if( !arr[i] )printf( "%d ", arr[i] );}puts( "" );
}void LocalMove( int arr[], int iSize )
{//本地移动 速度极慢 优点是消耗内存空间少if( iSize <= 1 )return;int i,j;int iZeroCount = 0;//零元总数for( i = 0; i < iSize; i++ ){if( !arr[i] )iZeroCount++;}int iZeroCur = iZeroCount;for( i  = 0; i < iSize && iZeroCur > 0; i++ ){if( !arr[i] ){for( j = i; j < iSize - ( iZeroCount - iZeroCur ); j++ ){arr[j] = arr[j+1];}arr[j-1] = 0;iZeroCur--;i--;}}//PrintArr( arr, iSize );
}int* CreateIntArr( int iSize )
{//创建整形数组puts( "CreateArr" );int* pIntArr = (int*)malloc( sizeof( int ) * iSize );if( !pIntArr )return NULL;srand( iSize );int i = 0;for( ; i < iSize; i++ ){if( 0 == i % 2 )*( pIntArr + i ) = rand();else*( pIntArr + i ) = 0;}puts( "Finish create array!" );return pIntArr;	
}int* CopyArr( int* pArrInt, int iSize )
{//复制整形数组if( !pArrInt || iSize <= 0 )return  NULL;int* pNewArr = (int*)malloc( sizeof( int ) * iSize );if( !pNewArr )return NULL;puts( "Starting copy array ..." );int i = 0;for( ; i < iSize; i++ ){*( pNewArr + i ) = *( pArrInt + i );}puts( "Finish copy array..." );return pNewArr;
}
void SaveMove( int arr[], int iSize )
{//空间换时间 这个算法的速度是上个算法速度的8万倍以上 这个专卖值得做if( iSize <= 1 )return;int i  = 0;int iNoneZero = 0;for( ; i < iSize; i++ ){if( arr[i] )iNoneZero++;}int* pIntArr = (int*)malloc( sizeof( int ) * iNoneZero );int iCur = 0;for( i = 0; i < iSize && iNoneZero > 0; i++ ){if( arr[i] ){*(pIntArr + iCur++) = arr[i];iNoneZero--;}}memset( arr, 0, iSize );for( i = 0; i < iCur; i++ ){arr[i] = *( pIntArr + i );}//PrintArr( arr, iSize );
}int main( int argc, char* argv[] )
{if( argc < 2 ){puts( "Usage: MoveZero.exe number" );return -1;}int iNum = atoi( argv[1] );if( iNum <= 0 ){puts( "Error argument!" );}int* pIntArrOne = CreateIntArr( iNum );int* pIntArrTwo = CopyArr( pIntArrOne, iNum );long lStart;lStart = GetTickCount();puts( "LocalMove" );LocalMove( pIntArrOne, iNum );printf( "LocalMove Cost Time: %ld\n", GetTickCount() - lStart );lStart = GetTickCount();puts( "SaveMove" );SaveMove( pIntArrTwo, iNum );printf( "SaveMove Cost Time: %ld\n", GetTickCount() - lStart );return 0;
}

测试结果如下：

C:\Users\fzql>"F:\MyDocument\Visual Studio 2008\Projects\VCInterview\VCInterview
\Debug\VCInterview.exe" 102400
CreateArr
Finish create array!
Starting copy array ...
Finish copy array...
LocalMove
LocalMove Cost Time: 16208
SaveMove
SaveMove Cost Time: 0

C:\Users\fzql>"F:\MyDocument\Visual Studio 2008\Projects\VCInterview\VCInterview
\Debug\VCInterview.exe" 1024000
CreateArr
Finish create array!
Starting copy array ...
Finish copy array...
LocalMove
LocalMove Cost Time: 1377832
SaveMove
SaveMove Cost Time: 16