绠楁硶鍘熺悊浠ヤ笅鍔ㄥ浘鏉ヨ嚜@浜斿垎閽熷娴嬶紝婕旂ず浜嗗綊骞剁畻娉曠殑鍘熺悊鍜屾楠ゃ€傚師鐞嗭細浣跨敤閫掑綊锛屽厛鎷嗗垎锛屽啀鍚堝苟锛屽啀鎺掑簭銆傛楠わ細骞冲潎寰楀垎鍒楁槸涓や釜瀛愬簭鍒椼€傞€掑綊鍦伴噸澶嶄笂涓€姝ワ紝鐩村埌瀛愬簭鍒楀彧鏈変竴涓厓绱犮€傜埗搴忓垪鍚堝苟涓や釜瀛愬簭鍒楀苟瀵瑰畠浠繘琛屾帓搴忋€傞€掑綊杩斿洖搴忓垪浠ｇ爜瀹炵幇//鍚堝苟鎺掑簭涓荤▼搴忓嚱鏁癿ergeSort($arr){$len=count($arr);濡傛灉锛?len<=1锛墈杩斿洖$arr;}//閫掑綊缁撴潫鏉′欢锛屽埌杩欎竴姝ユ椂锛屾暟缁勫彧鍓╀笅涓€涓厓绱狅紝鍗虫暟缁勫垎绂?mid=intval($len/2);//鍙栨暟缁勭殑涓棿$left=array_slice($arr,0,$mid);//灏嗘暟缁勭殑0-mid閮ㄥ垎鍚戝乏鎷嗗垎$right=array_slice($arr,$mid);//灏嗘暟缁勭殑涓閮ㄥ垎鍚戝彸鎷嗗垎$left=mergeSort($left);//宸﹁竟鎷嗗垎鍚庡紑濮嬮€掑綊褰掑苟$right=mergeSort($right);//鍙宠竟鍒嗗壊鍒嗗壊鍚庡紑濮嬮€掑綊寰€涓?arr=merge($left,$right);//鍚堝苟涓や釜鏁扮粍锛岀户缁€掑綊return$arr;}//鍚堝苟鍑芥暟灏嗘寚瀹氫袱涓湁搴忔暟缁?arrA,arr)鍚堝苟鎺掑簭鍑芥暟merge($arrA,$arrB){$arrC=array();while(count($arrA)&&count($arrB)){//杩欓噷涓嶆柇鐨勫垽鏂摢涓€兼瘮杈冨皬锛屾妸姣旇緝灏忕殑鍊肩粰arrC锛屼絾鏄渶鍚庤偗瀹氳繕鍓╀笅鍑犱釜鍊硷紝//瑕佷箞鍓╀笅arrA涓殑锛岃涔堢暀涓媋rrB涓殑锛岃繖浜涙湁搴忕殑鍊煎繀椤诲ぇ浜巃rrC涓殑鎵€鏈夊€硷紝鎵€浠ヤ娇鐢?arrC[]=$arrA[0]<$arrB[0]锛焌rray_shift($arrA):array_shift($arrB);}杩斿洖array_merge($arrC,$arrA,$arrB);}娴嬭瘯锛?startTime=microtime(1);$arr=鑼冨洿(1,10);shuffle($arr);echo"鎺掑簭鍓?",implode(',',$arr),"\n";$sortArr=mergeSort($arr);echo"鎺掑簭鍚?",implode(',',$sortArr),"\n";echo"浣跨敤鏃堕棿锛?,microtime(1)-$startTime,"s\n";鏃堕棿澶嶆潅搴﹀綊骞舵帓搴忕殑鏃堕棿澶嶆潅搴︽槸O(N*lgN)鍋囪鎺掑簭鐨勫簭鍒椾腑鏈塏涓暟銆傞亶鍘嗕竴娆¤绋嬬殑鏃堕棿澶嶆潅搴︽槸O(N)锛岄渶瑕侀亶鍘嗗灏戞锛熷綊骞舵帓搴忕殑褰㈠紡鏄竴妫典簩鍙夋爲锛屽畠闇€瑕侀亶鍘嗙殑娆℃暟灏辨槸浜屽弶鏍戠殑娣卞害锛屾寜鐓у畬鍏ㄤ簩鍙夋爲鏉ョ湅锛屽畠鐨勬椂闂村鏉傚害鏄疧(N*lgN)銆傚弬鑰冭祫鏂欏悎骞朵笌鎺掑簭鍗佸ぇ缁忓吀鎺掑簭绠楁硶鍔ㄧ敾涓庤В鏋愭劅璋㈤槄璇伙紝鎴戣寰楀唴瀹逛笉閿欙紝鐐逛釜璧炲惂馃槅鍘熸枃鍦板潃锛歨ttps://shockerli.net/post/me...
