{"id":3626,"date":"2023-01-19T16:33:09","date_gmt":"2023-01-19T08:33:09","guid":{"rendered":"https:\/\/qaqaq.top\/?p=3626"},"modified":"2023-01-19T16:33:09","modified_gmt":"2023-01-19T08:33:09","slug":"%e5%bf%ab%e9%80%9f%e6%8e%92%e5%ba%8f-2","status":"publish","type":"post","link":"https:\/\/qaqaq.top\/?p=3626","title":{"rendered":"\u5feb\u901f\u6392\u5e8f"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>package chapter4.part3;\r\n\r\n\/**\r\n * Created by weimengshu on 2018\/7\/13.\r\n *\/\r\nimport java.util.Arrays;\r\n\r\npublic class QuickSort {\r\n\r\n    public static void quickSort(int&#91;] arr, int startIndex, int endIndex) {\r\n        \/\/ \u9012\u5f52\u7ed3\u675f\u6761\u4ef6\uff1astartIndex\u5927\u7b49\u4e8eendIndex\u7684\u65f6\u5019\r\n        if (startIndex >= endIndex) {\r\n            return;\r\n        }\r\n        \/\/ \u5f97\u5230\u57fa\u51c6\u5143\u7d20\u4f4d\u7f6e\r\n        int pivotIndex = partition(arr, startIndex, endIndex);\r\n        \/\/ \u6839\u636e\u57fa\u51c6\u5143\u7d20\uff0c\u5206\u6210\u4e24\u90e8\u5206\u9012\u5f52\u6392\u5e8f\r\n        quickSort(arr, startIndex, pivotIndex - 1);\r\n        quickSort(arr, pivotIndex + 1, endIndex);\r\n    }\r\n\r\n    \/**\r\n     * \u5206\u6cbb\uff08\u53cc\u8fb9\u5faa\u73af\u6cd5\uff09\r\n     * @param arr     \u5f85\u4ea4\u6362\u7684\u6570\u7ec4\r\n     * @param startIndex    \u8d77\u59cb\u4e0b\u6807\r\n     * @param endIndex    \u7ed3\u675f\u4e0b\u6807\r\n     *\/\r\n    private static int partition(int&#91;] arr, int startIndex, int endIndex) {\r\n        \/\/ \u53d6\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\u7684\u5143\u7d20\u4f5c\u4e3a\u57fa\u51c6\u5143\u7d20\uff08\u4e5f\u53ef\u4ee5\u9009\u62e9\u968f\u673a\u4f4d\u7f6e\uff09\r\n        int pivot = arr&#91;startIndex];\r\n        int left = startIndex;\r\n        int right = endIndex;\r\n\r\n        while( left != right) {\r\n            \/\/\u63a7\u5236right\u6307\u9488\u6bd4\u8f83\u5e76\u5de6\u79fb\r\n            while(left&lt;right &amp;&amp; arr&#91;right] > pivot){\r\n                right--;\r\n            }\r\n            \/\/\u63a7\u5236left\u6307\u9488\u6bd4\u8f83\u5e76\u53f3\u79fb\r\n            while( left&lt;right &amp;&amp; arr&#91;left] &lt;= pivot) {\r\n                left++;\r\n            }\r\n            \/\/\u4ea4\u6362left\u548cright\u6307\u5411\u7684\u5143\u7d20\r\n            if(left&lt;right) {\r\n                int p = arr&#91;left];\r\n                arr&#91;left] = arr&#91;right];\r\n                arr&#91;right] = p;\r\n            }\r\n        }\r\n\r\n        \/\/pivot\u548c\u6307\u9488\u91cd\u5408\u70b9\u4ea4\u6362\r\n        arr&#91;startIndex] = arr&#91;left];\r\n        arr&#91;left] = pivot;\r\n\r\n        return left;\r\n    }\r\n\r\n    \/**\r\n     * \u5206\u6cbb\uff08\u5355\u8fb9\u5faa\u73af\u6cd5\uff09\r\n     * @param arr     \u5f85\u4ea4\u6362\u7684\u6570\u7ec4\r\n     * @param startIndex    \u8d77\u59cb\u4e0b\u6807\r\n     * @param endIndex    \u7ed3\u675f\u4e0b\u6807\r\n     *\/\r\n    private static int partitionV2(int&#91;] arr, int startIndex, int endIndex) {\r\n        \/\/ \u53d6\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\u7684\u5143\u7d20\u4f5c\u4e3a\u57fa\u51c6\u5143\u7d20\uff08\u4e5f\u53ef\u4ee5\u9009\u62e9\u968f\u673a\u4f4d\u7f6e\uff09\r\n        int pivot = arr&#91;startIndex];\r\n        int mark = startIndex;\r\n\r\n        for(int i=startIndex+1; i&lt;=endIndex; i++){\r\n            if(arr&#91;i]&lt;pivot){\r\n                mark ++;\r\n                int p = arr&#91;mark];\r\n                arr&#91;mark] = arr&#91;i];\r\n                arr&#91;i] = p;\r\n            }\r\n        }\r\n\r\n        arr&#91;startIndex] = arr&#91;mark];\r\n        arr&#91;mark] = pivot;\r\n        return mark;\r\n    }\r\n\r\n    public static void main(String&#91;] args) {\r\n        int&#91;] arr = new int&#91;] {4,4,6,5,3,2,8,1};\r\n        quickSort(arr, 0, arr.length-1);\r\n        System.out.println(Arrays.toString(arr));\r\n    }\r\n}\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82],"tags":[133],"class_list":["post-3626","post","type-post","status-publish","format-standard","hentry","category-82","tag-133"],"_links":{"self":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/3626"}],"collection":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3626"}],"version-history":[{"count":1,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/3626\/revisions"}],"predecessor-version":[{"id":3627,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/3626\/revisions\/3627"}],"wp:attachment":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}