好程序員Java學(xué)習(xí)路線分享5分鐘了解計(jì)數(shù)排序

好程序員Java學(xué)習(xí)路線分享5分鐘了解計(jì)數(shù)排序，前言：計(jì)數(shù)排序是一種非比較性質(zhì)的排序算法，計(jì)數(shù)排序借助輔助空間記錄每個(gè)元素出現(xiàn)的次數(shù)，根據(jù)次數(shù)確定每一個(gè)元素最終的位置。
計(jì)數(shù)排序思想介紹
1根據(jù)待排序數(shù)組，獲取最大值和最小值，得到所有元素的范圍 [m,n]
2新建一個(gè)長度為n-m+1的臨時(shí)數(shù)組
3遍歷待排序數(shù)組，元素的值-m作為臨時(shí)數(shù)組下標(biāo)，該下標(biāo)位置記錄元素出現(xiàn)次數(shù)
4遍歷結(jié)束，臨時(shí)數(shù)組就存儲了每個(gè)元素出現(xiàn)的次數(shù)
5根據(jù)該臨時(shí)數(shù)組，最終得到排序后元素

算法說明：
待排序數(shù)據(jù)：12，4，6，7，4，6
數(shù)據(jù)范圍為[4,12],臨時(shí)數(shù)組長度為12-4+1=9

最終得到排序后序列：4，4，6，6，7，12
計(jì)數(shù)排序的代碼實(shí)現(xiàn)
1.public?static?void?sortCount(int[]?arr)?{??
2.????????int?max?=?0;??
3.????????int?min?=?0;??
4.????????//?獲取數(shù)組的最大值和最小值??
5.????????for(int?i?=?0;?i?<?arr.length;?i++){??
6.????????????max?=?Math.max(max,?arr[i]);??
7.????????????min?=?Math.min(min,?arr[i]);??
8.????????}??
9.????????int?len?=?arr.length;??
10.????????//?創(chuàng)建臨時(shí)數(shù)組??
11.????????int[]?temp?=?new?int[max?-?min?+?1];??
12.????????//?計(jì)數(shù)??
13.????????for(int?i?=?0;?i?<?len;?i++)?{??
14.????????????temp[arr[i]?-?min]?+=?1;??
15.????????}??
16.????????//?將臨時(shí)數(shù)組中數(shù)據(jù)依次放回原數(shù)組??
17.????????for(int?i?=?0,?index?=?0;?i?<?temp.length;?i++)?{??
18.????????????int?item?=?temp[i];??
19.????????????while(item--?!=?0)?{??
20.????????????????arr[index++]?=?i?+?min;??
21.????????????}??
22.????????}??
23.????}??

總結(jié)
計(jì)數(shù)排序需要占用額外的存儲空間，它比較適用于數(shù)據(jù)比較集中的情況。