数据结构与算法(十五)——桶、计数、基数排序

桶排序、计数排序、基数排序都是线性排序，都是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket sort）

将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

时间复杂度为 O(n)

public static void basket(int data[])//data为待排序数组
{
    int n=data.length;
    int bask[][]=new int[10][n];
    int index[]=new int[10];
    int max=Integer.MIN_VALUE;

    for(int i=0;i<n;i++){
     max=max>(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());
    }

    String str;
    for(int i=max-1;i>=0;i--){
        for(int j=0;j<n;j++){
            str="";
            if(Integer.toString(data[j]).length()<max){
                for(int k=0;k<max-Integer.toString(data[j]).length();k++)
                str+="0";
            }
            str+=Integer.toString(data[j]);
            bask[str.charAt(i)-'0'][index[str.charAt(i)-'0']++]=data[j];
        }
        int pos=0;
        for(int j=0;j<10;j++){
            for(int k=0;k<index[j];k++){
                data[pos++]=bask[j][k];
            }
        }
        for(intx=0;x<10;x++)index[x]=0;
    }
}

计数排序（Counting sort）

计数排序对输入的数据有附加的限制条件：

输入的线性表的元素属于有限偏序集S；
设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

计数排序的时间复杂性为O(n)。

算法的步骤如下：

找出待排序的数组中最大和最小的元素
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
对所有的计数累加 (从 C 中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去1

// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。 
public void countingSort(int[] a, int n) { 
    if (n <= 1) return;
    // 查找数组中数据的范围 
    int max = a[0]; 
    for (int i = 1; i < n; ++i) { 
        if (max < a[i]) { 
            max = a[i];
        } 
    }

    int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max] 
    for (int i = 0; i <= max; ++i) { 
        c[i] = 0;
    }

    // 计算每个元素的个数，放入 c 中 
    for (int i = 0; i < n; ++i) { 
        c[a[i]]++;
    }

    // 依次累加 
    for (int i = 1; i <= max; ++i) { 
        c[i] = c[i-1] + c[i];
    }

    // 临时数组 r，存储排序之后的结果 
    int[] r = new int[n]; 
    // 计算排序的关键步骤，有点难理解 
    for (int i = n - 1; i >= 0; --i) { 
        int index = c[a[i]]-1; 
        r[index] = a[i]; 
        c[a[i]]--;
    }

    // 将结果拷贝给 a 数组 
    for (int i = 0; i < n; ++i) { 
        a[i] = r[i];
    } 
}

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序（Radix sort）

将整数按位数切割成不同的数字，然后按每个位数分别比较。（由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数）

实现原理
将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补0。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
PS:因为根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。

基数排序的方式可以采用LSD（Least significant digital 最低位优先）或MSD（Most significant digital 最高位优先），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

public class RadixSort
{
    public static void sort(int[] number, int d) //d表示最大的数有多少位
    {
        intk = 0;
        intn = 1;
        intm = 1; //控制键值排序依据在哪一位
        int[][]temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9
        int[]order = newint[10]; //数组orderp[i]用来表示该位是i的数的个数
        while(m <= d)
        {
            for(inti = 0; i < number.length; i++)
            {
                intlsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(inti = 0; i < 10; i++)
            {
                if(order[i] != 0)
                    for(intj = 0; j < order[i]; j++)
                    {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }
    public static void main(String[] args)
    {
        int[]data =
        {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
        RadixSort.sort(data, 3);
        for(inti = 0; i < data.length; i++)
        {
            System.out.print(data[i] + "");
        }
    }
}