排序（基数排序）

package BasicSort;  import java.util.Arrays; import java.util.Scanner;  public class BasicSort { public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int[] arr = new int[n];  for(int i = 0 ; i < n ; i++){
            arr[i] = scanner.nextInt();  } basicSort(arr);  System.out.println(Arrays.toString(arr));  } public static void basicSort(int[] arr){ //1.得到数组中最大的位数  int max = 0;  for(int i = 0 ; i < arr.length ; i++){ if(arr[i] > max){
                max = arr[i];  }
        } //得到最大数是几位  int length = (max+"").length();  /*  * 定义一个二维数组，表示十个桶  * 说明：  * 1.二维数组包含十个一维数组  * 2.为了防止在放入数的时候，数据溢出，则每一个一维数组，大小定义为 arr.length()  * 3.基数排序是空间换时间的经典算法  * */  int[][] bucket = new int[10][arr.length];  //为了记录每个桶中存放了多少个数据。我们定义一个一维数组来记录各个桶中每次放入数据的个数  //比如 bucketElementCount[1] 就表示bucket[1]桶中的数据个数  int[] bucketElementCount = new int[10];  //这里我们使用循环将代码进行处理  for(int i = 0 ,n = 1; i < length ; i++ , n *= 10){ //针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位。。。。  for(int j = 0 ; j < arr.length ; j++){ //取出每个元素对应位的值  int digitOfElement = arr[j] / n % 10;  //放入到对应的桶中  bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];  bucketElementCount[digitOfElement]++;  } //按照这个桶的顺序，（一维数组的下标，依此取出数据放到原数组）  int index = 0;  //遍历每一桶，并将每一桶的数据，放入到原数组  for(int k = 0 ; k < bucketElementCount.length ; k++){ //如果桶中有数据，我们取出，然后放回原数组  if(bucketElementCount[k] != 0){ for(int l = 0 ; l < bucketElementCount[k] ; l++){
                        arr[index++] = bucket[k][l];  }
                } //当把每个桶中数据取出后，需要将每个 bucketElementCounts[k] = 0 !!!!  bucketElementCount[k] = 0;  }
        }
    }
}

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int>nums(n);
    vector<int>temp(n);
    vector<int>bar(10);
    vector<int>count(10);
    int maxDigit = 1;
    int pos = 10;
    for (int i = 0; i < n; ++i)
    {
        cin >> nums[i];
        while (nums[i] >= pos)
        {
            maxDigit++;
            pos *= 10;
        }
    }
    pos = 10;
    for (int i = 0; i < maxDigit; ++i)
    {
        //全部元素装入桶里
        for (int j = 0; j < n; ++j)
        {

            bar[(nums[j]/(pos/10)) % 10]++;
        }
        //计算count数组
        count[0] = bar[0];
        for (int j = 1; j < 10; ++j)
        {
            count[j] = bar[j] + count[j - 1];

        }
        //将按位排好的元素装入到一个临时容器中
        for (int j = n - 1; j >= 0; --j)
        {
            temp[count[(nums[j] / (pos / 10)) % 10]-1] = nums[j];
            count[(nums[j] / (pos / 10)) % 10]--;
        }

        nums.assign(temp.begin(),temp.end());
        bar.assign(10, 0);
        pos *= 10;
    }
    for (int i = 0; i < n; ++i)
    {
        cout << nums[i] << " ";
    }
    return 0;

}