快捷導(dǎo)航

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

更新時(shí)間：2023年10月31日 10:19:31 作者：哇哈哈水有點(diǎn)甜

這篇文章主要介紹了Java排序算法之計(jì)數(shù)排序解析,找到數(shù)組中數(shù)值最大的元素,創(chuàng)建一個(gè)長(zhǎng)度為最大元素+1的臨時(shí)數(shù)組,這樣就可以把原始數(shù)組轉(zhuǎn)換為以原始數(shù)組元素值為下標(biāo),相同元素個(gè)數(shù)為值的臨時(shí)數(shù)組,需要的朋友可以參考下

Java計(jì)數(shù)排序解析

原理：找到數(shù)組中數(shù)值最大的元素，（如這里的8），創(chuàng)建一個(gè)長(zhǎng)度為最大元素+1的臨時(shí)數(shù)組，（這里為9），這樣就可以把原始數(shù)組轉(zhuǎn)換為：以原始數(shù)組元素值為下標(biāo)，相同元素個(gè)數(shù)為值的臨時(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] ，這就需要?jiǎng)?chuàng)建一個(gè)長(zhǎng)度為97的數(shù)組，而這個(gè)數(shù)組前90個(gè)位置就被浪費(fèi)了，所以可以進(jìn)行優(yōu)化

優(yōu)化：用數(shù)組的最大值減去最小值，創(chuàng)建一個(gè)長(zhǎng)度為差值+1的數(shù)組，保存每個(gè)元素時(shí)保存相對(duì)大小，如上面這個(gè)數(shù)組，差值為8-2=6，創(chuàng)建一個(gè)長(zhǎng)度為7的數(shù)組，用每個(gè)元素減去最小值，然后用結(jié)果去轉(zhuǎn)換為下面的數(shù)組

在這里插入圖片描述

代碼實(shí)現(xiàn)（java）：

//測(cè)試
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長(zhǎng)度的臨時(shí)數(shù)組
    int[] tmp = new int[len + 1];
    //遍歷原數(shù)組，將（元素-最小值）作為下標(biāo)，元素個(gè)數(shù)為value，插入到臨時(shí)數(shù)組
    for (int i : arr) {
        tmp[i-min] ++;
    }
    //遍歷臨時(shí)數(shù)組，每個(gè)下標(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排序算法之計(jì)數(shù)排序解析的文章就介紹到這了,更多相關(guān)Java計(jì)數(shù)排序解析內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: