欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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ù)組里有多少項小于或等于該元素,就能準(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。

image-20210806112939098

問題

上面是通過數(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就是這個偏移量。

image-20210806121018728

代碼實現(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)文章

最新評論