快捷導(dǎo)航

JAVA十大排序算法之計數(shù)排序詳解

更新時間：2021年08月23日 10:50:34 作者：阿粵Ayue

這篇文章主要介紹了java中的計數(shù)排序，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

計數(shù)排序

一種非比較排序。計數(shù)排序?qū)σ欢ǚ秶鷥?nèi)的整數(shù)排序時候的速度非?？?，一般快于其他排序算法。但計數(shù)排序局限性比較大，只限于對整數(shù)進(jìn)行排序，而且待排序元素值分布較連續(xù)、跨度小的情況。

如果一個數(shù)組里所有元素都是整數(shù)，而且都在0-k以內(nèi)。對于數(shù)組里每個元素來說，如果能知道數(shù)組里有多少項(xiàng)小于或等于該元素，就能準(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ù)存放，造成了資源浪費(fèi)。

如果我們知道了數(shù)組的最大值和最小值，則計數(shù)數(shù)組的大小為（最大值 - 最小值 + 1），如上面數(shù)組的最大值為99，最小值為90，則定義計數(shù)數(shù)組的大小為（95 - 90 + 1 = 6）。并且索引分別對應(yīng)原數(shù)組9095的值。我們把090的范圍用一個偏移量來表示，即最小值90就是這個偏移量。

代碼實(shí)現(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ù)排序比任何排序都要塊，這是一種犧牲空間換取時間的做法，因?yàn)榕判蜻^程中需要用一個計數(shù)數(shù)組來存元素組的出現(xiàn)次數(shù)。