这个排序函数是如何工作的？

Question

作为我的工作的一部分，我偶尔需要评估编程职位的候选人。最近有一段代码片段传到了我的桌子上，我的第一个想法是我不确定像这样的代码是否还能够编译。但它确实可以编译，并且也能正常工作。

有人能解释一下这是为什么以及如何工作的吗？要求是提供一个函数来对五个整数进行排序。

void order5(arr) int *arr; {
    int i,*a,*b,*c,*d,*e;
    a=arr,b=arr+1,c=arr+2,d=arr+3,e=arr+4;
    L1: if(*a >*b){*a^=*b;*b^=*a;*a^=*b;}
    L2: if(*b >*c){*b^=*c;*c^=*b;*b^=*c;goto L1;}
    L3: if(*c >*d){*c^=*d;*d^=*c;*c^=*d;goto L2;}
        if(*d >*e){*d^=*e;*e^=*d;*d^=*e;goto L3;}
}

现在我能看到这种方法的缺点（对于1970年后出生的人来说缺乏可读性和可维护性），但是有人能想到任何优点吗？我不愿轻易地否定它，但在决定是否让这个人回来参加第二轮面试之前，我想知道除了作者的工作保障之外，它是否具有任何可取之处。

- paxdiablo

---

+1 有趣，最后一句让我笑出声 :) - alex

Answer 1

这是一个完全展开的冒泡排序，内联表达式中使用了XOR交换技巧。我编译了几个不同选项的代码，希望能生成一些很棒的紧凑代码，但实际上并没有什么印象深刻的地方。我加入了一些“__restrict__”关键字，以便编译器知道“*a”中的任何一个都不能与其他别名重复，这确实有很大帮助。总的来说，我认为企图的聪明已经远离了常规，因此编译器并没有很好地优化代码。

我认为这里唯一的优点就是新奇性。它确实吸引了你的注意力！如果使用更现代的技术，比如使用MMX/SSE或GPU进行排序，或者使用5个线程争相将它们的元素插入正确的位置，我会更加印象深刻。或者使用外部合并排序，以防5个元素的数组无法适应内存。

- Ben Jackson

Answer 2

xor技巧只是交换两个整数的方法。goto语句是循环的模拟。优点？除了展示你能写多么混淆的代码以外，没有任何优点。函数()后面的参数是已弃用的功能。并且手头有一个数组，并且有5个不同的指针分别指向数组的每个元素，这简直太可怕了。总之：恶心！

- Armen Tsirunyan

---

混淆？哈哈！对我来说，这个程序非常清晰。甚至比许多“非混淆”程序更清晰。如果你不懂编程技巧，可能会很难理解。 - Vovanium

Answer 3

这是一个有点混乱的 侏儒排序 实现，用于五个项目。

以下是花园侏儒如何对一排花盆进行排序。基本上，他看着他旁边和前面的花盆；如果它们按正确顺序排列，他向前移动一个花盆，否则他交换它们并向后移动一个花盆。边界条件：如果没有前一个花盆，他向前移动；如果他旁边没有花盆，他就完成了。

"向前移动一个花盆" 是通过落入下一个 if 来实现的。每个异或交换后紧接着的 goto 执行 "向后移动一个花盆"。

- Nietzche-jou

Answer 4

你不能仅凭这样的回答就轻易地驳回某个人。也许这是以玩笑的口吻提供的。

这个问题非常人为，促使出现了勉强的答案。

你需要找出候选人如何解决更真实世界的问题。

- user325117

---

无法解雇他们？当然可以。我们掌握着钱袋子，我们做出决策。我非常确定，如果有人对自己的工作机会轻率对待（这不是种族或性别歧视，如果因为愚蠢或无能而不雇用某人被认定为歧视，我们将陷入大麻烦），我们完全可以毫不犹豫地解雇他们。招聘人员寻找任何理由来缩小范围。给他们一个理由是一个相当愚蠢的举动：http://www.joelonsoftware.com/articles/ResumeRead.html - paxdiablo

正确，但同样的，应聘者可能提供答案是因为他或她认为需要一个巧妙或类似于C黑客的答案。这就是我所说的人工问题不能得到有用答案的意思。 - user325117

虽然K&R风格的定义有点让人担忧。 - user325117

Answer 5

缺乏可读性和可维护性，对于1970年后出生的人来说都是问题。

那么，难以阅读的代码是否就更适合1970年之前出生的人维护呢？如果是这样的话，那太好了，因为我就是这样的人，这只能成为一个卖点。

在决定是否要让这个人参加第二轮面试之前，我想知道除了作者的工作保障之外，它是否还有其他值得称赞的特点。

这段代码没有任何一个值得称赞的特点。它奇怪地使用异或交换技术，可能唯一的可取之处是节省了一个整数大小的堆栈空间。然而，由于定义了五个指针和未使用的int，甚至这一点也被否定了。它还过度使用了逗号运算符。

通常情况下，我也会说“goto，呸”，但在这种情况下，它已经以相当优雅的方式使用，一旦你理解了所使用的排序算法。事实上，你可以说它使侏儒排序算法比使用索引变量更加清晰（除了不能推广到n个元素）。所以这就是它的优点，它让goto看起来很好 :)

关于“你会让候选人参加第二轮面试吗？” 如果代码片段附有详细的注释，解释算法的工作原理和编写者使用它的动机，我肯定会让他进行第二轮面试。如果没有，我可能会给他打电话并问这些问题。

需要注意的是，代码片段使用了K&R风格的参数声明。这意味着作者可能已经10到15年没有使用C语言编程了，或者他是从互联网上复制的。

- JeremyP