Java排序算法之計數(shù)排序解析
Java計數(shù)排序解析
原理：找到數(shù)組中數(shù)值最大的元素，（如這里的8），創(chuàng)建一個長度為最大元素+1的臨時數(shù)組，（這里為9），這樣就可以把原始數(shù)組轉(zhuǎn)換為： 以原始數(shù)組元素值為下標(biāo)，相同元素個數(shù)為值的臨時數(shù)組 如數(shù)組 [8,4,2,3,5] 經(jīng)過轉(zhuǎn)換后形成了 [0,0,1,1,1,1,0,0,1] 的數(shù)組，如下圖：
但是在一些情況下，這樣創(chuàng)建數(shù)組是不合適的，如[90,96,92,93,95] ，這就需要創(chuàng)建一個長度為97的數(shù)組，而這個數(shù)組前90個位置就被浪費(fèi)了，所以可以進(jìn)行優(yōu)化
優(yōu)化：用數(shù)組的最大值減去最小值，創(chuàng)建一個長度為差值+1的數(shù)組，保存每個元素時保存相對大小，如上面這個數(shù)組，差值為8-2=6，創(chuàng)建一個長度為7的數(shù)組，用每個元素減去最小值，然后用結(jié)果去轉(zhuǎn)換為下面的數(shù)組
代碼實現(xiàn)（java）：
//測試
public static void main(String[] args) {
int[] arr = {8,4,2,2,3,3,5};
countSort(arr);
}
public static void countSort(int[] arr){
//1.取出數(shù)組中的最大值和最小值
int max = arr[0];
int min = arr[0];
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
//最大值和最小值的差值
int len = max - min;
//創(chuàng)建差值+1長度的臨時數(shù)組
int[] tmp = new int[len + 1];
//遍歷原數(shù)組，將（元素-最小值）作為下標(biāo)，元素個數(shù)為value，插入到臨時數(shù)組
for (int i : arr) {
tmp[i-min] ++;
}
//遍歷臨時數(shù)組，每個下標(biāo)為值，元素值為次數(shù)，依次打印
for (int i = 0; i < tmp.length; i++) {
for (int j = i; j < tmp[i]+i; j++) {
System.out.println(j + min);
}
}
}到此這篇關(guān)于Java排序算法之計數(shù)排序解析的文章就介紹到這了,更多相關(guān)Java計數(shù)排序解析內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本篇文章主要介紹了JAVA如何獲取客戶端IP地址和MAC地址非常具有實用價值，這里整理了詳細(xì)的代碼，需要的朋友可以參考下2017-08-08
Java8?API添加了一個新的抽象稱為流Stream,可以讓你以一種聲明的方式處理數(shù)據(jù),下面這篇文章主要給大家介紹了關(guān)于Java8?Stream流的常用方法,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-07-07
ZooKeeper是一種分布式、高可用性的協(xié)調(diào)服務(wù),主要用于幫助系統(tǒng)避免單點(diǎn)故障和建立可靠的應(yīng)用程序,它通過Leader、Follower和Observer的角色來協(xié)調(diào)節(jié)點(diǎn),并提供分布式協(xié)作服務(wù)和維護(hù)配置信息,ZooKeeper在HDFS、YARN、HBase、SmallFS和Kafka等大數(shù)據(jù)產(chǎn)品中都有廣泛的應(yīng)用2025-02-02
這篇文章主要介紹了Spring常用配置及解析類說明，涉及Spring常用配置項的方法以及它的解析類等相關(guān)內(nèi)容，具有一定參考價值，需要的朋友可以了解下。2017-11-11
Spring AOP面向切面編程實現(xiàn)原理方法詳解
這篇文章主要介紹了Spring AOP面向切面編程實現(xiàn)原理方法詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08
一文詳解SpringBoot如何優(yōu)雅地實現(xiàn)異步調(diào)用
SpringBoot想必大家都用過，但是大家平時使用發(fā)布的接口大都是同步的，那么你知道如何優(yōu)雅的實現(xiàn)異步呢？這篇文章就來和大家詳細(xì)聊聊2023-03-03
SpringBoot文件上傳接口并發(fā)性能調(diào)優(yōu)
在一個項目現(xiàn)場,文件上傳接口(文件500K)QPS只有30,這個并發(fā)性能確實堪憂,此文記錄出坑過程,文中通過代碼示例講解的非常詳細(xì),具有一定的參考價值,需要的朋友可以參考下2024-06-06
springboot中如何使用openfeign進(jìn)行接口調(diào)用
這篇文章主要介紹了springboot中如何使用openfeign進(jìn)行接口調(diào)用問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-07-07
下面小編就為大家?guī)硪黄猈indows中Tomcat整合到Eclipse的圖文教程。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
java組件commons-fileupload實現(xiàn)文件上傳、下載、在線打開
這篇文章主要介紹了java組件commons-fileupload實現(xiàn)文件上傳、下載、在線打開,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-10-10