外排序

由于内存有限，我们需要把外存的数据分成好几段，然后把这些段数据分别排序

这些已排序的段称为顺串

假设有m个顺串，每次对k个顺串进行归并

那么需要归并次，为了提高效率，一个是降低顺串的个数，另一个就是增加归并的k

1.置换选择排序

假设我们有超过内存的数据要进行排序，假设内存为c，那么每次得到长度为c的初始顺串 那么，有没有办法增加顺串的长度呢，可ff以考虑用堆来实现 假设我们要求从小到大排序，那么维护一个长度为c的最小堆，可以得到多长的顺序串呢？ 每次取堆顶的时候，如果堆顶元素大于已经在输出缓存区的元素，那么就可以取，否则我们就不应该取，这样会破坏已经有序的输出缓存区，那么这时候，我们就只能取堆中剩下的元素， 我们把不能取的那个元素丢到最后，然后继续维护堆，这时候堆的长度为c-1，直到有c个都不能取的元素 由于取每个元素大于输出缓存区的元素的概率是1/2,那么这个顺串的期望长度是2c 这样就扩大了读取的顺串长度，平均扩大了两倍

用到的堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

//堆其实就是一个顺序存放的二叉树
class Minheap {
public:
	int* heap;
	int Maxsize;
	int size;
	Minheap(int heapsize)
	{
		size = 0;
		Maxsize = heapsize;
		heap = new int[Maxsize];
	}
	~Minheap()
	{
		delete[]heap;
	}
	void Siftup(int index) //适用于添加元素的时候，调整添加元素的那一条路径
	{
		while (index > 0)
		{
			int parent = (index - 1) / 2;
			if (heap[index] >= heap[parent]) break;
			swap(heap[index], heap[parent]);
			index = parent;

		}
	}
	//调整堆（使用于删除元素的时候，向下调整）
	void Siftdown(int index)
	{
		while (index < size / 2)
		{
			int lchild = index * 2 + 1;
			int rchild = index * 2 + 2;
			int smallest = lchild;
			if (lchild < size && rchild < size)
			{
				smallest = heap[lchild] < heap[rchild] ? lchild : rchild;

			}
			if (heap[index] > heap[smallest]) swap(heap[index], heap[smallest]);
			index = smallest;
		}
	}
	void push(int val)
	{
		if (size == Maxsize) return;
		heap[size] = val;
		Siftup(size);
		size++;
	}
};

实现堆之后，就可以介绍我们的置换选择算法了

置换选择算法的步骤包括

1.初始化堆

假设内存大小是ram个int

这时候要分类，如果读取的数据小于等于ram个，那么直接就是内排序了，直接堆排序

如果读取的数据大于ram，那么就先读取ram个数据，初始化最小堆

2.继续读取，直到堆为空

此时已经有一个堆顶，就是ram中最小的，我们输出，那么这时候堆空出一个

我们继续读取，分两种情况

如果下一个元素大于等于输出缓存区的，那么就可以进堆，我们直接放到堆顶，然后往下调整，因为这时候堆顶空了，直接放在堆顶是最方便的

如果小于的话，不能进堆，因为这样就会破坏有序结构，但是我们总不能把这个数据丢了吧，所以只能把堆的大小缩小一个，然后把这个元素放到最后，然后我们把最后一个元素放到堆顶，为什么是最后一个元素呢，我们主要是不想破坏已经形成堆的子树，所以我们要选择叶子结点放到堆顶，那叶子结点很多，为什么是最后一个呢，因为如果选择其他叶子节点，为了保持完全二叉树的顺序结构，就需要把后面的补上去，比如选择6这个位置，如果放到堆顶，那5-7之间就断开了，这样就需要把7后面的都往左平移一个，这就需要很大的开销，所以选择最后一个是最好的

那么总有一天堆会为空，那么这时候，我们就完成了一个顺串，而新的这些元素又填满了ram，我们调整一下堆，这就又回到了步骤1

2.二路归并

经过前面的选择置换排序，我们得到了若干个有序的顺串

那么，如何将这些顺串合并呢？

一个简单的思路是，每次从比较这些顺串的第一个，选最小的，然后不断循环

但这样无疑非常耗时，假设有m个顺串，那么选第一个最小的就需要m-1次比较，最坏的情况是顺串本来就排好顺序，那么假设第一个顺串有个元素，则前个全是从第一个取的，顺串个数没有变少，所以每个都要次比较，总共需要 由于 所以 那么 即 显然时间复杂度是，和顺串的个数平方有关，如果我们考虑的是总个数n的话，假设有k个顺串

那么时间复杂度就是 显然n大于k，不过这样看上去有比小的错觉

那么这样显然不好，我们可以考虑两两合并

假设两个顺串的长度为m_1,m_2

那么合并的时间复杂度就是

那么这样的话，每个元素都经过了次移动，所以时间复杂度来到了

然后合并完的会进入下一轮，那么这就是一个带权重的路径问题

我们可以用Huffman树，让长度长的尽量在上层

这样就可以优化到,而且常数比上面的小

三、k路归并-选择树

由于二路归并的轮数比较多，需要多次读取硬盘，可以

提高每次归并的个数

我们思考一下，比较n个数，一共需要n-1次两两比较，

败者树是一个完全二叉树，如果有n个叶子结点，那么就有n-1个内部结点

那么显然，我们可以把内部节点作为比较结果，n个叶子结点是比较的对象

我们用Data数组存放叶子结点，Loser数组存放败方（也就是内部结点）

我们要用Loser数组的第0个存放最后的结果，所以两个数组的长度都是n

显然Data数组的结点索引加上n-1,就是二叉树里的位置

那么它的父节点就是 但是又由于开头那个0，所以加上1，那也就是 首先先初始化一个败者树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void adjust(int index) //调整index所在路径
{
	int parent = (index + Segmentnum) / 2;
	//即使是败者树，我们也要维护赢者
	int winner = index;
	while (parent > 0)
	{
		if (Loser[parent] == -1)
		{
			swap(winner, Loser[parent]);
			break;
		}//初始化直接让输者是自己就行
		else //比较当前index的数据和输者的数据，如果更大，由于我们默认index是赢者，所以交换一下就行了
		{
			if (Data[winner].front() > Data[Loser[parent]].front())
			{
				swap(winner, Loser[parent]);
			};
		}
		parent /= 2;
	}
	Loser[0] = winner; //注意这个winner只是从0-index的winner，不过只要我们把index遍历一遍
	//就是全局的winner了
}

类比堆，初始化本身其实也是一种调整，所以我们假设我们已经有一个败者树

如果一个发生变化，如何调整回复败者树的结构？

显然我们顺着变化的index往上调整就是了，因为只影响了这条路径，winner记录当前的胜者

先假设变化的那个值是胜者，然后和父节点比，如果输了就交换

从这里也可以看出败者树比堆的比较次数少，因为堆要和兄弟节点和父节点比，需要比两次

同时胜者树因为需要维护胜者，无论输赢，都需要更新父节点，因为我不知道之前的父节点赢得是谁，发生变化之后，如果比父节点小，如果父节点是原来的这个节点，那我不能确定此时他是否还是胜者，如果父节点是兄弟节点，也就是兄弟节点胜出，那么此时胜者不需要改变，但是我不知道这个父节点到底是谁，所有我都得更新，败者树只要比败者强，就不更新，无论之前的败者是谁，败者树有1/2的概率不需要更新父节点

所以败者树显然是最佳选择