{"id":3632,"date":"2023-01-19T16:34:47","date_gmt":"2023-01-19T08:34:47","guid":{"rendered":"https:\/\/qaqaq.top\/?p=3632"},"modified":"2023-01-19T16:34:48","modified_gmt":"2023-01-19T08:34:48","slug":"%e8%ae%a1%e6%95%b0%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/qaqaq.top\/?p=3632","title":{"rendered":"\u8ba1\u6570\u6392\u5e8f"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>package chapter4.part5;\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 CountSort {\r\n\r\n    public static int&#91;] countSort(int&#91;] array) {\r\n        \/\/1.\u5f97\u5230\u6570\u5217\u7684\u6700\u5927\u503c\r\n        int max = array&#91;0];\r\n        for(int i=1; i&lt;array.length; i++){\r\n            if(array&#91;i] > max){\r\n                max = array&#91;i];\r\n            }\r\n        }\r\n        \/\/2.\u6839\u636e\u6570\u5217\u6700\u5927\u503c\u786e\u5b9a\u7edf\u8ba1\u6570\u7ec4\u7684\u957f\u5ea6\r\n        int&#91;] countArray = new int&#91;max+1];\r\n        \/\/3.\u904d\u5386\u6570\u5217\uff0c\u586b\u5145\u7edf\u8ba1\u6570\u7ec4\r\n        for(int i=0; i&lt;array.length; i++){\r\n            countArray&#91;array&#91;i]]++;\r\n        }\r\n        \/\/4.\u904d\u5386\u7edf\u8ba1\u6570\u7ec4\uff0c\u8f93\u51fa\u7ed3\u679c\r\n        int index = 0;\r\n        int&#91;] sortedArray = new int&#91;array.length];\r\n        for(int i=0; i&lt;countArray.length; i++){\r\n            for(int j=0; j&lt;countArray&#91;i]; j++){\r\n                sortedArray&#91;index++] = i;\r\n            }\r\n        }\r\n        return sortedArray;\r\n    }\r\n\r\n    public static int&#91;] countSortV2(int&#91;] array) {\r\n        \/\/1.\u5f97\u5230\u6570\u5217\u7684\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\uff0c\u5e76\u7b97\u51fa\u5dee\u503cd\r\n        int max = array&#91;0];\r\n        int min = array&#91;0];\r\n        for(int i=1; i&lt;array.length; i++) {\r\n            if(array&#91;i] > max) {\r\n                max = array&#91;i];\r\n            }\r\n            if(array&#91;i] &lt; min) {\r\n                min = array&#91;i];\r\n            }\r\n        }\r\n        int d = max - min;\r\n        \/\/2.\u521b\u5efa\u7edf\u8ba1\u6570\u7ec4\u5e76\u7edf\u8ba1\u5bf9\u5e94\u5143\u7d20\u4e2a\u6570\r\n        int&#91;] countArray = new int&#91;d+1];\r\n        for(int i=0; i&lt;array.length; i++) {\r\n            countArray&#91;array&#91;i]-min]++;\r\n        }\r\n        \/\/3.\u7edf\u8ba1\u6570\u7ec4\u505a\u53d8\u5f62\uff0c\u540e\u9762\u7684\u5143\u7d20\u7b49\u4e8e\u524d\u9762\u7684\u5143\u7d20\u4e4b\u548c\r\n        for(int i=1;i&lt;countArray.length;i++) {\r\n            countArray&#91;i] += countArray&#91;i-1];\r\n        }\r\n        \/\/4.\u5012\u5e8f\u904d\u5386\u539f\u59cb\u6570\u5217\uff0c\u4ece\u7edf\u8ba1\u6570\u7ec4\u627e\u5230\u6b63\u786e\u4f4d\u7f6e\uff0c\u8f93\u51fa\u5230\u7ed3\u679c\u6570\u7ec4\r\n        int&#91;] sortedArray = new int&#91;array.length];\r\n        for(int i=array.length-1;i>=0;i--) {\r\n            sortedArray&#91;countArray&#91;array&#91;i]-min]-1]=array&#91;i];\r\n            countArray&#91;array&#91;i]-min]--;\r\n        }\r\n        return sortedArray;\r\n    }\r\n\r\n    public static void main(String&#91;] args) {\r\n        int&#91;] array = new int&#91;] {4,4,6,5,3,2,8,1,7,5,6,0,10};\r\n        int&#91;] sortedArray = countSort(array);\r\n        System.out.println(Arrays.toString(sortedArray));\r\n\r\n        array = new int&#91;] {95,94,91,98,99,90,99,93,91,92};\r\n        sortedArray = countSort(array);\r\n        System.out.println(Arrays.toString(sortedArray));\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-3632","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\/3632"}],"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=3632"}],"version-history":[{"count":1,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/3632\/revisions"}],"predecessor-version":[{"id":3633,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/3632\/revisions\/3633"}],"wp:attachment":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}