首页 > 代码库 > 计数排序

计数排序

2024-07-06 21:43:53   225人阅读

计数排序是基于非比较的一种排序，效率高，但是需要额外的内存空间，适用于 数量比比较小，而且对元素最大值也有限制。

代码流程如下：假设原数组名称为a

1.计算出数组当中最大的值，比如maxv

2.申请一个用于计数的数组c，数组大小为maxv

3.统计各个元素出现的个数c[a[i]]++

4.使用c[i]=c[i-1]+c[i]统计出小于等于i的元素个数。

5.申请一个记录结果的数组b，使用b[c[a[i]]]记录排序结果，c[a[i]]--

排序的时间复杂度在maxv*k因此非常快，但是这是以牺牲存储空间为代价的。

具体的java代码如下：

+ View Code?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.io.*;
public class Main {
 
    public static void main(String[] args) throws IOException {
         
        String str =null;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while((str = reader.readLine())!=null){
            String []tmps = str.split(" ");
            int n = tmps.length;
            int nums[]=new int[n];
            int maxv=-1;
            for(int i=0;i<n;i++){
                nums[i]=Integer.valueOf(tmps[i]);
                if(maxv<nums[i])maxv=nums[i];
            }
             
            int []c =new int[maxv+1];//c 数组要从1开始
             
            for(int i=1;i<=maxv;i++){
                c[i]=0;
            }
             
            for(int i=0;i<n;i++){
                c[nums[i]]++;
            }
             
            for(int i=2;i<=maxv;i++){
                c[i]=c[i]+c[i-1];
            }
             
            int []b =new int[n+1];
            for(int i=0;i<n;i++){
                b[c[nums[i]]]=nums[i];
                c[nums[i]]--;
            }
            outPut(n, b);
        }
    }
 
    private static void outPut(int n, int[] b) {
        for(int i=1;i<=n;i++){
            System.out.print(b[i]+" ");
        }System.out.println();
    }
 
}

 


联系
我们