基数排序

package com.sort;

import java.util.Scanner;

/**
 * 基数排序（桶排序的优化） O(n+d(n+10+n+n))        稳定算法
 * 桶排序缺点：当最大值最小值间隔特别大时，浪费时间、空间。
 * 时间复杂度O（n+(m+n)）n为元素个数，m为桶大小）
 * 桶排序：例如：5、2、1000三个元素排序时，需要建大小为1000的桶。浪费空间、时间。
 * @author chenger
 *
 */
public class RadixSort {

    public static void main(String[] args) {
        new RadixSort().calculate();
    }
    
    public void calculate() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int i = 0;
        while(n > i) {
            arr[i++] = scanner.nextInt();
        }
        sort(arr);
        scanner.close();
    }
    
    public void sort(int[] arr) {
        int[] buckets = new int[10];    //桶
        int[] temp = new int[arr.length]; //临时
        int max = arr[0];
        // 找出最大元素
        for(int i : arr) {
            if(i > max)
                max = i;
        }
        // 循环len次
        for(int exp = 1 ; max / exp > 0 ; exp *= 10) {
            //计算每个桶有多少数据
            for(int i : arr) {
                buckets[i / exp % 10]++;
            }
            /**
             * 例如buckets[0]为0 buckets[1]为1、buckets[2]为2、buckets[3]为3 、
             * buckets[4]为2时说明buckets[4]的两个元素在这一次排序中的7-8位置。
             */
            // 统计buckets里的数
            for(int i = 1 ; i < 10 ; i++) {
                buckets[i] += buckets[i-1]; // buckets[i]的值应该在数组的什么位置
            }
            
            //数据按序存入临时空间
            for(int i = arr.length - 1 ; i >= 0 ; i--) {
                // **判断当前数据在哪个桶里，并且那个桶的数据在这次排序应该排在什么位置**
                temp[buckets[arr[i] / exp % 10]-- - 1] = arr[i];
            }
            System.arraycopy(temp, 0, arr, 0, arr.length);  //一次排序结果
            for(int i = 0 ; i < 10 ; i++) {
                buckets[i] = 0;
            }
        }
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }

}

描述

1.桶排序复习