高位优先的(通用)字符串排序(MSD) -- C++实现


本算法基于键索引计数法,从左往右根据单个字符排序 对字符串的长度无要求,是一个通用的排序算法

实现代码

// MSD.h

#ifndef MSD_H
#define MSD_H

#include "Component.h"

namespace jay{

	class MSD
	{
	public:
		// 从左往右根据单个字符排序 对字符串的长度无要求
		static void Sort(string a[],int nSize)
		{
			string *aux = new string[nSize]();
			Sort(a, 0, nSize-1, 0, aux);

			delete []aux;
			aux = nullptr;
		}

		static void Sort(string a[], int lo, int hi, int d, string aux[])
		{
			// 如果数组的大小小于CUTOFF 就直接调用insertion来排序 否则会进入下面递归排序过程
			// 以第 d 个字符为标准将a[lo]-a[hi]排序
			if (hi <= lo + CUTOFF) 
			{
				Insertion(a, lo, hi, d);
				return;
			}

			// 第一步 计算频率
			int *count = new int[R+2]();     //分组 扩展的ascii字符表有256个可显示字符  如果是unicode就是65536+2
			for (int i = lo; i <= hi; i++) 
			{
				int c = CharAt(a[i], d);
				count[c+2]++; 
			}     

			// 第二步 将频率转化为索引
			for (int r = 0; r < R+1; r++)
				count[r+1] += count[r];

			// 第三步 数据分类(排序)
			for (int i = lo; i <= hi; i++) 
			{
				int c = CharAt(a[i], d);
				aux[count[c+1]++] = a[i];
			}

			// 第四步 回写 这样 a[lo]-a[hi] 就以第 d 位做了排序
			for (int i = lo; i <= hi; i++) 
				a[i] = aux[i - lo];

			// 递归地以每个字符为分组,然后以d+1为键进行排序
			for (int r = 0; r < R; r++)
			{
				Sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux); 
			}

		}

		static void Insertion(string a[], int lo, int hi, int d) 
		{
			// 遍历数组的元素
			for (int i = lo; i <= hi; i++) 
				for (int j = i; j > lo && Less(a[j], a[j-1], d); j--)
				{
					ExchangeArrayElements(a, j, j-1);
				}
					
		}

		static bool Less(string v, string w, int d) 
		{
			int iShortLength = min(v.length(), w.length());

			// v在数组后 w在数组前

			// 当前比较的位置,已经超过较短字符串的结尾
			if (d >= iShortLength)
			{
				// 如果长度较短的字符串在前面,返回false,否则返回true
				if (v.length() > w.length())
					return false;
				else
					return true;
			}

			for (int i = d; i < iShortLength; i++) 
			{
				int a = v.at(i);
				int b = w.at(i);

				// 如果是大写字母,转化为小写
				if (a >= 'A' && a <= 'Z')
				{
					a = a + 32;
				}

				// 如果是大写字母,转化为小写
				if (b >= 'A' && b <= 'Z')
				{
					b = b + 32;
				}

				// v 的i小于w的i
				if (a < b) 
					return true;
				// v 的i大于w的i
				else if (a > b) 
					return false;
				// v 的i等于w的i
				else 
				{
					//已到达长度较小字符串的最后以为
					if (i+1 == iShortLength)
					{
						// 如果长度较短的字符串在前面,返回false,否则返回true
						if (v.length() > w.length())
							return false;
						else
							return true;
					}
				}

			}

		};

		static int CharAt(string s, int d) 
		{
			if (d == s.length()) 
				return -1;

			// 如果是大写字母,则返回对应小写字母的十进制数
			if (s.at(d) >= 'A' && s.at(d) <= 'Z')
			{
			   return s.at(d) + 32;
			}
			else
			{
				return s.at(d);
			}

//			return s.at(d);
			
		}

	private:
		static int CUTOFF;
		static int R;
	};

	int MSD::CUTOFF = 2; // 指定使用插入排序的数组大小
	int MSD::R = 256;     // 符号表的大小
};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include "Component.h"
#include "MSD.h"

using namespace jay;

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

int main(int argc, char* argv[])
{
	string arrayt[100] = {"1","4523","ads","234","66","c1","e4523","qads","0234","166","DDDD","dddd"};

	PrintArray(arrayt,12);

	MSD::Sort(arrayt,12);

	PrintArray(arrayt,12);

	cout <<endl;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。