算法描述

  • 字符串长度为W,从右向左对每个字符使用键索引计数法将所有字符串排序W遍,基数排序

实现

  1. public class LSD {
  2.     public static void sort(String[] a, int w){
  3.         int N = a.length;
  4.         int R = 256;
  5.         String[] aux = new String[N];
  7.         for (int d = w-1; d >= 0; d--){
  8.             int[] count = new int[R+1];
  9.             for (int i = 0; i < N; i++)//统计频度
  10.                 count[a[i].charAt(d)+1]++;
  11.             for (int r = 0; r < R; r++)//频度转化为索引
  12.                 count[r+1] += count[r];
  13.             for (int i = 0; i < N; i++)//排序
  14.                 aux[count[a[i].charAt(d)]++] = a[i];
  15.             for (int i = 0; i < N; i++)//回写
  16.                 a[i] = aux[i];
  17.         }
  18.     }
  19. }

算法分析

  • 基于R个字符字母表的N个长W字符串为键的元素,LSD需要访问7WN+3WR次数组,额外空间和N+R成正比

证明:W轮键索引计数:初始化数组:N+W(R+1),循环:W(2N+2R+3N+2N),空间上由aux[N]和count[R+1]可得

  • LSD算法是稳定的

证明:对于每一轮索引计数分别是稳定的,递推至W轮始终是稳定的