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

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

 更新時(shí)間:2021年08月23日 10:50:34   作者:阿粵Ayue  
這篇文章主要介紹了java中的計(jì)數(shù)排序,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

計(jì)數(shù)排序

一種非比較排序。計(jì)數(shù)排序?qū)σ欢ǚ秶鷥?nèi)的整數(shù)排序時(shí)候的速度非??欤话憧煊谄渌判蛩惴?。但計(jì)數(shù)排序局限性比較大,只限于對(duì)整數(shù)進(jìn)行排序,而且待排序元素值分布較連續(xù)、跨度小的情況。

如果一個(gè)數(shù)組里所有元素都是整數(shù),而且都在0-k以內(nèi)。對(duì)于數(shù)組里每個(gè)元素來說,如果能知道數(shù)組里有多少項(xiàng)小于或等于該元素,就能準(zhǔn)確地給出該元素在排序后的數(shù)組的位置。

如給定一個(gè)0~5范圍內(nèi)的數(shù)組[2,5,3,0,2,3,0,3],對(duì)于元素5為其中最大的元素,創(chuàng)建一個(gè)大小為(5-0+1 = 6)的計(jì)數(shù)數(shù)組,如果原數(shù)組中的值對(duì)應(yīng)計(jì)數(shù)數(shù)組的下標(biāo),則下標(biāo)對(duì)應(yīng)計(jì)數(shù)數(shù)組的值加1。

image-20210806112939098

問題

上面是通過數(shù)組的最大值來確定計(jì)數(shù)數(shù)組的長度的,但如果需要對(duì)學(xué)生的成績進(jìn)行排序,如學(xué)生成績?yōu)椋篬95,93,92,94,92,93,95,90],如果按照上面的方法來處理,則需要一個(gè)大小為100的數(shù)組,但是可以看到其中的最小值為90,那也就是說前面 0~89 的位置都沒有數(shù)據(jù)存放,造成了資源浪費(fèi)。

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

image-20210806121018728

代碼實(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;
            }
        }
        //初始化一個(gè)計(jì)數(shù)數(shù)組且值為0
        int[] countArray = new int[max + 1];
        for (int i = 0; i < countArray.length; i++) {
            countArray[i] = 0;
        }
        //填充計(jì)數(shù)數(shù)組
        for (int temp : array) {
            countArray[temp]++;
        }
        int o_index = 0;//原數(shù)組下標(biāo)
        int n_index = 0;//計(jì)數(shù)數(shù)組下標(biāo)
        while (o_index < array.length) {
            //只要計(jì)數(shù)數(shù)組的下標(biāo)不為0,就將計(jì)數(shù)數(shù)組的值從新寫回原數(shù)組
            if (countArray[n_index] != 0) {
                array[o_index] = n_index;//計(jì)數(shù)數(shù)組下標(biāo)對(duì)應(yīng)元素組的值
                countArray[n_index]--;//計(jì)數(shù)數(shù)組的值要-1
                o_index++;
            } else {
                n_index++;//上一個(gè)索引的值為0后開始下一個(gè)
            }
        }
        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;
            }
        }
        //定義一個(gè)偏移量,即最小值前面0~min的范圍,這里直接用一個(gè)負(fù)數(shù)來表示
        int bias = 0 - min;
        //初始化一個(gè)計(jì)數(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]++;
        }
        //填充計(jì)數(shù)數(shù)組
        int o_index = 0;//原數(shù)組下標(biāo)
        int n_index = 0;//計(jì)數(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));
    }
}

時(shí)間復(fù)雜度

很明顯,在排序過程中,我們至少遍歷了三次原始數(shù)組,一次計(jì)數(shù)數(shù)組,所以它的復(fù)雜度為Ο(n+m)。因此,計(jì)數(shù)排序比任何排序都要塊,這是一種犧牲空間換取時(shí)間的做法,因?yàn)榕判蜻^程中需要用一個(gè)計(jì)數(shù)數(shù)組來存元素組的出現(xiàn)次數(shù)。

算法穩(wěn)定性

在新建的計(jì)數(shù)數(shù)組中記錄原始數(shù)組中每個(gè)元素的數(shù)量,如果原始數(shù)組有相同的元素,則在輸出時(shí),無法保證元素原來的排序,是一種不穩(wěn)定的排序算法。

總結(jié)

本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • IDEA中打jar包的2種方式(Maven打jar包)

    IDEA中打jar包的2種方式(Maven打jar包)

    這篇文章主要給大家介紹了關(guān)于IDEA中打jar包的2種方式,分別是不使用Maven直接打Jar包與使用Maven打jar包的兩種方法,需要的朋友可以參考下
    2021-05-05
  • 解析Java和Eclipse中加載本地庫(.dll文件)的詳細(xì)說明

    解析Java和Eclipse中加載本地庫(.dll文件)的詳細(xì)說明

    本篇文章是對(duì)Java和Eclipse中加載本地庫(.dll文件)進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • 基于springboot實(shí)現(xiàn)redis分布式鎖的方法

    基于springboot實(shí)現(xiàn)redis分布式鎖的方法

    這篇文章主要介紹了基于springboot實(shí)現(xiàn)redis分布式鎖的方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11
  • Java獲取兩個(gè)集合List的交集、補(bǔ)集、并集(相加)和差集(相減)的不同方式

    Java獲取兩個(gè)集合List的交集、補(bǔ)集、并集(相加)和差集(相減)的不同方式

    這篇文章主要給大家介紹了關(guān)于Java獲取兩個(gè)集合List的交集、補(bǔ)集、并集(相加)和差集(相減)的不同方式,在一般操作中對(duì)于list集合取交集、差集、并集,比較簡單,需要的朋友可以參考下
    2023-08-08
  • SpringBoot去除參數(shù)前后空格和XSS過濾

    SpringBoot去除參數(shù)前后空格和XSS過濾

    本文主要介紹了SpringBoot去除參數(shù)前后空格和XSS過濾,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • 使用jps命令查看Java進(jìn)程的詳細(xì)指南

    使用jps命令查看Java進(jìn)程的詳細(xì)指南

    jps是Java開發(fā)者和系統(tǒng)管理員的得力助手,它簡化了Java進(jìn)程監(jiān)控的過程,使得快速檢查應(yīng)用運(yùn)行狀態(tài)變得輕而易舉,在Java開發(fā)和運(yùn)維場景中,jps是一個(gè)非常實(shí)用的命令行工具,本文介紹了如何有效地使用 jps命令來查看Java進(jìn)程的詳細(xì)指南,需要的朋友可以參考下
    2024-10-10
  • 詳解JAVAEE——SSH三大框架整合(spring+struts2+hibernate)

    詳解JAVAEE——SSH三大框架整合(spring+struts2+hibernate)

    這篇文章主要介紹了詳解JAVAEE——SSH三大框架整合(spring+struts2+hibernate),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-07-07
  • java線程池合理設(shè)置最大線程數(shù)和核心線程數(shù)方式

    java線程池合理設(shè)置最大線程數(shù)和核心線程數(shù)方式

    這篇文章主要介紹了java線程池合理設(shè)置最大線程數(shù)和核心線程數(shù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-12-12
  • java判斷域名無法訪問自行訪問下一條

    java判斷域名無法訪問自行訪問下一條

    這篇文章主要為大家介紹了java實(shí)現(xiàn)判斷域名無法訪問的時(shí)候自行訪問下一條域名示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-12-12
  • 解析spring boot與ireport 整合問題

    解析spring boot與ireport 整合問題

    本文通過實(shí)例代碼給大家介紹了spring boot 與 ireport 整合問題,關(guān)于pom文件依賴的問題通過實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧
    2021-10-10

最新評(píng)論