一、时间复杂度为O(n)的排序（计数排序，基数排序）

  以下算法不是基于比较的排序，是基于桶排序思想的排序。

1.计数排序

  【1】先根据元素的范围建立相应数量的桶
  【2】遍历数组并依次将其放进对应的桶中
  【3】依次取出桶中元素，排序完成

import java.util.*;

public class CountingSort {
    public int[] countingSort(int[] A, int n) {
        if(A == null || n < 2)
            return A;

        int max = A[0];        //数组中的最大值
        int min = A[0];        //数组中的最小值
        int index = 0;        

        //找出最大值和最小值
        for(int value : A){
            if(max < value)    max = value;
            if(min > value)    min = value;
        }

        //根据最大值和最小值建立桶
        int[] bucket = new int[max - min + 1];

        //遍历数组，将元素放入桶中
        for(int value : A)
            bucket[value - min]++;

        //元素出桶   
        for(int i = 0; i < bucket.length; i++){
            while(bucket[i] > 0){
                A[index++] = i + min;
                bucket[i]--;
            }
        }

        return A;

    }
}

2.基数排序

  【1】建立0-9号桶，遍历所有数，根据个位进行桶的放入
  【2】根据十位执行【1】，以此类推
  【3】最高位执行【1】后，倒出所有元素，排序完成
  注：取桶入桶按照队列方式先进先出

import java.util.*;

public class RadixSort {
    public int[] radixSort(int[] A, int n) {
        // write code here
        if(A == null || n < 2)
            return A;

        ArrayList<Integer> negativeArray = new ArrayList<Integer>();
        ArrayList<Integer> positiveArray = new ArrayList<Integer>();
        int min = A[0];
        int max = A[0];
        int index = 0;

        for(int value : A){
            if(value < 0)    
                negativeArray.add(-value);
            else    
                positiveArray.add(value);

            if(min > value)   
                min = value;
            else if(max < value)    
                max = value;
        }

        radixSortForPositive(negativeArray, -min);
        radixSortForPositive(positiveArray, max);

        for(int i = negativeArray.size()-1; i >= 0; i--){
            A[index++] = -negativeArray.get(i);
        }

        for(int i =0; i < positiveArray.size(); i++){
            A[index++] = positiveArray.get(i);
        }

        return A;
    }

    private void radixSortForPositive(ArrayList<Integer> positiveArray, int max){
        int base = 10;
        ArrayList<LinkedList> bucket1 = new ArrayList<LinkedList>();
        ArrayList<LinkedList> bucket2 = new ArrayList<LinkedList>();
        for(int i = 0; i < 10; i++){
            bucket1.add(new LinkedList());
            bucket2.add(new LinkedList());
        }

        for(int value : positiveArray){
            bucket1.get(value % 10).offer(value);
        }

        while(base <= max){
            for(int i = 0; i < 10; i++){
                while(!bucket1.get(i).isEmpty()){
                    int value = (int) bucket1.get(i).poll();
                    bucket2.get((value/base) % 10).add(value);
                }
            }

            ArrayList<LinkedList> temp = bucket1;
            bucket1 = bucket2;
            bucket2 = temp;
            base =base*10;
        }

        int index = 0;
        for(int i = 0; i < 10; i++){
            while(!bucket1.get(i).isEmpty())
                positiveArray.set(index++, (Integer)bucket1.get(i).poll());
        }
    }
}