###### tags: `Java`
# Java自學紀錄 - 計數排序
## 學習重點
* 計數排序法

## 計數排序法

>計數排序法是不移動資料,直接進行線性比較的
>可以想成N個學生舉著自己的分數,他們要如何知道自己的名次?
> **方法1** 就是算出比自己高分的人有幾個再+1就是自己的名次了,但其比較次數為N*N
>**方法2** 使他們排成一排,由第一個往右逐一比較,且分數低者,令其名次+1,到第二人時不必再跟第一人比較,同理第三個人不必再與第1.2人比較,期比較次數為```(N*N)/2```

==example==
圖檔來源 : http://gg.gg/lohv2

## Counting sort 實作

import java.util.Scanner;

public class Counting_sort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int a[] = new int [n]; 
        int b[] = new int [n]; //算名次
        for(int i=0;i<n;i++){
            a[i] = in.nextInt();
            b[i] = 1; //先把每個預設成1(因為最後名次都要+1)
        }
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]>a[j]) b[j]++;
                else b[i]++;
            }
        }
        System.out.print("各數名次分別為 : ");
        for(int i=0;i<n;i++){
            System.out.print(b[i]+" ");
        }
    }
}

>下圖為執行結果