JAVA十大排序算法之計數(shù)排序詳解
計數(shù)排序
一種非比較排序。計數(shù)排序?qū)σ欢ǚ秶鷥?nèi)的整數(shù)排序時候的速度非???,一般快于其他排序算法。但計數(shù)排序局限性比較大,只限于對整數(shù)進(jìn)行排序,而且待排序元素值分布較連續(xù)、跨度小的情況。
如果一個數(shù)組里所有元素都是整數(shù),而且都在0-k以內(nèi)。對于數(shù)組里每個元素來說,如果能知道數(shù)組里有多少項小于或等于該元素,就能準(zhǔn)確地給出該元素在排序后的數(shù)組的位置。
如給定一個0~5范圍內(nèi)的數(shù)組[2,5,3,0,2,3,0,3],對于元素5為其中最大的元素,創(chuàng)建一個大小為(5-0+1 = 6)的計數(shù)數(shù)組,如果原數(shù)組中的值對應(yīng)計數(shù)數(shù)組的下標(biāo),則下標(biāo)對應(yīng)計數(shù)數(shù)組的值加1。
問題
上面是通過數(shù)組的最大值來確定計數(shù)數(shù)組的長度的,但如果需要對學(xué)生的成績進(jìn)行排序,如學(xué)生成績?yōu)椋篬95,93,92,94,92,93,95,90],如果按照上面的方法來處理,則需要一個大小為100的數(shù)組,但是可以看到其中的最小值為90,那也就是說前面 0~89 的位置都沒有數(shù)據(jù)存放,造成了資源浪費。
如果我們知道了數(shù)組的最大值和最小值,則計數(shù)數(shù)組的大小為(最大值 - 最小值 + 1),如上面數(shù)組的最大值為99,最小值為90,則定義計數(shù)數(shù)組的大小為(95 - 90 + 1 = 6)。并且索引分別對應(yīng)原數(shù)組9095的值。我們把090的范圍用一個偏移量來表示,即最小值90就是這個偏移量。
代碼實現(xiàn)
public class CountSort { public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3}; public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90}; //優(yōu)化前 private static int[] sort(int[] array) { if (array.length < 2) return array; //找出數(shù)組的最大值 int max = array[0]; for (int i : array) { if (i > max) { max = i; } } //初始化一個計數(shù)數(shù)組且值為0 int[] countArray = new int[max + 1]; for (int i = 0; i < countArray.length; i++) { countArray[i] = 0; } //填充計數(shù)數(shù)組 for (int temp : array) { countArray[temp]++; } int o_index = 0;//原數(shù)組下標(biāo) int n_index = 0;//計數(shù)數(shù)組下標(biāo) while (o_index < array.length) { //只要計數(shù)數(shù)組的下標(biāo)不為0,就將計數(shù)數(shù)組的值從新寫回原數(shù)組 if (countArray[n_index] != 0) { array[o_index] = n_index;//計數(shù)數(shù)組下標(biāo)對應(yīng)元素組的值 countArray[n_index]--;//計數(shù)數(shù)組的值要-1 o_index++; } else { n_index++;//上一個索引的值為0后開始下一個 } } return array; } //優(yōu)化后 private static int[] sort2(int[] array) { if (array.length < 2) return array; //找出數(shù)組中的最大值和最小值 int min = array[0], max = array[0]; for (int i : array) { if (i > max) { max = i; } if (i < min) { min = i; } } //定義一個偏移量,即最小值前面0~min的范圍,這里直接用一個負(fù)數(shù)來表示 int bias = 0 - min; //初始化一個計數(shù)數(shù)組且值為0 int[] countArray = new int[max - min + 1]; for (int i = 0; i < countArray.length; i++) { countArray[i] = 0; } for (int temp : array) { countArray[temp + bias]++; } //填充計數(shù)數(shù)組 int o_index = 0;//原數(shù)組下標(biāo) int n_index = 0;//計數(shù)數(shù)組下標(biāo) while (o_index < array.length) { if (countArray[n_index] != 0) { array[o_index] = n_index - bias; countArray[n_index]--; o_index++; } else { n_index++; } } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); System.out.println("=================優(yōu)化排序===================="); print(ARRAY2); System.out.println("============================================"); print(sort2(ARRAY2)); } }
時間復(fù)雜度
很明顯,在排序過程中,我們至少遍歷了三次原始數(shù)組,一次計數(shù)數(shù)組,所以它的復(fù)雜度為Ο(n+m)。因此,計數(shù)排序比任何排序都要塊,這是一種犧牲空間換取時間的做法,因為排序過程中需要用一個計數(shù)數(shù)組來存元素組的出現(xiàn)次數(shù)。
算法穩(wěn)定性
在新建的計數(shù)數(shù)組中記錄原始數(shù)組中每個元素的數(shù)量,如果原始數(shù)組有相同的元素,則在輸出時,無法保證元素原來的排序,是一種不穩(wěn)定的排序算法。
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
解析Java和Eclipse中加載本地庫(.dll文件)的詳細(xì)說明
本篇文章是對Java和Eclipse中加載本地庫(.dll文件)進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05基于springboot實現(xiàn)redis分布式鎖的方法
這篇文章主要介紹了基于springboot實現(xiàn)redis分布式鎖的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11Java獲取兩個集合List的交集、補集、并集(相加)和差集(相減)的不同方式
這篇文章主要給大家介紹了關(guān)于Java獲取兩個集合List的交集、補集、并集(相加)和差集(相減)的不同方式,在一般操作中對于list集合取交集、差集、并集,比較簡單,需要的朋友可以參考下2023-08-08詳解JAVAEE——SSH三大框架整合(spring+struts2+hibernate)
這篇文章主要介紹了詳解JAVAEE——SSH三大框架整合(spring+struts2+hibernate),具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-07-07java線程池合理設(shè)置最大線程數(shù)和核心線程數(shù)方式
這篇文章主要介紹了java線程池合理設(shè)置最大線程數(shù)和核心線程數(shù)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-12-12