{"id":23507,"date":"2023-01-27T17:41:22","date_gmt":"2023-01-27T10:41:22","guid":{"rendered":"https:\/\/kiencang.net\/?p=23507"},"modified":"2023-08-26T18:36:06","modified_gmt":"2023-08-26T11:36:06","slug":"thuat-toan-sap-xep-quick-sort","status":"publish","type":"post","link":"https:\/\/kiencang.net\/thuat-toan-sap-xep-quick-sort\/","title":{"rendered":"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp nhanh (quick sort), gi\u1ea3i th\u00edch k\u00e8m v\u00ed d\u1ee5 trong PHP [serial v\u1ec1 c\u00e1c thu\u1eadt to\u00e1n c\u01a1 b\u1ea3n trong l\u1eadp tr\u00ecnh]"},"content":{"rendered":"\n
T\u00ean nghe \u0111\u00e3 th\u1ea5y h\u1ea5p d\u1eabn r\u1ed3i \u0111\u00fang kh\u00f4ng c\u00e1c b\u1ea1n, d\u00e2n l\u1eadp tr\u00ecnh n\u00f3i r\u1eb1ng, tr\u00ean c\u00e1c m\u1ea3ng ng\u1eabu nhi\u00ean v\u00e0 c\u00f3 s\u1ed1 l\u01b0\u1ee3ng t\u01b0\u01a1ng \u0111\u1ed1i, quick sort c\u00f3 t\u1ed1c \u0111\u1ed9 s\u1eafp x\u1ebfp t\u1ed1t h\u01a1n \u0111\u00e1ng k\u1ec3 so v\u1edbi bubble sort (s\u1eafp x\u1ebfp n\u1ed5i b\u1ecdt)<\/a> v\u00e0 t\u01b0\u01a1ng \u0111\u01b0\u01a1ng merge sort (s\u1eafp x\u1ebfp tr\u1ed9n)<\/a>, c\u1ee5 th\u1ec3 s\u1ed1 b\u01b0\u1edbc c\u1ea7n thi\u1ebft c\u1ee7a quick sort \u0111\u1ec3 s\u1eafp x\u1ebfp ho\u00e0n th\u00e0nh y\u00eau c\u1ea7u l\u00e0 \u00edt h\u01a1n [\u0111\u1ed9 ph\u1ee9c t\u1ea1p c\u1ee7a thu\u1eadt to\u00e1n l\u00e0 O(n log n)]. Gi\u1edd ch\u00fang ta s\u1ebd c\u00f9ng t\u00ecm hi\u1ec3u xem n\u00f3 nh\u01b0 th\u1ebf n\u00e0o nh\u00e9.<\/p>\n\n\n\n B\u00e0i to\u00e1n, cho d\u00e3y s\u1ed1: 4, 2, 9, 7, 3, 1, 6, 8, 10, 5<\/p>\n\n\n\n H\u00e3y s\u1eafp x\u1ebfp n\u00f3 theo th\u1ee9 t\u1ef1 t\u1eeb nh\u1ecf \u0111\u1ebfn l\u1edbn.<\/p>\n\n\n\n \u0110\u00e2y l\u00e0 \u0111o\u1ea1n m\u00e3 m\u1eabu PHP s\u1eed d\u1ee5ng \u00fd t\u01b0\u1edfng v\u1ec1 quick sort:<\/p>\n\n\n\n<?php\nfunction kc_quickSort($arr) {\n if (count($arr) <= 1) return $arr;\n \n $pivot = $arr[0];\n $left = $right = array();\n \n for ($i = 1; $i < count($arr); $i++) {\n if ($arr[$i] < $pivot) {\n $left[] = $arr[$i];\n } else {\n $right[] = $arr[$i];\n }\n }\n \n $left = kc_quickSort($left);\n $right = kc_quickSort($right);\n return array_merge($left, array($pivot), $right);\n}\n\n$arr = array(4, 2, 9, 7, 3, 1, 6, 8, 10, 5);\n$arr = kc_quickSort($arr);\n\n\/\/ hi\u1ec3n th\u1ecb k\u1ebft qu\u1ea3\nprint_r($arr);<\/code><\/pre>\n\n\n\n