第七章 排序（桶排序）

要求

对输入的字符串进行排序

可变字符串的基数排序

代码

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
/*
* 对String类对象的数组进行基数排序
* 假设全为ASCII码
* 并设所有字符串的长度都以maxLen为界
*/
void radixSort(vector<string>& arr, int maxLen)
{
	const int BUCKETS = 256;//把字符看作256进制的数
	
	vector<vector<string>> wordsByLength(maxLen + 1);
	vector<vector<string>> buckets(BUCKETS);

	for (string& s : arr)
	{
		wordsByLength[s.length()].push_back(move(s));
	}

	int idx = 0;
	for (auto& wordList : wordsByLength)
	{
		for (string& s : wordList)
		{
			arr[idx++] = move(s);
		}
	}
	
	int startingIndex = arr.size();
	for (int pos = maxLen - 1; pos >= 0; --pos)
	{
		startingIndex -= wordsByLength[pos + 1].size();

		for (int i = startingIndex; i < arr.size(); i++)
		{
			buckets[arr[i][pos]].push_back(move(arr[i]));
		}

		idx = startingIndex;
		for (auto& thisBucket : buckets)
		{
			for (string& s : thisBucket)
			{
				arr[idx++] = move(s);
			}
			thisBucket.clear();
		}
	}
}

int main()
{
	vector<string>arr = { "We", "can", "extend", "either", "version", "of", "radix", "sort", "to", "work", "with", "variable", "length", "strings"};
	radixSort(arr, 8);
	for (string& s : arr)
		cout << s << ' ';
	return 0;
}

输入

We,can,extend,either,version,of,radix,sort,to,work,with,variable,length,strings

输出