{"id":8060,"date":"2024-04-21T07:01:01","date_gmt":"2024-04-20T23:01:01","guid":{"rendered":""},"modified":"2024-04-21T07:01:01","modified_gmt":"2024-04-20T23:01:01","slug":"Quick Select Algorithm \u5feb\u901f\u9009\u62e9\u7b97\u6cd5","status":"publish","type":"post","link":"https:\/\/mushiming.com\/8060.html","title":{"rendered":"Quick Select Algorithm \u5feb\u901f\u9009\u62e9\u7b97\u6cd5"},"content":{"rendered":"<p><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"display: none;\"> \n <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path> \n<\/svg> <\/p>\n<blockquote>\n<p>\u66f4\u591a\u4ee3\u7801\u548cLeetcode\u9898\u76ee\u89e3\u6790\u8bf7\u770b\u8fd9\u91cc<\/p>\n<\/blockquote>\n<h3 id=\"\u4ec0\u4e48\u662fquick-select\">\u4ec0\u4e48\u662f<em>Quick select<\/em>?<\/h3>\n<ul>\n<li><code>Quick select<\/code>\u7b97\u6cd5\u901a\u5e38\u7528\u6765\u5728\u672a\u6392\u5e8f\u7684\u6570\u7ec4\u4e2d\u5bfb\u627e\u7b2ck\u5c0f\/\u7b2ck\u5927\u7684\u5143\u7d20\u3002\u5176\u65b9\u6cd5\u7c7b\u4f3c\u4e8e<code>Quick sort<\/code>\u3002<code>Quick select<\/code>\u548c<code>Quick sort<\/code>\u90fd\u662f\u7531Tony Hoare\u53d1\u660e\u7684\uff0c\u56e0\u6b64<code>Quick select<\/code>\u7b97\u6cd5\u4e5f\u88ab\u79f0\u4e3a\u662f<code>Hoare's selection algorithm<\/code>\u3002 <\/li>\n<li><code>Quick select<\/code>\u7b97\u6cd5\u56e0\u5176\u9ad8\u6548\u548c\u826f\u597d\u7684average case\u65f6\u95f4\u590d\u6742\u5ea6\u800c\u88ab\u5e7f\u4e3a\u5e94\u7528\u3002<code>Quick select<\/code>\u7684average case\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(n)<\/code>\uff0c\u7136\u800c\u5176worst case\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(n^2)<\/code>\u3002 <\/li>\n<li>\u603b\u4f53\u800c\u8a00\uff0c<code>Quick select<\/code>\u91c7\u7528\u548c<code>Quick sort<\/code>\u7c7b\u4f3c\u7684\u6b65\u9aa4\u3002\u9996\u5148\u9009\u5b9a\u4e00\u4e2a<code>pivot<\/code>\uff0c\u7136\u540e\u6839\u636e\u6bcf\u4e2a\u6570\u5b57\u4e0e\u8be5<code>pivot<\/code>\u7684\u5927\u5c0f\u5173\u7cfb\u5c06\u6574\u4e2a\u6570\u7ec4\u5206\u4e3a\u4e24\u90e8\u5206\u3002\u90a3\u4e48\u4e0e<code>Quick sort<\/code>\u4e0d\u540c\u7684\u662f\uff0c<code>Quick select<\/code>\u53ea\u8003\u8651\u6240\u5bfb\u627e\u7684\u76ee\u6807\u6240\u5728\u7684\u90a3\u4e00\u90e8\u5206\u5b50\u6570\u7ec4\uff0c\u800c\u975e\u50cf<code>Quick sort<\/code>\u4e00\u6837\u5206\u522b\u518d\u5bf9\u4e24\u8fb9\u8fdb\u884c\u5206\u5272\u3002\u6b63\u662f\u56e0\u4e3a\u5982\u6b64\uff0c<code>Quick select<\/code>\u5c06\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6\u4ece<code>O(nlogn)<\/code>\u964d\u5230\u4e86<code>O(n)<\/code>\u3002<\/li>\n<\/ul>\n<h3 id=\"quick-select\u7b97\u6cd5\u63cf\u8ff0\"><em>Quick select<\/em>\u7b97\u6cd5\u63cf\u8ff0<\/h3>\n<p><strong>Input: array nums, int k. (find kth smallest element in an unsorted array)<\/strong> <br \/> <strong>Output: int target<\/strong> <\/p>\n<blockquote>\n<ol>\n<li>Choose an element from the array as pivot, exchange the position of pivot and number at the end of the array. <br \/> \n<ul>\n<li><em>The<\/em><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"Quick Select Algorithm \u5feb\u901f\u9009\u62e9\u7b97\u6cd5\u4ec0\u4e48\u662fQuickselect?Quickselect\u7b97\u6cd5\u901a\u5e38\u7528\u6765\u5728\u672a\u6392\u5e8f\u7684\u6570\u7ec4\u4e2d\u5bfb\u627e\u7b2ck\u5c0f\/\u7b2ck\u5927\u7684\u5143\u7d20","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/8060"}],"collection":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/comments?post=8060"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/8060\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=8060"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=8060"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=8060"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}