•   欢迎来到21NN网.
  •   请记住本站网址www.21nn.cn

Java完成计数排序(CountingSort)的代码示例【JAVA教程】,CountingSort

摘要: 本篇文章给人人带来的内容是关于Java完成计数排序(CountingSort)的代码示例,有肯定的参考价值,有须要的朋侪能够参考一下,愿望对你有所协助。计数排序,属于桶排序特别的一种。当要...
本篇文章给人人带来的内容是关于Java完成计数排序(CountingSort)的代码示例,有肯定的参考价值,有须要的朋侪能够参考一下,愿望对你有所协助。

计数排序,属于桶排序特别的一种。

当要排序n个数据的时刻,假如所处的局限不大,我们能够取个中的最大值K,并将数据疏散在K个桶内里,

每一个桶内里的数据都是雷同的(如许省去了桶内排序的时候),然后递次掏出就好啦。

固然计数排序说起来简朴,写起来有些处所不好明白。

比方我们如今有2,5,3,0,2,3,0,3这8个数,要对它排序,我们就能够先取到它的最大值5,然后肯定局限在0-5,

我们请求一个0-5的内存空间去离别盘算每一个位置对应的每一个数的个数。

下图示意的就是0-5这个内存空间的数据,我们能够看到个中0涌现了两次,1涌现了0次,2涌现了两次,3涌现了三次,4涌现了0次,5涌现了一次。

同时还能够总结一些规律出来,比方我们如今看到c[2]这个位置,2涌现了两次,在2前面c[0] + c[1]总共有2个元素,所以c[2]对应这两个2在原数组中的位置是2,3,我们能够得出规律c[2]所在位置 = c[0] + c[1],背面的c[3]的位置 = c[2] + c[1],我们就如许挨着递次和:然后我们扫描原数组2,5,3,0,2,3,0,3,每碰到一个数,就将该数代入c数组的索引中掏出当前元素在排序以后真正的索引。

我的Java完成以下:

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 13:45
 **/
public class CountingSort {
    public static void main(String[] args) {
        int[] numbers = {3, 9, 2, 1, 8, 7, 6, 10, 9};
        // 假定数组中存储的都黑白负整数
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 计数排序
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers){
        int n = numbers.length;
        int maxNumber = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        int[] r = new int[n];
        int[] c = new int[maxNumber + 1];
        for(int i = 0; i < n; ++i){
            c[numbers[i]]++;
        }
        for(int i = 1; i <= maxNumber; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
}

个中症结的代码:

for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;5         
            }

从c数组中掏出排序以后的索引。

以上就是Java完成计数排序(CountingSort)的代码示例的细致内容,更多请关注ki4网别的相干文章!

分享到:

发表评论

评论列表

还没有评论,快来说点什么吧~

公众号二维码

微信公众号