{"id":23518,"date":"2023-01-27T22:01:40","date_gmt":"2023-01-27T15:01:40","guid":{"rendered":"https:\/\/kiencang.net\/?p=23518"},"modified":"2023-08-26T18:38:39","modified_gmt":"2023-08-26T11:38:39","slug":"thuat-toan-merge-sort","status":"publish","type":"post","link":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/","title":{"rendered":"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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

Thu\u1eadt to\u00e1n ti\u1ebfp theo m\u00e0 ch\u00fang ta s\u1ebd c\u00f9ng t\u00ecm hi\u1ec3u sau khi \u0111i qua 2 thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp n\u1ed5i b\u1ecdt (bubble sort)<\/a> v\u00e0 s\u1eafp x\u1ebfp nhanh (quick sort)<\/a> l\u00e0 s\u1eafp x\u1ebfp tr\u1ed9n (merge sort). <\/p>\n\n\n\n

S\u1eafp x\u1ebfp tr\u1ed9n c\u00f3 nhi\u1ec1u \u0111i\u1ec3m t\u01b0\u01a1ng \u0111\u1ed3ng v\u1edbi s\u1eafp x\u1ebfp nhanh, khi n\u00f3 c\u0169ng s\u1eed d\u1ee5ng \u0111\u1ec7 quy<\/a> l\u00e0m ph\u01b0\u01a1ng th\u1ee9c. V\u1ec1 t\u1ed1c \u0111\u1ed9, b\u00ean l\u1eadp tr\u00ecnh n\u00f3i r\u1eb1ng, trong \u0111a s\u1ed1 tr\u01b0\u1eddng h\u1ee3p n\u00f3 nhanh h\u01a1n s\u1eafp x\u1ebfp n\u1ed5i b\u1ecdt, v\u00e0 t\u01b0\u01a1ng \u0111\u01b0\u01a1ng s\u1eafp x\u1ebfp nhanh.<\/p>\n\n\n\n

B\u00e0i to\u00e1n: m\u1ed9t d\u00e3y s\u1ed1 kh\u00f4ng theo th\u1ee9 t\u1ef1 4, 2, 9, 7, 3, 1, 6, 8, 10, 5. Y\u00eau c\u1ea7u s\u1eafp x\u1ebfp theo th\u1ee9 t\u1ef1 t\u1eeb nh\u1ecf \u0111\u1ebfn l\u1edbn.<\/p>\n\n\n\n

M\u00e3 m\u1eabu trong PHP:<\/p>\n\n\n\n

<?php \nfunction mergeSort($arr) {\n    $len = count($arr);\n    if ($len <= 1) return $arr;\n\n    $mid = (int)($len\/2);\n\n    $left = array_slice($arr, 0, $mid);\n    $right = array_slice($arr, $mid);\n\n    $left = mergeSort($left);\n    $right = mergeSort($right);\n\n    return merge($left, $right);\n}\n\nfunction merge($left, $right) {\n    $result = array();\n    $i = 0;\n    $j = 0;\n\n    while (count($left) > $i && count($right) > $j) {\n        if ($left[$i] > $right[$j]) {\n            $result[] = $right[$j];\n            $j++;\n        } else {\n            $result[] = $left[$i];\n            $i++;\n        }\n    }\n\n    while (count($left) > $i) {\n        $result[] = $left[$i];\n        $i++;\n    }\n\n    while (count($right) > $j) {\n        $result[] = $right[$j];\n        $j++;\n    }\n\n    return $result;\n}\n\n$arr = array(4, 2, 9, 7, 3, 1, 6, 8, 10, 5);\nprint_r(mergeSort($arr));<\/code><\/pre>\n\n\n\n
Gi\u1ea3i th\u00edch qua:<\/p>\n\n\n\n
    \n
  • $arr: m\u1ea3ng ch\u1ee9a c\u00e1c ph\u1ea7n t\u1eed c\u1ea7n s\u1eafp x\u1ebfp<\/li>\n\n\n\n
  • $len: s\u1ed1 l\u01b0\u1ee3ng ph\u1ea7n t\u1eed c\u1ee7a m\u1ea3ng, \u1edf \u0111\u00e2y l\u00e0 10<\/li>\n\n\n\n
  • array_slice($arr, 0, $mid): l\u1ea5y ph\u1ea7n t\u1eed t\u1eeb 0 cho \u0111\u1ebfn ph\u1ea7n t\u1eed c\u00f3 th\u1ee9 t\u1ef1 $mid trong m\u1ea3ng $arr<\/li>\n\n\n\n
  • array_slice($arr, $mid): l\u1ea5y ph\u1ea7n t\u1eed c\u00f3 th\u1ee9 t\u1ef1 t\u1eeb $mid + 1 cho \u0111\u1ebfn ph\u1ea7n t\u1eed cu\u1ed1i c\u00f9ng trong $arr<\/li>\n<\/ul>\n\n\n\n
    \u00dd t\u01b0\u1edfng ch\u00ednh:<\/p>\n\n\n\n
      \n
    • S\u1eafp x\u1ebfp tr\u1ed9n s\u1ebd chia m\u1ea3ng l\u00e0m 2 ph\u1ea7n c\u00f3 s\u1ed1 l\u01b0\u1ee3ng t\u01b0\u01a1ng \u0111\u01b0\u01a1ng nhau sau (n\u1ebfu ch\u1eb5n n\u00f3 s\u1ebd chia \u0111\u1ec1u, n\u1ebfu l\u1ebb, th\u00ec m\u1ed9t ph\u1ea7n s\u1ebd c\u00f3 nhi\u1ec1u h\u01a1n ph\u1ea7n c\u00f2n l\u1ea1i m\u1ed9t ph\u1ea7n t\u1eed). Trong v\u00ed d\u1ee5 tr\u00ean, 2 m\u1ea3ng \u0111\u01b0\u1ee3c chia s\u1ebd l\u00e0: 4, 2, 9, 7, 3 v\u00e0 1, 6, 8, 10, 6<\/li>\n\n\n\n
    • Ti\u1ebfp \u0111\u1ebfn t\u1eebng ph\u1ea7n t\u1eed trong m\u1ea3ng s\u1ebd \u0111\u01b0\u1ee3c so s\u00e1nh v\u1edbi nhau theo th\u1ee9 t\u1ef1. Nh\u01b0 \u1edf tr\u00ean 4 s\u1ebd \u0111\u01b0\u1ee3c so v\u1edbi 1, c\u00f2n 2 \u0111\u01b0\u1ee3c so v\u1edbi 6, c\u1ee9 th\u1ec3 cho \u0111\u1ebfn cu\u1ed1i l\u00e0 3 \u0111\u01b0\u1ee3c so v\u1edbi 6. Trong m\u1ed7i c\u1eb7p so s\u00e1nh \u0111\u00f3, ph\u1ea7n t\u1eed nh\u1ecf s\u1ebd \u0111\u01b0\u1ee3c \u0111\u01b0a v\u00e0o m\u1ea3ng tr\u01b0\u1edbc (v\u00ed ch\u00fang ta \u0111ang c\u1ea7n s\u1eafp x\u1ebfp t\u1eeb b\u00e9 \u0111\u1ebfn l\u1edbn), m\u1ea3ng k\u1ebft qu\u1ea3 \u0111\u00f3 l\u00e0 $result. <\/li>\n<\/ul>\n\n\n\n
      \u0110o\u1ea1n m\u00e3 nh\u1eadn tr\u00e1ch nhi\u1ec7m so s\u00e1nh c\u1eb7p \u0111\u00f4i n\u00e0y l\u00e0:<\/p>\n\n\n\n
          while (count($left) > $i && count($right) > $j) {\n        if ($left[$i] > $right[$j]) {\n            $result[] = $right[$j];\n            $j++;\n        } else {\n            $result[] = $left[$i];\n            $i++;\n        }\n    }<\/code><\/pre>\n\n\n\n
        \n
      • Qu\u00e1 tr\u00ecnh tr\u00ean l\u00e0 \u0111\u1ec7 quy, n\u00ean cu\u1ed1i c\u00f9ng ph\u1ea7n t\u1eed nh\u1ecf nh\u1ea5t s\u1ebd \u1edf v\u1ecb tr\u00ed \u0111\u1ea7u v\u00e0 c\u1ee9 th\u1ebf t\u0103ng d\u1ea7n cho \u0111\u1ebfn v\u1ecb tr\u00ed cu\u1ed1i c\u00f9ng.<\/li>\n<\/ul>\n\n\n\n
        Th\u1ebf c\u00f2n \u0111o\u1ea1n m\u00e3 b\u00ean d\u01b0\u1edbi \u0111\u00e2y c\u00f3 nhi\u1ec7m v\u1ee5 g\u00ec?<\/p>\n\n\n\n
            while (count($left) > $i) {\n        $result[] = $left[$i];\n        $i++;\n    }\n\n    while (count($right) > $j) {\n        $result[] = $right[$j];\n        $j++;\n    }<\/code><\/pre>\n\n\n\n
        N\u00f3 \u0111\u01b0\u1ee3c d\u00f9ng \u0111\u1ec3 d\u1ef1 ph\u00f2ng n\u1ebfu m\u1ea3ng c\u00f3 l\u1ebb ph\u1ea7n t\u1eed, th\u00ec ph\u1ea7n t\u1eed cu\u1ed1i s\u1ebd v\u1eabn \u0111\u01b0\u1ee3c \u0111\u01b0a v\u00e0o m\u1ea3ng, v\u00ec ph\u1ea7n t\u1eed n\u00e0y ch\u01b0a \u0111\u01b0\u1ee3c \u0111\u01b0a v\u00e0o trong qu\u00e1 tr\u00ecnh so s\u00e1nh c\u1eb7p \u0111\u00f4i.<\/p>\n\n\n\n
        Trong \u0111\u1ec7 quy, lu\u00f4n c\u00f3 \u0111i\u1ec1u ki\u1ec7n k\u1ebft th\u00fac \u0111\u1ec7 quy. V\u1edbi thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n n\u00f3 ch\u00ednh l\u00e0 \u0111o\u1ea1n m\u00e3 n\u00e0y: if ($len <= 1) return $arr;<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"
        Thu\u1eadt to\u00e1n ti\u1ebfp theo m\u00e0 ch\u00fang ta s\u1ebd c\u00f9ng t\u00ecm hi\u1ec3u sau khi \u0111i qua 2 thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp n\u1ed5i b\u1ecdt (bubble sort) v\u00e0 s\u1eafp x\u1ebfp nhanh (quick sort) l\u00e0 s\u1eafp x\u1ebfp tr\u1ed9n (merge sort). S\u1eafp x\u1ebfp tr\u1ed9n c\u00f3 nhi\u1ec1u \u0111i\u1ec3m t\u01b0\u01a1ng \u0111\u1ed3ng v\u1edbi s\u1eafp x\u1ebfp nhanh, khi n\u00f3 c\u0169ng s\u1eed d\u1ee5ng \u0111\u1ec7 quy …<\/p>\n","protected":false},"author":1,"featured_media":24649,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[333],"tags":[334],"yoast_head":"\nThu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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] • Ki\u1ebfn c\u00e0ng<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/kiencang.net\/thuat-toan-merge-sort\/\" \/>\n<meta property=\"og:locale\" content=\"vi_VN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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] • Ki\u1ebfn c\u00e0ng\" \/>\n<meta property=\"og:description\" content=\"Thu\u1eadt to\u00e1n ti\u1ebfp theo m\u00e0 ch\u00fang ta s\u1ebd c\u00f9ng t\u00ecm hi\u1ec3u sau khi \u0111i qua 2 thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp n\u1ed5i b\u1ecdt (bubble sort) v\u00e0 s\u1eafp x\u1ebfp nhanh (quick sort) l\u00e0 s\u1eafp x\u1ebfp tr\u1ed9n (merge sort). S\u1eafp x\u1ebfp tr\u1ed9n c\u00f3 nhi\u1ec1u \u0111i\u1ec3m t\u01b0\u01a1ng \u0111\u1ed3ng v\u1edbi s\u1eafp x\u1ebfp nhanh, khi n\u00f3 c\u0169ng s\u1eed d\u1ee5ng \u0111\u1ec7 quy …\" \/>\n<meta property=\"og:url\" content=\"https:\/\/kiencang.net\/thuat-toan-merge-sort\/\" \/>\n<meta property=\"og:site_name\" content=\"Ki\u1ebfn c\u00e0ng\" \/>\n<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/anhducnguyen87\/\" \/>\n<meta property=\"article:published_time\" content=\"2023-01-27T15:01:40+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-08-26T11:38:39+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/kiencang.net\/wp-content\/uploads\/2023\/01\/sap-xep-tron.png\" \/>\n\t<meta property=\"og:image:width\" content=\"618\" \/>\n\t<meta property=\"og:image:height\" content=\"595\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Nguy\u1ec5n \u0110\u1ee9c Anh\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u0110\u01b0\u1ee3c vi\u1ebft b\u1edfi\" \/>\n\t<meta name=\"twitter:data1\" content=\"Nguy\u1ec5n \u0110\u1ee9c Anh\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u01af\u1edbc t\u00ednh th\u1eddi gian \u0111\u1ecdc\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 ph\u00fat\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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] • Ki\u1ebfn c\u00e0ng","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/","og_locale":"vi_VN","og_type":"article","og_title":"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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] • Ki\u1ebfn c\u00e0ng","og_description":"Thu\u1eadt to\u00e1n ti\u1ebfp theo m\u00e0 ch\u00fang ta s\u1ebd c\u00f9ng t\u00ecm hi\u1ec3u sau khi \u0111i qua 2 thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp n\u1ed5i b\u1ecdt (bubble sort) v\u00e0 s\u1eafp x\u1ebfp nhanh (quick sort) l\u00e0 s\u1eafp x\u1ebfp tr\u1ed9n (merge sort). S\u1eafp x\u1ebfp tr\u1ed9n c\u00f3 nhi\u1ec1u \u0111i\u1ec3m t\u01b0\u01a1ng \u0111\u1ed3ng v\u1edbi s\u1eafp x\u1ebfp nhanh, khi n\u00f3 c\u0169ng s\u1eed d\u1ee5ng \u0111\u1ec7 quy …","og_url":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/","og_site_name":"Ki\u1ebfn c\u00e0ng","article_author":"https:\/\/www.facebook.com\/anhducnguyen87\/","article_published_time":"2023-01-27T15:01:40+00:00","article_modified_time":"2023-08-26T11:38:39+00:00","og_image":[{"width":618,"height":595,"url":"https:\/\/kiencang.net\/wp-content\/uploads\/2023\/01\/sap-xep-tron.png","type":"image\/png"}],"author":"Nguy\u1ec5n \u0110\u1ee9c Anh","twitter_card":"summary_large_image","twitter_misc":{"\u0110\u01b0\u1ee3c vi\u1ebft b\u1edfi":"Nguy\u1ec5n \u0110\u1ee9c Anh","\u01af\u1edbc t\u00ednh th\u1eddi gian \u0111\u1ecdc":"4 ph\u00fat"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/","url":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/","name":"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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] • Ki\u1ebfn c\u00e0ng","isPartOf":{"@id":"https:\/\/kiencang.net\/#website"},"datePublished":"2023-01-27T15:01:40+00:00","dateModified":"2023-08-26T11:38:39+00:00","author":{"@id":"https:\/\/kiencang.net\/#\/schema\/person\/5e7e1a04d8d1218ad8c421ba43d25c16"},"breadcrumb":{"@id":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/#breadcrumb"},"inLanguage":"vi","potentialAction":[{"@type":"ReadAction","target":["https:\/\/kiencang.net\/thuat-toan-merge-sort\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/kiencang.net\/thuat-toan-merge-sort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/kiencang.net\/"},{"@type":"ListItem","position":2,"name":"Thu\u1eadt to\u00e1n s\u1eafp x\u1ebfp tr\u1ed9n (merge 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]"}]},{"@type":"WebSite","@id":"https:\/\/kiencang.net\/#website","url":"https:\/\/kiencang.net\/","name":"Ki\u1ebfn c\u00e0ng","description":"\u00d4m l\u00fd thuy\u1ebft, h\u00f4n th\u1ef1c h\u00e0nh","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/kiencang.net\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"vi"},{"@type":"Person","@id":"https:\/\/kiencang.net\/#\/schema\/person\/5e7e1a04d8d1218ad8c421ba43d25c16","name":"Nguy\u1ec5n \u0110\u1ee9c Anh","image":{"@type":"ImageObject","inLanguage":"vi","@id":"https:\/\/kiencang.net\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/6d71f9b89393952a8382e30dad26c1ec?s=96&d=monsterid&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/6d71f9b89393952a8382e30dad26c1ec?s=96&d=monsterid&r=g","caption":"Nguy\u1ec5n \u0110\u1ee9c Anh"},"description":"Sinh n\u0103m 1987, t\u1ed1t nghi\u1ec7p Cao \u0111\u1eb3ng th\u1ef1c h\u00e0nh FPT qu\u00e3ng 2014, chuy\u00ean ng\u00e0nh Thi\u1ebft k\u1ebf website. T\u00f4i th\u00edch Content, SEO, Ads, T\u0103ng t\u1ed1c website v\u00e0 Th\u01b0\u01a1ng m\u1ea1i \u0111i\u1ec7n t\u1eed. B\u00ean c\u1ea1nh b\u00e0i t\u1ef1 vi\u1ebft, t\u00f4i c\u0169ng d\u1ecbch nhi\u1ec1u n\u1ed9i dung th\u00fa v\u1ecb c\u1ee7a c\u00e1c t\u00e1c gi\u1ea3 kh\u00e1c nhau. FB c\u00e1 nh\u00e2n: facebook.com\/anhducnguyen87. Email li\u00ean h\u1ec7: guiemailchotoi@gmail.com","sameAs":["https:\/\/www.facebook.com\/anhducnguyen87\/"],"url":"https:\/\/kiencang.net\/author\/admin\/"}]}},"_links":{"self":[{"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/posts\/23518"}],"collection":[{"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/comments?post=23518"}],"version-history":[{"count":3,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/posts\/23518\/revisions"}],"predecessor-version":[{"id":23560,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/posts\/23518\/revisions\/23560"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/media\/24649"}],"wp:attachment":[{"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/media?parent=23518"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/categories?post=23518"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kiencang.net\/wp-json\/wp\/v2\/tags?post=23518"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}