基本算法
全排列算法有这么几种:
(A)字典序法
(B)递增进位制数法
(C)递减进位制数法
(D)邻位对换法
废话不多说，直接上代码
C代码
#include#define swap(a,b){long temp=*a;*a=*b;*b=temp;}static int i=0; void Permutation(char* pStr, char* pBegin){ if(!pStr || !pBegin) return; if(*pBegin == 0) { i++; //printf("%s\n",pStr); } else { for(char* pCh = pBegin; *pCh != '\0'; pCh++) { swap(pCh,pBegin); //swap Permutation(pStr, pBegin + 1); swap(pCh,pBegin);//restore } } } . void main(){ char str[] ={'a','b','c','d','e','f','h','i','j','k','l','m','n','\0'}; char *p=str; Permutation(p, p); printf("%d",i);}
编译运行
[root@dev code]# gcc -o cs allsort.c -std=c99[root@dev code]# time ./cs 1932053504real 2m14.918suser 2m14.951ssys 0m0.002s
PHP代码
0){ $y = $x --; if($arr[$x] < $arr[$y]){ $z = $len; while($arr[$x] > $arr[$z]){ $z--; } list($arr[$x],$arr[$z]) = array($arr[$z],$arr[$x]); for($i=$len;$i>$y;$i--,$y++){ list($arr[$i],$arr[$y]) = array($arr[$y],$arr[$i]); } $x = $len; $rs[] = implode('',$arr); } }} 在服务器上运行
[root@localhost ~]# ltrace -c php k3.php 0256 kb256 kb19.150321960449% time seconds usecs/call calls function------ ----------- ----------- --------- -------------------- 29.32 49.854320 49854320 1 __libc_start_main 13.33 22.661048 433 52289 memcpy 12.55 21.333285 480 44379 pthread_getspecific 11.08 18.831467 650 28958 memcmp 7.74 13.162971 424 30989 malloc 7.71 13.101429 420 31128 free 6.00 10.193844 769 13243 pthread_self 5.15 8.764527 1906 4598 __ctype_b_loc 2.60 4.428846 303 14610 memset 1.57 2.672196 1336098 2 mysql_server_end 1.18 2.001771 222419 9 0.52 0.887929 167 5294 strlen 0.36 0.605670 605670 1 SSL_load_error_strings 0.21 0.362475 181237 2 dlopen 0.18 0.303863 168 1804 strrchr 0.11 0.191724 95862 2 mysql_server_init 0.09 0.149435 163 914 strcasecmp 0.07 0.114988 114988 1 OPENSSL_add_all_algorithms_noconf 0.06 0.104254 167 624 realloc 0.05 0.087413 87413 1 OpenSSL_add_all_ciphers 0.02 0.028834 28834 1 SSL_library_init 0.01 0.025241 25241 1 OpenSSL_add_all_digests 0.01 0.015832 184 86 strtol 0.01 0.015439 160 96 pthread_mutex_unlock 0.01 0.015379 163 94 strncasecmp 0.01 0.015220 158 96 pthread_mutex_lock 0.01 0.014174 164 86 atoi 0.00 0.007627 158 48 strchr 0.00 0.007012 159 44 memchr 0.00 0.006125 191 32 _setjmp 0.00 0.004771 159 30 strdup 0.00 0.004349 181 24 __lxstat 0.00 0.003919 3919 1 xmlInitParser 0.00 0.003668 3668 1 xmlCleanupParser 0.00 0.003068 161 19 tolower 0.00 0.002930 225 13 fflush 0.00 0.002105 263 8 __fxstat 0.00 0.002083 160 13 strtok_r 0.00 0.001900 271 7 write 0.00 0.001892 157 12 fileno 0.00 0.001835 203 9 calloc 0.00 0.001694 1694 1 exit 0.00 0.001618 323 5 fopen 0.00 0.001599 159 10 strcmp 0.00 0.001590 159 10 getenv 0.00 0.001561 1561 1 SSL_get_ex_new_index 0.00 0.001534 170 9 pthread_mutex_init 0.00 0.001286 160 8 pthread_mutex_destroy 0.00 0.001190 1190 1 SYS_exit_group 0.00 0.001169 194 6 floor 0.00 0.001088 362 3 __isinf 0.00 0.001056 211 5 ftell 0.00 0.001050 350 3 open 0.00 0.000920 153 6 __errno_location 0.00 0.000704 704 1 dlclose 0.00 0.000684 171 4 sprintf 0.00 0.000670 167 4 log 0.00 0.000668 222 3 fclose 0.00 0.000633 633 1 tzset 0.00 0.000596 198 3 __isnan 0.00 0.000595 595 1 curl_global_init 0.00 0.000568 568 1 setlocale 0.00 0.000567 189 3 read 0.00 0.000564 188 3 dlsym 0.00 0.000555 277 2 xmlOutputBufferCreateFilenameDefault 0.00 0.000542 180 3 close 0.00 0.000475 158 3 localeconv 0.00 0.000470 235 2 munmap 0.00 0.000467 155 3 strncmp 0.00 0.000409 204 2 signal 0.00 0.000388 194 2 __finite 0.00 0.000378 189 2 isatty 0.00 0.000373 186 2 mmap 0.00 0.000371 185 2 mysql_thread_end 0.00 0.000361 180 2 time 0.00 0.000349 174 2 xmlSetGenericErrorFunc 0.00 0.000335 167 2 xmlSetExternalEntityLoader 0.00 0.000335 167 2 xmlParserInputBufferCreateFilenameDefault 0.00 0.000334 167 2 pow 0.00 0.000321 160 2 mysql_thread_init 0.00 0.000304 152 2 sysconf 0.00 0.000301 150 2 pthread_setspecific 0.00 0.000272 272 1 fgetc 0.00 0.000237 237 1 curl_global_cleanup 0.00 0.000213 213 1 scandir 0.00 0.000201 201 1 __xstat 0.00 0.000198 198 1 getcwd 0.00 0.000194 194 1 readlink 0.00 0.000193 193 1 EVP_cleanup 0.00 0.000190 190 1 gettimeofday 0.00 0.000188 188 1 sigprocmask 0.00 0.000187 187 1 access 0.00 0.000187 187 1 rewind 0.00 0.000182 182 1 xmlRelaxNGCleanupTypes 0.00 0.000179 179 1 xmlSetStructuredErrorFunc 0.00 0.000176 176 1 X509_get_default_cert_area 0.00 0.000175 175 1 pthread_key_delete 0.00 0.000172 172 1 strncat 0.00 0.000170 170 1 snprintf 0.00 0.000170 170 1 pthread_key_create 0.00 0.000168 168 1 __xmlParserVersion 0.00 0.000168 168 1 gnu_get_libc_version 0.00 0.000167 167 1 atol 0.00 0.000159 159 1 strstr 0.00 0.000158 158 1 xmlGetExternalEntityLoader 0.00 0.000156 156 1 sigemptyset 0.00 0.000156 156 1 xmlResetLastError 0.00 0.000153 153 1 sigaddset------ ----------- ----------- --------- --------------------100.00 170.032299 229727 total
可以看到大多数的时间花费在memcpy memcmp 等函数上，CPU密集型的计算还是交给C语言吧