{"id":5476,"date":"2023-01-05T12:44:25","date_gmt":"2023-01-05T04:44:25","guid":{"rendered":"https:\/\/badgameshow.com\/steven\/?p=5476"},"modified":"2023-01-05T12:44:25","modified_gmt":"2023-01-05T04:44:25","slug":"%e5%ad%b8%e7%bf%92typescript%e4%b8%ad%e7%9a%84%e5%a0%86%e6%8e%92%e5%ba%8f%ef%bc%88heapsort%ef%bc%89","status":"publish","type":"post","link":"https:\/\/badgameshow.com\/steven\/typescript\/%e5%ad%b8%e7%bf%92typescript%e4%b8%ad%e7%9a%84%e5%a0%86%e6%8e%92%e5%ba%8f%ef%bc%88heapsort%ef%bc%89\/","title":{"rendered":"\u5b78\u7fd2TypeScript\u4e2d\u7684\u5806\u6392\u5e8f\uff08HeapSort\uff09"},"content":{"rendered":"

<\/p>\n

TypeScript \u9663\u5217\u7684\u5806\u6392\u5e8f(heapSort)<\/h1>\n

\u5806\u6392\u5e8f(heapSort)\u662f\u4e00\u7a2e\u6f14\u7b97\u6cd5\uff0c\u5b83\u5229\u7528\u4e86\u5806\u7a4d\u7684\u7279\u6027\uff0c\u5c07\u8cc7\u6599\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u9032\u884c\u6392\u5e8f\u3002\u5806\u6392\u5e8f\u662f\u4e00\u7a2e\u4e0d\u7a69\u5b9a\u7684\u6392\u5e8f\u6f14\u7b97\u6cd5\uff0c\u5b83\u7684\u6642\u9593\u8907\u96dc\u5ea6\u70baO(nlogn)\u3002\u5728TypeScript\u4e2d\uff0c\u53ef\u4ee5\u4f7f\u7528\u5806\u6392\u5e8f\u4f86\u5c0d\u9663\u5217\u9032\u884c\u6392\u5e8f\u3002<\/p>\n

\u5806\u6392\u5e8f\u7684\u6b65\u9a5f<\/h2>\n

\u5806\u6392\u5e8f\u7684\u6b65\u9a5f\u5982\u4e0b\uff1a<\/p>\n

    \n
  1. \u5c07\u8cc7\u6599\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u653e\u5165\u5806\u7a4d\u4e2d\u3002<\/li>\n
  2. \u5c07\u5806\u7a4d\u7684\u6839\u7bc0\u9ede\u8207\u6700\u5f8c\u4e00\u500b\u7bc0\u9ede\u4ea4\u63db\uff0c\u7136\u5f8c\u5c07\u5806\u7a4d\u7684\u5927\u5c0f\u6e1b1\uff0c\u9019\u6a23\u6700\u5f8c\u4e00\u500b\u7bc0\u9ede\u5c31\u662f\u6700\u5927\u7684\u5143\u7d20\u3002<\/li>\n
  3. \u91cd\u65b0\u8abf\u6574\u5806\u7a4d\uff0c\u4f7f\u5176\u6eff\u8db3\u5806\u7a4d\u7684\u6027\u8cea\u3002<\/li>\n
  4. \u91cd\u8907\u6b65\u9a5f2\u548c\u6b65\u9a5f3\uff0c\u76f4\u5230\u5806\u7a4d\u7684\u5927\u5c0f\u70ba1\u3002<\/li>\n<\/ol>\n

    TypeScript \u4e2d\u7684\u5806\u6392\u5e8f\u7a0b\u5f0f\u78bc<\/h2>\n

    \u4ee5\u4e0b\u662fTypeScript\u4e2d\u7684\u5806\u6392\u5e8f\u7a0b\u5f0f\u78bc\uff1a<\/p>\n

    \n\/\/ \u5c07\u8cc7\u6599\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u653e\u5165\u5806\u7a4d\u4e2d\nfunction heapify(arr: number[], n: number, i: number): void {\n    let largest = i;\n    let l = 2 * i + 1;\n    let r = 2 * i + 2;\n\n    \/\/ \u5982\u679c\u5de6\u5b50\u7bc0\u9ede\u6bd4\u6839\u7bc0\u9ede\u5927\uff0c\u5247\u5c07\u6700\u5927\u503c\u66f4\u65b0\u70ba\u5de6\u5b50\u7bc0\u9ede\n    if (l < n && arr[l] > arr[largest]) {\n        largest = l;\n    }\n\n    \/\/ \u5982\u679c\u53f3\u5b50\u7bc0\u9ede\u6bd4\u6839\u7bc0\u9ede\u5927\uff0c\u5247\u5c07\u6700\u5927\u503c\u66f4\u65b0\u70ba\u53f3\u5b50\u7bc0\u9ede\n    if (r < n && arr[r] > arr[largest]) {\n        largest = r;\n    }\n\n    \/\/ \u5982\u679c\u6700\u5927\u503c\u4e0d\u7b49\u65bc\u6839\u7bc0\u9ede\uff0c\u5247\u5c07\u6839\u7bc0\u9ede\u548c\u6700\u5927\u503c\u4ea4\u63db\n    if (largest != i) {\n        let temp = arr[i];\n        arr[i] = arr[largest];\n        arr[largest] = temp;\n\n        \/\/ \u4ea4\u63db\u5f8c\uff0c\u91cd\u65b0\u8abf\u6574\u5806\u7a4d\n        heapify(arr, n, largest);\n    }\n}\n\n\/\/ \u5806\u6392\u5e8f\nfunction heapSort(arr: number[]): void {\n    let n = arr.length;\n\n    \/\/ \u5c07\u8cc7\u6599\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u653e\u5165\u5806\u7a4d\u4e2d\n    for (let i = Math.floor(n \/ 2) - 1; i >= 0; i--) {\n        heapify(arr, n, i);\n    }\n\n    \/\/ \u5c07\u5806\u7a4d\u7684\u6839\u7bc0\u9ede\u8207\u6700\u5f8c\u4e00\u500b\u7bc0\u9ede\u4ea4\u63db\uff0c\u7136\u5f8c\u5c07\u5806\u7a4d\u7684\u5927\u5c0f\u6e1b1\n    for (let i = n - 1; i > 0; i--) {\n        let temp = arr[0];\n        arr[0] = arr[i];\n        arr[i] = temp;\n\n        \/\/ \u91cd\u65b0\u8abf\u6574\u5806\u7a4d\n        heapify(arr, i, 0);\n    }\n}\n\n\/\/ \u6e2c\u8a66\nlet arr = [3, 5, 2, 4, 1];\nheapSort(arr);\nconsole.log(arr); \/\/ [1, 2, 3, 4, 5]\n<\/pre>\n
    \u5728\u4e0a\u9762\u7684\u7a0b\u5f0f\u78bc\u4e2d\uff0c\u6211\u5011\u9996\u5148\u4f7f\u7528heapify()<\/code>\u51fd\u6578\u5c07\u8cc7\u6599\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u653e\u5165\u5806\u7a4d\u4e2d\uff0c\u7136\u5f8c\u4f7f\u7528heapSort()<\/code>\u51fd\u6578\u5c0d\u5806\u7a4d\u9032\u884c\u6392\u5e8f\u3002<\/p>\n
    <\/p>\n
    \u5806\u6392\u5e8f\u7684\u512a\u9ede<\/h2>\n
    \u5806\u6392\u5e8f\u6709\u4ee5\u4e0b\u512a\u9ede\uff1a<\/p>\n
      \n
    • \u6642\u9593\u8907\u96dc\u5ea6\u4f4e<\/strong>\uff1a\u5806\u6392\u5e8f\u7684\u6642\u9593\u8907\u96dc\u5ea6\u70baO(nlogn)\uff0c\u6bd4\u8d77\u5176\u4ed6\u6392\u5e8f\u6f14\u7b97\u6cd5\u7684\u6642\u9593\u8907\u96dc\u5ea6\u8981\u4f4e\u3002<\/li>\n
    • \u4e0d\u9700\u8981\u984d\u5916\u7684\u8a18\u61b6\u9ad4\u7a7a\u9593<\/strong>\uff1a\u5806\u6392\u5e8f\u4e0d\u9700\u8981\u984d\u5916\u7684\u8a18\u61b6\u9ad4\u7a7a\u9593\uff0c\u5b83\u53ea\u9700\u8981\u4e00\u500b\u8f14\u52a9\u8b8a\u6578\u4f86\u4ea4\u63db\u5143\u7d20\u3002<\/li>\n
    • \u7a69\u5b9a\u6027<\/strong>\uff1a\u5806\u6392\u5e8f\u662f\u4e00\u7a2e\u4e0d\u7a69\u5b9a\u7684\u6392\u5e8f\u6f14\u7b97\u6cd5\u3002<\/li>\n<\/ul>\n
      \u7e3d\u7d50<\/h2>\n
      \u5806\u6392\u5e8f\u662f\u4e00\u7a2e\u6f14\u7b97\u6cd5\uff0c\u5b83\u5229\u7528\u4e86\u5806\u7a4d\u7684\u7279\u6027\uff0c\u5c07\u8cc7\u6599\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u9032\u884c\u6392\u5e8f\u3002\u5728TypeScript\u4e2d\uff0c\u53ef\u4ee5\u4f7f\u7528\u5806\u6392\u5e8f\u4f86\u5c0d\u9663\u5217\u9032\u884c\u6392\u5e8f\u3002\u5806\u6392\u5e8f\u7684\u6642\u9593\u8907\u96dc\u5ea6\u70baO(nlogn)\uff0c\u6bd4\u8d77\u5176\u4ed6\u6392\u5e8f\u6f14\u7b97\u6cd5\u7684\u6642\u9593\u8907\u96dc\u5ea6\u8981\u4f4e\uff0c\u800c\u4e14\u5b83\u4e0d\u9700\u8981\u984d\u5916\u7684\u8a18\u61b6\u9ad4\u7a7a\u9593\uff0c\u53ea\u9700\u8981\u4e00\u500b\u8f14\u52a9\u8b8a\u6578\u4f86\u4ea4\u63db\u5143\u7d20\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
      \u6587\u7ae0\u6458\u8981\uff1a\u672c\u6587\u5c07\u4ecb\u7d39TypeScript\u4e2d\u7684\u5806\u6392\u5e8f\uff08HeapSort\uff09\uff0c\u8a73\u7d30\u89e3\u91cb\u5806\u6392\u5e8f\u7684\u539f\u7406\uff0c\u4ee5\u53ca\u5982\u4f55\u4f7f\u7528TypeScript\u5be6\u73fe\u5806\u6392\u5e8f\u3002\u672c\u6587\u5c07\u70ba\u60a8\u63d0\u4f9b\u4e00\u500b\u5b8c\u6574\u7684\u5806\u6392\u5e8f\u7a0b\u5e8f\uff0c\u8b93\u60a8\u53ef\u4ee5\u8f15\u9b06\u5b78\u7fd2\u5806\u6392\u5e8f\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[187],"tags":[186],"class_list":["post-5476","post","type-post","status-publish","format-standard","hentry","category-typescript","tag-typescript"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack-related-posts":[],"jetpack_shortlink":"https:\/\/wp.me\/pcFK27-1qk","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/posts\/5476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/comments?post=5476"}],"version-history":[{"count":1,"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/posts\/5476\/revisions"}],"predecessor-version":[{"id":5477,"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/posts\/5476\/revisions\/5477"}],"wp:attachment":[{"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/media?parent=5476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/categories?post=5476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/badgameshow.com\/steven\/wp-json\/wp\/v2\/tags?post=5476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}