算法练习_低位优先的字符串排序算法

概念

在许多排序应用中，决定顺序的键都是字符串，因此，对字符串的处理十分重要。
一种字符串排序算法是低位优先法（LSD)，这种方法会从右到左地检查键中的字符，适用于键的长度都相同的字符串排序应用。

键索引计数法

键索引计数法是 LSD 的基础，有 4 个步骤：

• 频率统计：使用 int[] 数组来计算每个键出现的频率；
• 将频率转换为索引：计算每个键在排序结果中的起始索引位置；
• 数据分类：将所有元素移到一个辅助数组中进行排序；
• 回写：将排好序的数组写回原数组。

图解

假设将学生分为若干组，标号 1、2、3等，希望将学生按组分类

代码实现

public class KeyIndex {

    Student[] sort(Student[] students, int r) {

        int length = students.length;
        int[] count = new int[r + 1];
        Student[] aux = new Student[length];

        //频率统计
        for (int i = 0; i < length; i++) {
            count[students[i].getKey() + 1]++;
        }
        //转换为索引
        for (int j = 0; j < r; j++) {
            count[j + 1] = count[j + 1] + count[j];
        }
        //数据分类
        for (int i = 0; i < length; i++) {
            aux[count[students[i].getKey()]++] = students[i];
        }
        //回写
        for (int i = 0; i < length; i++) {
            students[i] = aux[i];
        }
        return students;
    }
}

class Student {
    String name;
    int key;

    public Student(String name, int key) {
        this.name = name;
        this.key = key;
    }

    public int getKey() {
        return key;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", key=" + key +
                '}';
    }
}

低位优先的字符串排序算法

假设有一位工程师，记录了给定时间段内某条公路上所有车辆的车牌号，他希望知道总共有多少不同的车辆经过这段高速公路。解决这个问题的一种简单方法就是将所有车牌号排序，然后遍历找出不同车牌号的数量。这可以使用键索引计数法来完成，从右向左以每个位置的字符作为键。

图解

代码实现

public class LSD {
    void sort(String[] a, int w) {
        int length = a.length;
        int R = 256;
        for (int i = w - 1; i >= 0; i--) {
            int[] count = new int[R + 1];
            //统计频率
            for (int j = 0; j < length; j++) {
                count[a[j].charAt(i) + 1]++;
            }
            //计算索引
            for (int j = 0; j < R; j++) {
                count[j + 1] += count[j];
            }
            String[] aux = new String[length];
            //按索引重排
            for (int j = 0; j < length; j++) {
                aux[count[a[j].charAt(i)]++] = a[j];
            }
            //回写
            for (int j = 0; j < length; j++) {
                a[j] = aux[j];
            }
        }
    }

    public static void main(String[] args) {
        String[] strings = new String[]{"1ick750", "2iye230", "3cio720", "4pgc938", "3cio720", "1ick750", "2iye230", "2tye230"};
        new LSD().sort(strings, 6);
        Assert.check(strings[0].equals("1ick750"));
        Assert.check(strings[1].equals("1ick750"));
        Assert.check(strings[2].equals(strings[3]));
    }
}

参考文档

《算法》第四版