Java排序之計數(shù)排序

wind3110991 發(fā)布于2019-08-15 18:07 / 3245人閱讀

摘要：排序之計數(shù)排序計數(shù)排序思路計數(shù)排序適用于有明確范圍的數(shù)組，比如給定一個數(shù)組，且知道所有值得范圍是。這個時候可以使用一個長度的數(shù)組，待排序的數(shù)組就可以散在這個數(shù)組上，數(shù)組的值就是當前值的個數(shù)，再經(jīng)過一次遍歷展開，得到的數(shù)組就有序了。

Java排序之計數(shù)排序 1. 計數(shù)排序思路

計數(shù)排序適用于有明確范圍的數(shù)組，比如給定一個數(shù)組，且知道所有值得范圍是[m,n]。這個時候可以使用一個n-m+1長度的數(shù)組，待排序的數(shù)組就可以散在這個數(shù)組上，數(shù)組的值就是當前值的個數(shù)，再經(jīng)過一次遍歷展開，得到的數(shù)組就有序了。

新建一個長度為n-m+1的臨時數(shù)組

遍歷待排序數(shù)組，它的值-m作為臨時數(shù)組下角標，這個位置的值加1

遍歷結束，臨時數(shù)組就存儲了每個值得個數(shù)

最后將它展開賦值給原數(shù)組

2. Java代碼實現(xiàn)

package com.wangjun.arithmetic;

import java.util.Arrays;

public class SortCount {

    public static void main(String[] args) {
        //測試
        int[] arr = {1,4,6,7,5,4,3,2,1,4,5,10,9,10,3};
        sortCount(arr, 1, 10);
        System.out.println(Arrays.toString(arr));
    }
    
    //計數(shù)排序的初步實現(xiàn)，使用了多余的空間，可以嘗試不使用多余的空間
    public static void sortCount(int[] arr, int m, int n) {
        int len = arr.length;
        int[] tem = new int[n - m + 1];
        for(int i = 0; i < len; i++) {
            tem[arr[i] - m] += 1;
        }
        for(int i = 0, index = 0; i < tem.length; i++) {
            int item = tem[i];
            while(item-- != 0) {
                arr[index++] = i + m;
            }
        }
    }

}

打印結果：

[1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10]

GPU云服務器云服務器計數(shù)排序 java 排序 java 排序動畫 java 排序速度

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/69635.html

基本算法學習(四)之計數(shù)排序(JS)

摘要：計數(shù)排序首先我們要對計數(shù)排序有一個正確的認識計數(shù)排序是用于確定范圍的整數(shù)的線性時間排序算法這一句話我們就可以知道計數(shù)排序該如何用了處理數(shù)據(jù)確定范圍內的整數(shù)特點快線性時間其數(shù)據(jù)如下最佳情況最差情況平均情況計數(shù)排序的步驟如下查找待排序數(shù)組中最大計數(shù)排序首先我們要對計數(shù)排序有一個正確的認識,計數(shù)排序是用于確定范圍的整數(shù)的線性時間排序算法,這一句話我們就可以知道計數(shù)排序該如何用了.處理數(shù)據(jù)...

AlexTuan 2019-08-21 11:22 評論0 收藏0
【算】計數(shù)排序和桶排序

摘要：計數(shù)排序之前接觸的選擇快排等算法，都是著眼于怎么更快的調整元素位置，以達到排序的目的。桶排序桶排序能解決浮點數(shù)字的問題，至于槽大嘛，依然深受其害。思路桶排序與計數(shù)排序的思路多少有些類似，有數(shù)組整裝待排，還是一如既往的從小到大好了。計數(shù)排序之前接觸的選擇、快排等算法，都是著眼于怎么更快的調整元素位置，以達到排序的目的。而計數(shù)排序則不然，設計思路可謂另辟蹊徑！思路我們對15個10以...

Yangyang 2019-08-15 15:39 評論0 收藏0
【算法】計數(shù)排序 + 各個排序算法的穩(wěn)定性

摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。之前介紹的排序算法：【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...

不知名網(wǎng)友 2021-11-29 10:50 評論0 收藏0
Javag工程師成神之路（2019正式版）

摘要：結構型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態(tài)模式策略模式職責鏈模式責任鏈模式訪問者模式。主要版本更新時間備注 v1.0 2015-08-01 首次發(fā)布 v1.1 2018-03-12 增加新技術知識、完善知識體系 v2.0 2019-02-19 結構...

Olivia 2019-08-16 15:14 評論0 收藏0
常用排序算法之JavaScript實現(xiàn)

摘要：代碼實現(xiàn)六堆排序算法簡介堆排序是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。九計數(shù)排序算法簡介計數(shù)排序是一種穩(wěn)定的排序算法。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

jerry 2019-08-21 12:27 評論0 收藏0