三向字符串快速排序 -- C++实现


实现代码

// MSD.h

#ifndef THREEWAYQUICKSORT_H
#define THREEWAYQUICKSORT_H

#include "Component.h"

namespace jay{

	class ThreeWayQuickSort
	{
	public:
		static void Sort(string a[],int nSize)
		{
			Sort(a, 0, nSize-1, 0);

		}

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

			// lt是当前字符串集合[lo,hi]的第一个字符串  gt是当前字符串集合[lo,hi]的最后一个字符串
			int lt = lo, gt = hi;
			// 获取比较的键v a[lo].charAt(d)
			int v = CharAt(a[lo], d);
			// 从第二个开始比较
			int i = lo + 1;          
			while (i <= gt) 
			{
				// 获取当前字符串d的值 a[i].charAt(d)
				int t = CharAt(a[i], d); 

				int vTmp = v;
				int tTmp = t;

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

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

				if  (tTmp < vTmp) 
					ExchangeArrayElements(a, lt++, i++); 
				else if (tTmp > vTmp) 
					ExchangeArrayElements(a, i, gt--);   
				else        
					i++;              
			}

			// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 

			// 第一部分递归比较
			Sort(a, lo, lt-1, d); 

			// 第二部分递归比较
			if (v >= 0) 
                Sort(a, lt, gt, d+1); 
			
			// 第三部分递归比较
			Sort(a, gt+1, hi, d); 

		}

		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 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);
			}
			
		}

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

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

#endif

测试代码

//main.cpp

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

#include "Component.h"
#include "ThreeWayQuickSort.h"

using namespace jay;


int main(int argc, char* argv[])
{
	string arrayt[100] = {"166","4523","ads","234","66","c1","e4523","qads","a","1","DDDDD2","dddd","ddddd3"};
//	string arrayt[100] = {"1","she","ads","234","66","c1","e4523","qads","a","166","shes","she","shess"};

	PrintArray(arrayt,13);

	ThreeWayQuickSort::Sort(arrayt,13);

	PrintArray(arrayt,13);

	cout <<endl;
}

 

暂无评论

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