线性表的应用--箱子排序(桶排序)和基数排序

箱子排序

箱子排序的思想简单而言就是分配range(比如0,9,range=10)个箱子,然后把每个相同的元素放入一个箱子,最后把箱子连接起来得到新的有序的线性表。箱子排序是一种稳定排序,它不会改变排序前线性表中相同元素的相对次序。
虽然可以用数组来表示箱子,但是涉及到箱子的合并(链表的合并操作为Θ(1)),我们使用单向链表来实现使其更高效。单向链表的定义实现见线性表–单向链表的C++描述。
用于箱子排序的一个结构体例子
因为使用到我们定义的链表,因此用于箱子排序的类型T必须实现对成员函数operator size_t()和bool operator!=()运算符的重载。另外我们还需要对类型T实现operator<<运算符的重载。

//========================箱子排序========================
//用于排序的一个结构体例子
//链表中的T必须拥有定义的 operator int() 和 operator!= 和 opeartor<<的重载操作
struct studentRecord{
	studentRecord(string _name,int _score):name(_name),score(_score){ }

	string name;//学生姓名
	int score;//学生成绩
	operator int()const {//将类转换成int用于箱子排序
		return score;
	}
	bool operator!=(const studentRecord& rhs)const {
		return score != rhs.score;
	}
};
std::ostream& operator<<(std::ostream&os, const studentRecord& sr) {
	os << "student name:" << sr.name << " socre=" << sr.score << endl;
	return os;
}

使用链表的多个方法进行箱子排序

//=======================binSort=======================
//用链表的多个方法进行箱子排序
template <typename T>
void binSort(myExtendedChainList<T>& chain, size_t range) {
	typedef T value_type;
	//对箱子按照基数range初始化
	myExtendedChainList<T>* bin = new myExtendedChainList<T>[range + 1]();//箱子范围[0,range]
	//把待排序链表逐个取出,放入对应的箱子中
	size_t nodes = chain.get_size();
	for (size_t i = 0; i < nodes;++i) {
		value_type _element = chain.get_element(0);//每次读取首节点
		chain.erase(0);//每次删除首节点
		bin[size_t (_element)].push_back(_element);//放入对应的箱子中 注:T必须支持size_t operator()类型转换操作
	}
	//再把箱子中的节点链接成有序链表
	for (size_t i = 0; i < range + 1;++i) {
		while (!bin[i].empty()) {//当前箱子中有节点
			value_type _element=bin[i].get_element(0);
			bin[i].erase(0);
			chain.push_back(_element);
		}
	}
	delete[] bin;
}

如果我们在乎效率,我们可以注意到,把binSort定义为链表的一个成员函数就可以省略很多操作(如不断inser/erase带来的new/delete操作),提高效率且节省空间。
将箱子排序作为链表的一个成员方法

//=======================成员函数myExtendedChainList<T>::binSort======================
template <typename T>
void myExtendedChainList<T>::binSort(size_t range) {
	//相较于非成员函数binSort而言 将其定义为成员函数效率更高 所耗空间更小
	//非成员函数版本binSort需要分配range+1个链表对象的内存 且每个链表(对应一个箱子)都可能要在insert时执行new操作
	//		在erase时执行delete操作 影响空间和效率
	//而作为成员函数的话 只需要在排序时分配2*range的指针内存 [0,range]中的每个箱子都有两个指针top/bottom
	//		每对top/bottom用于指向当前箱子中的链表的起始节点 无需new/delete 只需更改原始链表的连接顺序得到有序的多个子链表
	//		每个箱子里面的节点是有序的(且元素值相等的)


	myChainNode<T>** top = new myChainNode<T>*[range+1];//指向当前range(箱子)的最后一个节点
	myChainNode<T>** bottom = new myChainNode<T>*[range+1];//指向当前range(箱子)的第一个节点
	for (size_t i = 0; i < range + 1;++i) {
		top[i] = bottom[i] = nullptr;//都初始化为空指针
	}
	
	//把链表的节点分配到箱子中
	for (; firstNode != nullptr; firstNode = firstNode->next) {
		T _element = firstNode->element;
		size_t binNo =_element;//将元素T转换成size_t对应箱子的序号
		if (bottom[binNo] == nullptr)	//当前箱子为空
			bottom[binNo] = top[binNo] = firstNode;
		else {//当前箱子不为空
			top[binNo]->next = firstNode;
			top[binNo] = firstNode;
		}
	}

	//把箱子中的节点收集到有序链表
	myChainNode<T>* nodePtr=nullptr;//节点指针
	for (size_t i = 0; i < range + 1;++i) {
		if (bottom[i]!=nullptr) {//当前箱子有节点
			if (nodePtr == nullptr)	//第一个非空箱子
				firstNode = bottom[i];
			else //不是第一个非空箱子 则nodePtr指针一定指向上个有节点元素的箱子的top(也就是箱子中最后一个节点)
				nodePtr->next = bottom[i];
			nodePtr = top[i];//nodePtr指针指向当前箱子的top(也就是箱子中的最后一个节点)
		}
	}
	if (nodePtr != nullptr)	//排序完成
		//将最后一个箱子中最后的节点的next置空 避免部分节点形成环形链表
		//(因为排序后最后一个节点可能不是原链表的最后一个节点,没有在排序中重新赋值它的next而仍然指向原链表中它的后继节点)
		nodePtr->next = nullptr;
		
	delete[] top;
	delete[] bottom;
}

测试

#include <random>
#include <ctime>
int main() {
	//std::default_random_engine e(time(0));
	std::default_random_engine e;//不使用种子方便调试
	std::uniform_int_distribution<int> u(0,10);//成绩测评在0-10 一共11个等级  range[0-10]
	myExtendedChainList<studentRecord> chain;
	for (size_t i = 0; i < 30;++i) {//模拟一个班的成绩
		chain.push_back(studentRecord(std::to_string(i+1),u(e)));
	}
	//cout << chain << endl;
	//binSort(chain,10);	//调用非成员函数版本的排序
	chain.binSort(10);		//调用成员函数版本的排序
	cout << chain << endl;
	return 0;
}

结果截图:
在这里插入图片描述

基数排序

基数排序是对箱子排序的一种扩展。与箱子排序不同,基数排序不直接对原数字排序,而是把原数字按照基数(radix)进行分解。例如把985按照十进制基数10分解为9、8、5(985=9*10 2 + 8*10 1 + 5*10 0),然后分三次依此对5、8、9进行排序。这就是基数排序的思想。它仅在Θ(n)的时间内,就可以对0~n c-1(c>=0,整数常量)之间的n个元素进行排序。箱子排序可以看做基数为radix=range的基数排序。
基数排序的基础是基于箱子排序的稳定性(不改变原始线性表中相同值元素的相对次序)。我们可以先对低位次(即个位)排序,使所有元素按照个位数字排列。然后再对十位进行排序,得到的序列在十位数字相同的情况下,它们的个位数字保持有序。然后再对百位进行排序,得到的序列在百位数字相同的情况下,它们的十位、个位数字保持有序……直到排序完成。
例如我们要对0~10 6-1的1000个整数排序,如果使用箱子排序则基数range=radix=10 6,我们要分配10 6个箱子来装这1000个整数,无论是时间效率还是空间效率都是不可取的。这时我们将基数设定为radix=10,则只需要进行6次range=radix=10的箱子排序即可。依此次调用chain.binSort(range%10)(对个位排序),chain.binSort((range%100)/10)(对十位排序),chain.binSort((range%1000)/100)(对百位排序)……

另外,线性表也可以应用在并查集算法(在线等价类)中。并查集问题也称为在线等价类问题,简单而言就是初始时有n个元素,每个元素都属于一个独立的等价类,需要执行的操作有1.combine(a,b),把包含a和b的等价类合并成一个等价类 2.find(element)确定元素element在哪一个类。但是基于线性表效率不是最高的,基于树结构的并查集解决方案效率更快。离线等价类的问题是确定所有的等价类,其解决方案一般基于栈结构。

代码交流 2020