字符串

Java中String类来表示字符串，主要特性：

字符：String由一系列字符组成，字符的类型char，7位ascii，16位Unicode编码。

不可变性：String对象不可变。

索引：String类中的charAt()。

长度：String类中的length()。

子字符串：subString()。

字符串的连接：StringBuilder，toString，+运算符。

字符串的表示：字符数组和Java字符串。char[] a，new String(a)；String s，s.toCharArray()。

字符串排序

利用字符串的特殊性质将字符串键排序的方法。

第一类方法：从右至左检查键中的字符，低位优先Least-Significant-Digit-First，LSD，使用数字代替字符，如果将一个字符串看做一个256进制的数字，那么从右向左检查字符串就等于先检查低位的最低位。这种方法最适合用于键的长度都相同的字符串排序应用。

第二类方法：从左至右检查键中的字符，高位优先，MSD，吸引人之处在于不一定需要检查所有的输入就能够完成排序。

键索引计数法：将N个键为0至R-1之间的整数的元素需要访问数组11N+4R+1次。

初始化数组会访问数组N+R+1，在第一次循环中，N个元素都会让计数器加1，访问数组2N次，第二次循环会进行R次假发，访问数组2R次，第三次循环会使计数器的值增大N次并移动N次，访问数组2N次。所有的移动操作，都维护了等键元素的相对顺序。

int N = a.length;

String[] aux = new String(N);

int[] count = new int(R+1)

//计算频率

for(int i = 0;i<N;i++)

count[a[i].key()+1]++;

//将频率转化为索引

for(int r = 0;r<R;r++)

count[r+1]+=count[r];

//将元素分类

for(int i = 0;i<N;i++)

aux[count[a[i].key()]++]= a[i];

//回写

for(int i = 0;i<N;i++)

a[i]= aux[i];

低位优先的字符串排序：能够稳定地将定长字符串排序。

如果字符串的长度都为W，那就从右向左以每个位置的字符作为键，用键索引计数法将字符串排序W遍。倒序保证排序的稳定性。

public class LSD {

publicstatic void sort(String[] a,int w) {

//通过前W个字符将a[]排序

intN = a.length();

intR = 256; //字符串ascii7位。以char的int值来作为编号顺序

Stirng[]aux = new String[N];

for(intd = W-1;d>=0;d--) {

int[]count = new int[R+1];

//计算出现频率

for(inti = 0;i<N;i++) {

count[a[i].charAt(w)+1]++;

}

//将频率转换为索引

for(intr = 0;r<R;r++) {

count[r+1]+=count[r];

}

//将元素分类

for(inti = 0;i<N;i+=) {

aux[count[a[i].charAt(d)]++]= a[i];

}

//将元素还原

for(inti = 0;i<N;i++) {

a[i]= aux[i];

}

输入排序结果

43ABCE 23AADF

23ABDF 23ABDF

23AADF 43ABCE

对于基于R个字符的子母表的N个以长为W的字符串为键的元素，低位优先的字符串排序需要访问~7WN+3WR次数组，使用的额外空间与N+R成正比。

高位优先的字符串排序

对于长度不一的字符串，我们可以一般从左到右的进行排序。首先用键索引计数法按照首字母排序，然后递归地再将每个首字母对应的字数组排序，忽略首字母，因为首字母都是一样的，它将数组切分为能够独立排序的字数组来完成任务，但它的切分会为每个首字母得到一个字数组。

输入输出

she are

shells by

seashells seashells

by seashells

the seashore

seashore shells

the shells

shells she

she she

sells shells

are surely

surely the

seashells the

对子字符串末尾的约定

将所有字符都已经被检查过的字符串所在的字数组排在所有子数组的前面，这样就不需要递归地将这个字数组排序。

将字符串中的字符索引转化为数组索引，当指定的位置超过了字符串的末尾时，该方法返回-1，然后所有的返回值加1，得到一个非负的int值，并用它作为count[]索引。这种转化意味字符串中的每个字符都可能产生R+1种不同的值：0表示字符串的结尾，i表示第i个字符。因为键索引计数法本身需要一个多余的位置，所以int count[] = new int[R+2]，创建记录频率的数组，count[]数组中的值在统计频率、转换为索引并将数据分类后，它正是每个字符所对应的字数组排序时所需要的位置。

自己的理解：

字符串数值 String[] a

字符串长度N = a.length

置换字符串数值String[] aux

键值索引int count[R=256+2]

count[0]=0的存在便于count[i]=count[i]+count[i-1]计算频率的统一性

count[1]用来存放长度不够的字符串个数。比如计算[ab][a] [ad]计算到第二个字符时，[a]没有对应的，这样的应该存放到前面，则将其存放在第一个count[1]中，得到优先排。

input

dcf

acd

sort(a,lo,hi,d)

d从第一个(d=0)慢慢递增到字符串最长来排序。

第一次排序后，得到经过键值排序的新的String[] a，这里按照首字母a,b,c拍下去，如果这样的首字符存在的话。

acd

dcf

接着递归地调用sort

简化地将键值从0-R全部都递归，如果那些字数组字符串中的首字母不在的话，也递归进去，不在则在终止递归中进行操作。

第d个

第一步：频率

第二步：索引

第三步：分类

第四步：回写

http://grepcode.com/file/repo1.maven.org/maven2/com.googlecode.princeton-java-algorithms/algorithms/4.0.1/edu/princeton/cs/algorithms/MSD.java

http://lixinzhang.github.io/string-sorts-zi-fu-chuan-pai-xu.html

String Sorts 字符串排序

对字符串的排序，主要涉及一种count技术，即根据字符的有限性通过计数的方式来划分rerank的位置。

LSD string sort

原理

LSD算法是典型的针对固定长度字符串排序的方法，如对IP地址，账号的排序。
主要的的思想，从右向左，对每个位置的字符进行rerank。
rerank, 采用一个counter记录每个字符所对应字符串rerank后的起始位置。这个方法有小技巧和逻辑性，值得一读。Pay attention!

特性

LSD是稳定的排序算法
LSD算法需要使用7WN+3WR的数组访问以及N+R的内存空间。W为key string的长度，N为待排序元素个数，由于实际应用中R远远小于N，因此近似时间复杂度为WN。

Source Code

void LSD_sort(string arr[], int N, int W) {
const int R = 256;
string * aux = new string [N];
for(int i=W-1; i>=0; i--){
int counter[R] = {0};
for(int j=0; j<N; j++){
counter[arr[j][i]+1] += 1;
}
for(int j=1; j<R; j++){
counter[j] += counter[j-1];
}
for(int j=0; j<N; j++){
aux[counter[arr[j][i]]++] = arr[j];
}
for(int j=0; j<N; j++){
arr[j] = aux[j];
}
}
delete [] aux;
}

MSD string Sort

MSD is most-significant-digit-first.

原理

MSD主要解决当字符串长度不一致时的，更普遍的的字符串排序问题
与LSD不同，MSD方法从左向右进行比较，并且每次比较都会将原字符串序列分成多个partition。然后对每个patition再进行子问题求解。
MSD仍需要借助count技术，对不同的字符串进行划分。但存在一个问题，因为利用count技术的时候，需要访问R数组访问，但与长度已经很小的子序列而言是不值得的，因此对于小长度的子问题，直接采用朴素的插入排序求解。

特性

MSD主要针对不同长度的字符串，因此当有字符串到达末尾的时候，即C++/C中的\0时，由于accsi码值为0，因此具有高优先级，使得其自然排序上升。
MSD算法会耗费非常多的内存空间，因为在应用 count方法时，count数组不能放在外面作为类成员变量共享（辅助数组aux则可以）。
MSD的算法效率与输入数据非常相关，如若第一列就可以很好的区分开256个部分，那么一次就完成了排序；最差的情况是，数组里的所有字符串都相等，那么就不得不一直走到队尾。
MSD需要8N+3R ~ 7wN+3WR之间的数组访问次数。其中w为平均的字符串长度。

字符串之排序

Source Code

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

class MSD{
public:
static void sort(string arr[], int size);
static void sort(string arr[], int lo, int hi, int d);
static void insertSort(string arr[], int lo, int hi, int d);
public:
static string * aux;
static int * a;
const static int R;
const static int M; //cutoff for small subarrays
};


const int MSD::R = 256;
const int MSD::M = 0;
string * MSD::aux = NULL;

void MSD::sort(string arr[], int size){
if(size <= 1) return;
MSD::aux = new string[size];
sort(arr, 0, size-1, 0);
}
void MSD::sort(string arr[], int lo, int hi, int d){
if(lo >= hi) return ;
if(hi<lo+M){
insertSort(arr, lo, hi, d);
return ;
}
int count [R+1] = {0};
for(int i=lo; i<=hi; i++){
count[arr[i][d] + 1] ++;
}
for(int r=1; r<R+1; r++){
count[r] += count[r-1];
}
for(int i=lo; i<=hi; i++){
aux[count[arr[i][d]]++] = arr[i];
}
for(int i=lo; i<=hi; i++){
arr[i] = aux[i-lo];
}
for(int r=0; r<R; r++){
MSD::sort(arr, lo+count[r], lo+count[r+1]-1, d+1);
}
}

void MSD::insertSort(string arr[], int lo, int hi, int d){
for(int i=lo+1; i<=hi; i++){
for(int j=i; j>lo; j--){
if(arr[i][d] > arr[j][d]){
swap(arr[i], arr[j]);
}
}
}
}

int main(){
//MSD::R = 10;
string arr[] = {"she", "sells", "seashells", "by", "the", "sea",
"shore", "the", "shells", "she", "sells", "are", "surely", "seashells"};
int len = 14;
MSD::sort(arr, len);
for(int i=0; i<len; i++)
cout<<arr[i]<<endl;
return 0;
}

Three-way string quicksort

原理

参考MSD方法的思想，很容易想到一种基于partition的排序方法——quick sort.
我们可以按照每个位置的字符作为比较元素，然后划分为3个partition。根据之前所了解的三路快排，我们知道中间的那份partition包含的元素是相同的，因此在进行子问题递归的时候，比较元素的位置+1。而另外两个，则继续在该位置上进行子问题计算。

特性

时间赋值度约定于2NlnN

源代码

class Quick3string{
public:
static void sort(string arr[], int size){
sort(arr, 0, size-1, 0);
}
static void sort(string arr[], int lo, int hi, int d){
if(lo>=hi) return;
int lt = lo, gt = hi;
int v = arr[lo][d];
int i = lo+1;
while(i<=gt){
int t = arr[i][d];
if(t<v) swap(arr[lt++], arr[i++]);
else if (t>v) swap(arr[i], arr[gt--]);
else i++;
}
sort(arr, lo, lt-1, d);
if(v>=0) sort(arr, lt, gt, d+1);
sort(arr, gt+1, hi, d);
}
};

Conclution

字符串之排序

« 斐波那契数列及尾递归
区间形DP »

Comments

秒客网

字符串之排序

String Sorts 字符串排序

LSD string sort

原理

特性

Source Code

MSD string Sort

原理

特性

Source Code

Three-way string quicksort

原理

特性

源代码

Conclution

相关文章