高位优先字符串排序

迷南。 2022-06-13 12:52 163阅读 0赞

转自：http://blog.csdn.net/xuelabizp/article/details/50781616

本节内容总结自《算法（第4版）》5.1节

## 1.高位优先字符串排序 ##

字符串常见的排序算法有两种，分别是[低位优先（LSD）][LSD]和高位优先（MSD），低位优先从右向左检查字符，高位优先从左向右检查字符。低位优先字符串排序要求待排序的字符串长度一致，然而很多时候字符串长度并不一致，低位优先排序并不适用，此时就要用到高位优先排序或者三向字符串快排。

*  高位优先排序对于待排序的字符串没有什么要求
 *  高位优先排序的过程中使用了键索引计数算法
 *  高位优先排序要特别注意字符串达到末尾的情况，因为当字符串达到末尾时，比其本身加上任意字符都要小，如app小于apple。为了判断字符串是否已达到末尾的情况，编写字符索引函数`int charAt(const string& str, int d)`，当字符索引大于字符长度即字符串达到结尾时，返回`-1`，否则返回索引字符对应的ASCII码

高位优先排序递归进行，R表示字符串的基数（字符串中不同字符的数量）。高位优先排序将字符从左向右按照字符分区间进行排序，如待排序的字符串为:

> c   
> a   
> b   
> abc   
> ab

第一次递归按照最左边字符排序，结果为:

> a   
> abc   
> ab   
> b   
> c

然后在以a，b，c开始的字符串中，分别按照第二位排序，直到排序完毕。

注意：键索引计数一共有4个步骤，计算频率->将频率转换为索引->数据分类->回写。其中计算频率需要用到辅助数组`int count[]`，在低位优先排序中，这个数组的大小为`R+1`，加`1`是为了索引方便，而在高位优先中，还需要再加`1`，即`int count[]`的大小为`R+2`。再加`1`是当字符串达到末尾时，返回索引为`-1`，而数组的下标从`0`开始，故加1才能使用`int count[]`数组计数。此时，`count[0]`表示已达到末尾的字符串数目，`count[`1\]表示字母表中第1个字符的数目……

## 1.高位优先字符串排序实现 ##

#include "stdafx.h"
    #include <IOSTREAM>
    #include <FSTREAM>
    #include <STRING>
    #include <VECTOR>
    
    const int R = 256;
    const int M = 15;
    using namespace std;
    
    int charAt(const string& str, int d)
    {
        if ( d < str.size() )
            return str[d];
        else 
            return -1;
    }
    
    //参数分别表示字符串容器，排序字符串起始位置，排序字符串结束位置，键的位数，辅助存储容器
    void MSD_sort(vector<string>& sVec, int lo, int hi, int d, vector<string>& aux)
    {
        if (hi <= lo)
            return;
    
        int count[R+2]={
       0};
        //计算频率
        for (int i=lo; i<=hi; i++)
            count[charAt(sVec[i], d) + 2]++;//加2
        //频率转化为索引
        for (int r=0; r<R+1; r++)
            count[r+1] += count[r];
        //分类
        for (i=lo; i<=hi; i++)
            aux[count[charAt(sVec[i], d) + 1]++] = sVec[i];//一个加1隐藏在直接索引中
        //回写
        for (i=lo; i<=hi; i++)
            sVec[i] = aux[i-lo];//注意aux下标
    
        //以从左到右的每个字符为键进行排序
        for (r=0; r<R; r++)//count[R+1]为0，不对应任何字符
            MSD_sort(sVec, lo+count[r], lo+count[r+1]-1, d+1, aux);
    }
    
    int main(int argc, char* argv[])
    {
        string str;
        vector<string> sVec;
        ifstream infile("data.txt");
        cout<<"------Before sort:"<<endl;
        while (infile>>str)
        {
            cout<<str<<endl;
            sVec.push_back(str);
        }
    
        int n = sVec.size();
        vector<string> aux(n);
        MSD_sort(sVec, 0, n-1, 0, aux);
    
        cout<<"------After sort:"<<endl;
        for (int i=0; i<n; i++)
            cout<<sVec[i]<<endl;
    
        return 0;
    }
    
     
      
       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
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
      
     
      
       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
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66

测数数据如下：

> she   
> sells   
> seashells   
> by   
> the   
> seashore   
> the   
> shells   
> she   
> sells   
> are   
> surely   
> seashells

运行结果如下：   
![41538883.jpg][]

## 3.大幅度提升性能的方法 ##

在数值排序中提到过一次优化排序效率的方法：当待排序数组的长度较小时，使用插入排序。同样的，该方法也适应与高位优先字符串排序，而且这种优化一般情况下也是必须的，有专家做过实验，在数据量巨大时，将长度小于10的子数组排序切换到插入排序，可以将排序的效率提升十倍左右。

针对字符串的插入排序和[数值的插入排序][Link 1]思想一模一样，具体代码如下：

void insertion_sort(vector<string>& sVec, int lo, int hi, int d)
    {
        for (int i=lo+1; i<=hi; i++)
            for (int j=i; j>lo && charAt(sVec[j], d)<charAt(sVec[j-1], d); j--) 
            {
                string temp = sVec[j];
                sVec[j] = sVec[j-1];
                sVec[j-1] = temp;
            }
    }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
      
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10

## 4.总结 ##

*  高位优先字符串排序是稳定排序
 *  高位优先字符串排序时间复杂度为O(N)~O(Nw)，w为字符串平均长度
 *  高位优先字符串排序空间复杂度为O(N\+WR)，W为最大长度，O(N)为辅助数组占用的空间，O(WR)是W次递归中count\[R+2\]数组占用的空间
 *  高位优先字符串排序一般用于随机字符串排序，在有大量重复字符串时效率低下（此时需要三向字符串快速排序来救场）
 *  低位优先字符串排序适合定长较短字符串排序，相比于高位优先字符串排序，优势在于编写简单，否则MSD完全可以替代LSD

[LSD]: http://blog.csdn.net/xuelabizp/article/details/50715271
[41538883.jpg]: http://7xn9xp.com1.z0.glb.clouddn.com/16-3-1/41538883.jpg
[Link 1]: http://blog.csdn.net/xuelabizp/article/details/49992137