Keep and carry on.

字符串算法（一）排序

post @ 2017-05-04

概述

​ 字符串排序算法分为低位优先排序、高位优先排序、快速排序。

​ 低位优先即从字符串的低位开始向高位取每一个字符进行排序，一般用于待排序的字符串长度相等的情况；

​ 高位优先排序从高位向下排序，事先设定一个阈值，如果待排序的字符串个数小于阈值，则用插入排序的方法；

​ 快速排序则是用快速排序的原理，对每一个字符将比它小的字符移动到它的左边，将比它大的字符移动到他的右边，然后用递归的方法对两边继续进行排序。

实现

低位优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void sort(String[] a,int w){
		int len=a.length;
		String[] aux=new String[len];
		int n=127;
		
		for(int i=w-1;i>=0;i--){
			int[] count=new int[n+1];
			for(int j=0;j<len;j++){
				count[a[j].charAt(i)+1]++;
			}
			for(int j=0;j<n;j++){
				count[j+1]+=count[j];
			}
			for(int j=0;j<len;j++){
				aux[count[a[j].charAt(i)]++]=a[j];
			}
			for(int j=0;j<len;j++){
				a[j]=aux[j];
			}
		}
	}

构造一个大小为127长度的数组来分别记录出现的字符，再遍历相同位置上的每一个字符如果出现一次则加1.将这个127长度的数组进行累加，则数组中每个值与其前一位的差值为它前一个值在待排序字符串中出现的次数。

1

如图是第一轮的排序，0的asc码值为48，则数组中的49减48的个数为5.则他们每一位的值可以表示该位之前有多少个字符，即它的排列顺序。

高位优先

低位优先适用于字符串长度相同的字符串排序，高位优先适用于所有的字符串排序。高位优先一共有三个函数，分别是charAt、sort、InsertionSort。其中sort用于排序，使用递归的方法对每个字符串进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private static void sort(String[] a, int lo, int hi, int d)
    {//以第d个字符为键将a[lo]至a[hi]排序
        if(hi <= lo + M)
        {//快速排序
            InsertionSort(a, lo, hi, d);
            return;
        }
        int[] count = new int[R+2]; //计算频率
        for(int i = lo; i <= hi; i++)
        {
            count[charAt(a[i], d) + 2]++;
        }
        for(int r = 0; r < R+1; r++) //将频率转换为索引
        {
            count[r+1] +=count[r];
        }
        for(int i = lo; i <= hi; i++) //数据分类
        {
            aux[count[charAt(a[i], d) + 1]++] = a[i];
        }
        for(int i = lo; i <= hi; i++) //回写
        {
            a[i] = aux[i-lo];
        }
        //递归的以每个字符为键进行排序
        for(int r = 0; r < R; r++)
        {
            sort(a, lo + count[r], lo + count[r+1] - 1, d+1);
        }
    }

对每个字符的排序方法与低位优先的字符排序方法相同，不同点在于最后递归的代码，将前一位字符相同的字符串递归后一位字符进行排序，其中R的值为256.

1
2
3
4
5
6
7
8
9
10
11
private static int charAt(String s, int d)
    {
        if(d < s.length())
        {
            return s.charAt(d);
        }
        else
        {
            return -1;
        }
    }

charAt函数重写了String类的charAt，让字符为空的情况下，返回-1，也就是字符串长度不同的情况下，若后一位没有值了则该位在字符串排序中为0，即排在最低位。

方法中还设定了一个阈值M=3，如果字符串太少，则直接使用插入排序来提高效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//快速排序
    private static void InsertionSort(String[] a, int lo, int hi, int d) 
    {   
        for( int i = lo; i < hi; i++) 
        { 
            for( int j=i+1; j>lo; j--) 
            {               
                if( a[j-1].compareTo(a[j]) <= 0)
                {
                    break;
                }
                String temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;              
            }
        }  
    }

快速排序

与数字排序的快速排序算法相同，把每一位字符转化为数字后使用排序，再递归的思想对头字符相同的字符串进行排序，同样要构造一个charAt来使字符没有的情况下，返回-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
private static void sort(String[] a, int lo, int hi, int d)
    {
        if(hi <= lo)
        {
            return;
        }
        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo + 1;
        while(i <= gt)
        {
            int t = charAt(a[i], d);
            if(t < v)
            {
                swap(a, lt, i);
                lt++;
                i++;
            }
            else if(t > v) 
            {
                swap(a, gt, i);
                gt--;
            }
            else 
            {
                i++;
            }
        }
        sort(a, lo, lt - 1, d);     
        if(v >= 0)
        {
            sort(a, lt, gt, d + 1);
        }
        sort(a, gt + 1, hi, d);
    }
    private static int charAt(String s, int d)
    {
        if(d < s.length())
        {
            return s.charAt(d);
        }
        else
        {
            return -1;
        }
    }
    private static void swap(String[] a, int i, int j) 
    {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

快速排序的基本原理就是使用递归，选择一个值，将其它的值都按小于大于的关系移动到该值的左方或者是右方。

Read More
⬆︎TOP