重学「冒泡排序」

PAT里链表题有各式各样的骚操作。这些非常规操作易学易用，但是习惯了这些后，反而对题目真正想考察的知识生疏了。今天就碰到一道这样的题，想用正经的算法写却写不出来。希望大家以我为戒，不要过多的学习这些「奇技淫巧」

Linked List Sorting这道题很常规，是个很一般的链表排序题。链表不能随机访问，因此算法上的选择限制很大，只有冒泡、插入、选择排序可以选。我选了冒泡练手，没想到没做出来。

冒泡排序的关键步骤是交换两个相邻的逆序元素。每完成一趟后都有一个元素被顺利的放到了最终位置上。

按我的想法，i in (0,n),j in (i+1,n)，每次j走到n时，就把「最小」的元素放到了i的位置，依次增加i就得到了升序排列。很遗憾，这是错的

1
2
3
for (int i = 0; i < n; i++)
	for (int j = i + 1; j < n; j++)
		if (n[j] < n[j-1]) swap(n[j], n[j-1]);

在[5,3,1,2,6,7]上考虑这段代码，if语句能保证，只要n[j]比n[j-1]大，就把这个大的往后移。。而对于最小值1，仅仅在j=2的时候被swap到了n[1]，并没有真正的移动到n[0]这个我所期待的位置。观察j扫描的方向也是向后的。

再看另一种写法

1
2
3
for (int i = 0; i < n; i++)
	for (int j = n-1; j > i; j--)
		if (n[j] < n[j-1]) swap(n[j], n[j-1]);

这时if语句能保证的是只要n[j]比n[j-1]小，就把这个小的往前移。在[5,3,1,2,6,7]，第一轮之后1就被放在了n[0]上。注意到j的移动方向是向前的。

我们想得到升序的序列，那么就要把大的往后移，小的往前移。j从前往后移动的过程中，我们是把最大的元素往后移一位，在下一次比较时最大的元素还会继续被移往后方，最终放在a[n-1]同理，j从后往前的过程中，最小的元素会被一直前移，直到a[0]。

因此一趟完成后到底是最大的元素被放到最后了还是最小的元素被放到最前了，要看j移动的方向。在链表中从前往后是方便的，因而最大的元素会被先放到最后。所以我们需要做的是，每一趟减少j移动结束的范围。

想到这里基本上就能理清了。加上处理头节点的一些细节后，不难写出代码

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
53
54
55
56
57
58
59
60
61
62
63
#include "cstdio"
#include "vector"
using namespace std;
struct node {
	int addr;
	int key;
	int next;
};
vector<node> nodes = vector<node>(100086);
int main()
{
	int n, head;
	scanf("%d %d", &n, &head);
	for (int i = 0; i < n; i++)
	{
		int addr, key, next;
		scanf("%d %d %d", &addr, &key, &next);
		nodes[addr] = node({ addr,key,next });
	}
	int newHead = head;
	int end = -1;
	while (end != newHead)
	{
		int t = newHead;
		int pre = -1;
		while (nodes[t].next != end)
		{
			int next = nodes[t].next;
			if (nodes[t].key > nodes[next].key)
			{
				if (pre != -1)
					nodes[pre].next = next;
				else
					newHead = next;
				nodes[t].next = nodes[next].next;
				nodes[next].next = t;
			}
			pre = t;
			t = next;
		}
		end = t;
	}
	int h = newHead;
	int cnt = 0;
	while (h != -1)
	{
		cnt++; h = nodes[h].next;
	}
	if (cnt == 0)
		printf("0 -1\n");
	else
		printf("%d %05d\n", cnt, newHead);
	h = newHead;
	while (h != -1)
	{
		if (nodes[h].next == -1)
			printf("%05d %d -1\n", nodes[h].addr, nodes[h].key);
		else
			printf("%05d %d %05d\n", nodes[h].addr, nodes[h].key, nodes[h].next);
		h = nodes[h].next;
	}
	return 0;
}

欢天喜地的去提交，发现有一个点超时了。诚然，冒泡排序的时间复杂度是Θ(n^2)，非常规操作里用std::sort处理后输出的时间复杂度是Θ(nlogn)，超时是理所应当。放眼望去绝大多数AC的代码都用的与这种投机取巧的方法。不知道这是不是违背出题人的初衷呢？

当然，这问题轮不到我评头论足，我只是个连冒泡排序都忘得一干二净的渣渣🙂

总结：

  • 冒泡排序一趟后被放到最终位置的元素与扫描方向有关
  • 基本功要打扎实，切忌「眼高手低」
PAT
prev： next：