这是什么排序算法，它是如何工作的？ （如果没有名称或知名资源。）
What sorting algorithm is this, and how does it work? (If there isn't a name or well-known resource for it.)
自从我参加 DSA class 以来已经将近十年了。我浏览了 Wikipedia's list of sorting algorithms，但 none 脱颖而出。它是优先级队列实现的一部分，似乎部分排序发生在推送函数 (EnQueue) 中，而另一部分发生在弹出函数 (DeQueue) 中。
这是原始的 Mathematica 代码，但由于大多数人不熟悉 Mathematica，我在下面做了一些翻译每个函数。
EnQueue[q : queue[ar_, n_, pred_], val_] := Module[{i, j},
If[n == Length[ar], ar = Join[ar, makeArray@Length@ar]];
n++; ar[[n]] = val;
i = n;
While[True,
j = Quotient[i, 2];
If[j < 1 || pred[ar[[j]], ar[[i]]],
Break[]
];
ar[[{i, j}]] = {ar[[j]], ar[[i]]};
i = j;
];
q
]
EnQueue函数首先检查元素的数量n是否已经达到堆的大小ar，如果是，则将堆加倍。接下来，它增加元素的数量并将新元素存储在该索引处（Mathematica 索引是从 1 开始的，而不是从 0 开始的）。然后，它将 i 设置为该索引（新元素的），并进入一个循环，将 j 设置为 floor(i/2)， 即 某个元素在堆的中间。现在，如果 j < 1（据我所知，这相当于检查是否 i == 1），或者如果 ar[j]（中间的元素） 应该 领先于 ar[i]（新元素），然后我们中断。否则，我们交换 i 和 j 处的元素，然后继续；所以在第二次迭代中，我们从 i 指向 middle 和 j 指向 quarter-way 开始。
DeQueue[queue[ar_, n_, pred_]] :=
Module[{i, j, res = ar[[1]]},
ar[[1]] = ar[[n]]; ar[[n]] = Null; n--;
j = 1;
While[j <= Quotient[n, 2],
i = 2 j;
If[i < n && pred[ar[[i + 1]], ar[[i]]],
i++
];
If[pred[ar[[i]], ar[[j]]],
ar[[{i, j}]] = {ar[[j]], ar[[i]]};
];
j = i];
res]
同时，DeQueue returns 堆的前面，并将堆的 back 移到前面（并取消设置后面，并且减少元素的数量）。然后，从指向前面的 j 开始，它进入一个循环，从将 i 设置为双 j 开始。 如果 i 在边界内（指向一个元素）但相对于下一个元素是乱序的，则 i 递增。如果i相对于j是有序的（前面；换句话说，如果前面是out相对于i的顺序), 然后交换两个位置， j 设置为 i 所在的位置。我们继续循环，直到 j 通过中间。
主要是上面加粗的部分我没看懂。我 认为 它正在做的是对 DeQueue 上的 一半 堆进行排序，并对 中的新元素进行部分排序=12=]，但我不确定...
排队对我来说似乎是一个 min-heap 例程
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps
Dequeue 删除堆的顶部项，它存储在数组的第一项中，然后用数组的最后一项替换它，并将其向下筛选堆，每次交换它 child 只要 child 小于该项目（并且小于它的兄弟，如果它有的话）。当没有更小的 child 时停止，即当项目到达堆底或小于它的 children （或 child，它只有一个）。
编辑： 单词 'enqueue' 和 'dequeue' 表明它是一个队列。该算法是在数组中实现的二进制堆，因此这是一个优先级队列。
自从我参加 DSA class 以来已经将近十年了。我浏览了 Wikipedia's list of sorting algorithms，但 none 脱颖而出。它是优先级队列实现的一部分，似乎部分排序发生在推送函数 (EnQueue) 中，而另一部分发生在弹出函数 (DeQueue) 中。
这是原始的 Mathematica 代码，但由于大多数人不熟悉 Mathematica，我在下面做了一些翻译每个函数。
EnQueue[q : queue[ar_, n_, pred_], val_] := Module[{i, j},
If[n == Length[ar], ar = Join[ar, makeArray@Length@ar]];
n++; ar[[n]] = val;
i = n;
While[True,
j = Quotient[i, 2];
If[j < 1 || pred[ar[[j]], ar[[i]]],
Break[]
];
ar[[{i, j}]] = {ar[[j]], ar[[i]]};
i = j;
];
q
]
EnQueue函数首先检查元素的数量n是否已经达到堆的大小ar，如果是，则将堆加倍。接下来，它增加元素的数量并将新元素存储在该索引处（Mathematica 索引是从 1 开始的，而不是从 0 开始的）。然后，它将 i 设置为该索引（新元素的），并进入一个循环，将 j 设置为 floor(i/2)， 即 某个元素在堆的中间。现在，如果 j < 1（据我所知，这相当于检查是否 i == 1），或者如果 ar[j]（中间的元素） 应该 领先于 ar[i]（新元素），然后我们中断。否则，我们交换 i 和 j 处的元素，然后继续；所以在第二次迭代中，我们从 i 指向 middle 和 j 指向 quarter-way 开始。
DeQueue[queue[ar_, n_, pred_]] :=
Module[{i, j, res = ar[[1]]},
ar[[1]] = ar[[n]]; ar[[n]] = Null; n--;
j = 1;
While[j <= Quotient[n, 2],
i = 2 j;
If[i < n && pred[ar[[i + 1]], ar[[i]]],
i++
];
If[pred[ar[[i]], ar[[j]]],
ar[[{i, j}]] = {ar[[j]], ar[[i]]};
];
j = i];
res]
同时，DeQueue returns 堆的前面，并将堆的 back 移到前面（并取消设置后面，并且减少元素的数量）。然后，从指向前面的 j 开始，它进入一个循环，从将 i 设置为双 j 开始。 如果 i 在边界内（指向一个元素）但相对于下一个元素是乱序的，则 i 递增。如果i相对于j是有序的（前面；换句话说，如果前面是out相对于i的顺序), 然后交换两个位置， j 设置为 i 所在的位置。我们继续循环，直到 j 通过中间。
主要是上面加粗的部分我没看懂。我 认为 它正在做的是对 DeQueue 上的 一半 堆进行排序，并对 中的新元素进行部分排序=12=]，但我不确定...
排队对我来说似乎是一个 min-heap 例程
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps
Dequeue 删除堆的顶部项，它存储在数组的第一项中，然后用数组的最后一项替换它，并将其向下筛选堆，每次交换它 child 只要 child 小于该项目（并且小于它的兄弟，如果它有的话）。当没有更小的 child 时停止，即当项目到达堆底或小于它的 children （或 child，它只有一个）。
编辑： 单词 'enqueue' 和 'dequeue' 表明它是一个队列。该算法是在数组中实现的二进制堆，因此这是一个优先级队列。