三向字符串快速排序

谁借莪１个温暖的怀抱￠ 2022-06-13 12:53 157阅读 0赞

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

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

--------------------

## 1.三向字符串快速排序算法 ##

MSD对包含大量重复键的字符串进行排序时，效率十分低下。三向字符串快速排序可以很好的解决这个问题，其是MSD和快速排序的结合版。

三向字符串快排有两个标记，第一个标记`lt`指向字符串集合开始位置，第二个标记`gt`指向字符串结束位置。首先选出第一个字符串作为切分字符串，然后从开始位置向后遍历字符串集合，如果当前字符串键值比切分字符串键值小，将当前字符串和`lt`所指向的字符串交换，然后比较下一个字符串；如果当前字符串键值和切分字符串键值相等，不做处理，直接比较下一个字符串；如果当前字符串键值比切分字符串键值大，将当前字符串和`gt`所指向的字符串交换，然后继续比较当前字符串，因为后面的字符串到底大还是小并不知道。

该轮遍历将字符串分为了三份，分别是键值小于切分字符串部分，键值等于切分字符串部分，键值大于切分字符串部分。将这三部分分别进行上述的三向切分比较，不同的是小于和大于部分的键值位不变，而相等部分的键值位向后移一位，如下图所示：   
![77253119.jpg][]

## 2.三向字符串快速排序实现 ##

#include "stdafx.h"
    #include <iostream>
    #include <fstream>
    #include <VECTOR>
    #include <STRING>
    
    using namespace std;
    
    void swap(vector<string>& a, int m, int n)
    {
        string temp = a[m];
        a[m] = a[n];
        a[n] = temp;
    }
    
    int charAt(const string& str, int d)
    {
        if ( d < str.size() )
            return str[d];
        else 
            return -1;
    }
    
    void quick_3_string(vector<string>& sVec, int lo, int hi, int d)
    {
        if (hi<=lo)
            return;
        int lt = lo, gt = hi;
        int v = charAt(sVec[lo], d);
        int i = lo + 1;
        while (i<=gt)
        {
            int t =  charAt(sVec[i], d);
            if (t < v) swap(sVec, lt++, i++);
            else if ( t > v) swap(sVec, i, gt--);
            else i++;
        }
    
        quick_3_string(sVec, lo, lt-1, d);
        if (v >=0 )
            quick_3_string(sVec, lt, gt, d+1);
        quick_3_string(sVec, gt+1, hi, d);
    }
    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();
        quick_3_string(sVec, 0, n-1, 0);
    
        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
      
     
      
       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

*  和MSD类似，使用了`charAt`函数，当字符串结束时返回`-1`
 *  `lt`始终指向键值和v相等的第一个字符串，`gt`始终指向键值和v相等的最后一个字符串
 *  在小型子数组中使用插入排序，可以显著地提升排序效率

## 3.总结 ##

*  三向字符串快速排序是不稳定排序
 *  三向字符串快速排序时间复杂度为O(N)~O(NlogN)
 *  三向字符串快速排序空间复杂度O(logN)
 *  三向字符串快速排序特别适合大量重复键的字符排序，如域名

[77253119.jpg]: http://7xn9xp.com1.z0.glb.clouddn.com/16-3-3/77253119.jpg