低位优先的字符串排序(LSD) -- C++实现


注意该算法只适用长度一致的字符串

实现代码

// LSD.h

#ifndef LSD_H
#define LSD_H

#include "Component.h"

namespace jay{

	class LSD
	{
	public:
		static void sort(string a[],int nSize,int iStringLength)
		{
			int R = 256;   // extend ASCII alphabet size
			string *aux = new string[nSize](); // 同时初始化手动分配的内存块

			// 根据第d个字符用键索引计算法排序 从右往左一个一个排序
			for (int d = iStringLength-1; d >= 0; d--)
			{ 

				// 第一步 计算出现频率 
				int *count = new int[R+1](); // 同时初始化手动分配的内存块

                // 目前只能处理大写或者小写的字母,可以通过适当的增加一个At函数来处理大小写字母混合的处理
				for (int i = 0; i < nSize; i++)
					count[a[i].at(d) + 1]++; //charAt(d) + 1这里的+1对于第二步非常重要

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

				第三步 将元素分类(排序)
				for (int i = 0; i < nSize; i++)
					aux[count[a[i].at(d)]++] = a[i];

				// 第四步 回写
				for (int i = 0; i < nSize; i++)
					a[i] = aux[i];
				
				delete []count;
				count = nullptr;
			}

			delete []aux;
			aux = nullptr;
		}
	};
};

#endif

测试代码

//main.cpp

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


#include "Component.h"
#include "LSD.h"


using namespace jay;


int main(int argc, char* argv[])
{
	string arrayt[30] = {"1112","4523","adsf","1234","6666"};

	PrintArray(arrayt,5);

	LSD::sort(arrayt,5,4);

	PrintArray(arrayt,5);

	cout <<endl;
}

 

暂无评论

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