快捷導(dǎo)航

Java排序算法之計數(shù)排序解析

更新時間：2023年10月31日 10:19:31 作者：哇哈哈水有點甜

這篇文章主要介紹了Java排序算法之計數(shù)排序解析,找到數(shù)組中數(shù)值最大的元素,創(chuàng)建一個長度為最大元素+1的臨時數(shù)組,這樣就可以把原始數(shù)組轉(zhuǎn)換為以原始數(shù)組元素值為下標(biāo),相同元素個數(shù)為值的臨時數(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個位置就被浪費了，所以可以進(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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: