非常簡潔明了的基數排序——java實作

基數排序：

    它的基本思想是：類似于建立一個二維的連結清單（第一層連結清單為0-9号），首先看每個數的個位，如果為0放入0号連結清單，為1放入1号連結清單……再對十位，百位排……。每躺排序後吧連結清單周遊一遍放入傳入的arr中，經過幾輪之後就排序完成。簡單來說就是先對個位排序，在對十位排序，再對百位排序，以此類推。

排序方法：

比如我們要排序 arr｛135，242，192，93，345，11，24，19｝

第一步：收集個位數

    1.把每個數對10求餘得到個位數，然後根據個位數放入0-9号連結清單：

   連結清單：  0    1    2    3   4     5     6   7   8    9

        ｛ []  [11] [242,192] [93] [24] [135,345]  []  []  []   [19] ｝

    根據周遊，取出元素放入arr數組中得到：

            ｛11，242，192，93，24，135，345，19｝

    2.進行第二輪對100求餘再除10得到十位的數字，進行對十位排序：

   連結清單：   0     1    2   3     4      5   6   7   8      9

        ｛ []  [11，19] [24] [135] [242，345]  []  []  []  []   [192，93] ｝

    3.進行第三輪排序，對1000求餘，再除100得到百位數字，進行百位排序：

   連結清單：       0          1       2     3    4   5   6   7    8   9

       ｛ [11，19，24，93]  [135，192]  [242]   [345]  []  []  []   []   []   [] ｝

     周遊得到：    ｛11，19，24，93，135，192，242，345｝

大家發現沒有，當對最大的位數排序完後，數組arr就已經排序成功了，這就是基數排序。

下面的圖就是這個例子：（圖中第一躺個位19應該在9号連結清單）

        由于這個方法隻能對正數進行排序，如果存在負數，我們就把負數和正數分開成兩個數組，然後排序之後合并起來就可以，具體見代碼，加入了詳細注釋。

import java.util.ArrayList;


public class BasicSort {

	public static void basicSort(int[] arr) {
		
		//擷取最大值
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			if(max < arr[i]) {
				max = arr[i];
			}
		}
		
		//擷取最大位數
		int count = 0;
		while (max > 0) {
			max /= 10;
			count++;
		}
		
		ArrayList<ArrayList> queue = new ArrayList<ArrayList>();
		//i是位數，在每個位數上構造一個數組
		for (int i = 0; i < 10; i++) {
			queue.add(new ArrayList());
		}
		
		//配置設定數組
		for (int i = 0; i < count; i++) {//周遊各個位
			
			for (int j = 0 ; j < arr.length; j++) {//周遊arr數組
				//擷取對應位的值，如果第一輪就得到各位的值，第二輪就得到百位的值
				int x = arr[j] % (int)(Math.pow(10, i + 1)) / (int)(Math.pow(10, i));
				queue.get(x).add(arr[j]);//取第x組把目前元素添加進去
			}
			
			//形成新的arr數組
			int count2 = 0;
			for (int j = 0; j < 10; j++) {
				while (queue.get(j).size() > 0) {
					ArrayList<Integer> q = queue.get(j);
					arr[count2] = q.get(0);
					q.remove(0);
					count2++;
				}
			}
		}
	}
	
	public static void sort(int[] arr) {
		//設定兩個數組接受正負數
		int[] arr1 = new int[arr.length];
		int[] arr2 = new int[arr.length];
		//正負數計數器
		int count1 = 0;
		int count2 = 0;
		
		//正數放入arr1，負數把他變正放入arr2
		for (int i = 0; i < arr.length; i++) {
			if(0 <= arr[i]) {
				arr1[count1] = arr[i];
				count1++;
			}
			else {
				arr2[count2] = -1 * arr[i];
				count2++;
			}
		}
		
		//對負數排序，然後反向存入arr的0——count2中
		basicSort(arr2);
		for(int i = 0; i < count2 ; i++) {
			arr[i] = -1 * arr2[arr2.length - 1 - i];
		}
		//對正數排序，吧正數從count2存入arr中
		basicSort(arr1);
		for(int i = count2; i < count1 + count2 ; i++) {
			arr[i] = arr1[i];
		}
	}
	
	
	public static void main(String[] args) {
		int[] arr = {136,-37,27,48,1,-2,0};
		sort(arr);
		for (int n:arr) {
			System.out.print(" " + n);
		}
	}
	
}