排序算法-基数排序的时间复杂度分析

基数排序的思想

基数排序，基数排序的思想是把位数相同的一组数组依次从后往前比较其每一位上的大小，通过几轮比较使得数据达到有序的作法。比较的次数跟数据的位数有关系。好比要比较一组手机号码从小到大排列，能够比较手机号每一位大小，而后比较11次，手机号达到有序。java

注意：基数排序每次位的比较能够使用线性排序的方式，好比桶排序或者计数排序，由于它们的时间复杂度为O(n)，并且每轮的比较须要保证每次比较数据的稳定性，否则基数排序就没法完成。算法

图解

代码

package com.study.algorithm.sort;

public class RadixSort {

    /**
     * 基数排序
     *
     * @param arr
     */
    public static void radixSort(int[] arr) {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // 从个位开始，对数组arr按"指数"进行排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    /**
     * 计数排序-对数组按照"某个位数"进行排序
     *
     * @param arr
     * @param exp 指数
     */
    public static void countingSort(int[] arr, int exp) {
        if (arr.length <= 1) {
            return;
        }

        // 计算每一个元素(位0~9)出现的个数
        int[] c = new int[10];
        for (int i = 0; i < arr.length; i++) {
            c[(arr[i] / exp) % 10]++;
        }

        // 计算排序后的位置
        for (int i = 1; i < c.length; i++) {
            c[i] += c[i - 1];
        }

        // 临时数组r，存储排序以后的结果
        int[] r = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            r[c[(arr[i] / exp) % 10] - 1] = arr[i];
            c[(arr[i] / exp) % 10]--;
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = r[i];
        }
    }
    public static void printArr(int[] arr,int n){
        for (int i = 0; i < n ; i++) {
            System.out.print("["+arr[i]+"]");
        }
    }
    public static void main(String[] args) {
        int[] arr={11255 ,45652,22545,54454,55211,45686,12125,45654};
        radixSort(arr);
        printArr(arr,8);

    }
}

基数排序的时间复杂度

基数排序每一位的比较能够使用线性排序，好比桶排序或者计数排序，固然须要保证如计数排序的稳定性。每次排序时间复杂度O(n)，那么若是有k位，则时间复杂度为O(k*n),若是k不大好比手机号11位，那么时间复杂度就是O(n)数组

基数排序的稳定性

基数排序是稳定排序算法spa

基数排序是原地排序算法吗？

基数排序基于线性排序如计数排序，因此不是原地排序算法。code

基数排序的应用场景

基数排序对数据有要求，要可以将数据分割成独立的位。每一位的数据范围不能太大，要可以使用线性排序来实现。基数排序数据的长度要相等，不等的话须要补齐。blog