奇长数组快速小阶统计算法的正确性
correctness of fast small order statistic algorithm for odd-length array
Problem 9-3 of the textbook Intro to Algorithms (CLRS) 描述了一种快速 O(n) 算法，用于查找长度为 n 的数组的第 k 阶统计量（排序时数组中的第 k 个元素），对于 k远小于 n。我不确定这个算法在n为奇数时是否正确，想看看有没有办法证明它是正确的。
基本思路是，我们首先将数组分成两半，第一部分是 floor(n/2) 元素，第二部分是 ceil(n/2) 元素。然后，我们 "partner" 上半部分的每个元素与下半部分的对应元素。当 n 为奇数时，这将留下剩余的未配对元素。
对于每对搭档，我们确保左边的搭档 >= 右边的搭档，如果不是，则交换两者。然后，递归地找到下半场的第 k 阶统计量，将下半场进行的任何交换与上半场的相应交换进行镜像。在此之后，整个数组的第k阶统计量要么在前半部分的前k个元素，要么在后半部分的前k个元素。
我的困惑来自数组长度n为奇数的情况，后半部分有一个没有伙伴的孤独元素。由于递归是在后半部分执行的，由数组的最后一个 ceil(n/2) 元素组成，包括唯一的无伙伴最后一个元素，我们应该将后半部分进行的所有交换与内部进行的交换进行镜像上半场相应的合作伙伴，当其中一个交换涉及最终元素时，不清楚该怎么做，因为它没有合作伙伴。
教科书似乎没有特别注意这个问题，所以我假设当交换涉及最后一个元素时，那么不要在上半场对伙伴进行任何镜像移动全部。结果，最后一个元素只是 "steals" 与它交换的任何人的伙伴。但是，在这种情况下，是否有一种简单的方法可以查看算法是否仍然正确？如果当最后一个元素窃取了其他人的伙伴时，伙伴实际上是第 k 阶统计数据，并且稍后被交换到无法访问的位置怎么办？涉及顺序统计选择的递归和分区机制对我来说非常不透明，因此我不能自信地排除这种情况。
我认为您对算法的描述并不完全准确（但是您链接到的解释远非清晰）。据我了解，算法对奇数长度数组正确的原因如下：
我们先来看几个长度为偶数的数组的例子，其中n=10，k=3（即我们正在寻找第三小的元素，也就是2）：
a. 5 2 7 6 1 9 3 8 4 0
b. 5 1 7 6 2 9 3 8 4 0
c. 5 0 7 6 2 9 3 8 4 1
d. 5 0 7 6 2 9 3 8 1 4
如果我们将数组分成两部分，我们得到：
a. 5 2 7 6 1 9 3 8 4 0
b. 5 1 7 6 2 9 3 8 4 0
c. 5 0 7 6 2 9 3 8 4 1
d. 5 0 7 6 2 9 3 8 1 4
还有这些夫妇：
a. (5,9) (2,3) (7,8) (6,4) (1,0) <- 0 coupled with 1
b. (5,9) (1,3) (7,8) (6,4) (2,0) <- 0 coupled with 2
c. (5,9) (0,3) (7,8) (6,4) (2,1) <- 1 coupled with 2
d. (5,9) (0,3) (7,8) (6,1) (2,4) <- 0, 1 and 2 not coupled with each other
在比较和交换这对夫妇之后，使他们的最小元素在第一组中，我们得到：
a. 5 2 7 4 0 9 3 8 6 1
b. 5 1 7 4 0 9 3 8 6 2
c. 5 0 7 4 1 9 3 8 6 2
d. 5 0 7 1 2 9 3 8 6 4
您会看到最小的元素 0 总是在第一组中。第二小的元素 1 要么在第一组中，要么在第二组中（如果它与最小的元素 0 耦合）。第三小的元素 2 要么在第一组中，要么在第二组中（如果它与最小的元素 0 耦合）与最小元素 0 或第二小元素 1 耦合。
所以最小的元素在第一组，第二和第三小的元素可以在任何一组。这意味着第三小的元素是第一组中的 3 个最小元素之一，或者是第二组中的 2 个（！）最小元素之一。
a. 5 2 7 4 0 9 3 8 6 1 -> 0 2 4 + 1 3
b. 5 1 7 4 0 9 3 8 6 2 -> 0 1 4 + 2 3
c. 5 0 7 4 1 9 3 8 6 2 -> 0 1 4 + 2 3
d. 5 0 7 1 2 9 3 8 6 4 -> 0 1 2 + 3 4
所以如果我们说整个数组的第 k 个最小元素现在是任一组中第 k 个最小元素之一，则第二组中有一个可用位置，这就是为什么，在奇数长度的数组中，我们将未耦合的元素添加到第二组。无论未耦合的元素是否是我们正在寻找的元素，它肯定是任一组中第 k 个最小的元素之一。
其实更正确的说法是，第k小的元素要么是第一组中k个最小的元素之一，要么是k/2+1个最小的元素之一第二组中的元素。我实际上不确定该算法是否是最优的，甚至是正确的。有很多重复的比较和交换正在进行，并且在交换另一组中的相应元素时跟踪一对和交换一组中的元素的想法似乎没有意义。
Problem 9-3 of the textbook Intro to Algorithms (CLRS) 描述了一种快速 O(n) 算法，用于查找长度为 n 的数组的第 k 阶统计量（排序时数组中的第 k 个元素），对于 k远小于 n。我不确定这个算法在n为奇数时是否正确，想看看有没有办法证明它是正确的。
基本思路是，我们首先将数组分成两半，第一部分是 floor(n/2) 元素，第二部分是 ceil(n/2) 元素。然后，我们 "partner" 上半部分的每个元素与下半部分的对应元素。当 n 为奇数时，这将留下剩余的未配对元素。
对于每对搭档，我们确保左边的搭档 >= 右边的搭档，如果不是，则交换两者。然后，递归地找到下半场的第 k 阶统计量，将下半场进行的任何交换与上半场的相应交换进行镜像。在此之后，整个数组的第k阶统计量要么在前半部分的前k个元素，要么在后半部分的前k个元素。
我的困惑来自数组长度n为奇数的情况，后半部分有一个没有伙伴的孤独元素。由于递归是在后半部分执行的，由数组的最后一个 ceil(n/2) 元素组成，包括唯一的无伙伴最后一个元素，我们应该将后半部分进行的所有交换与内部进行的交换进行镜像上半场相应的合作伙伴，当其中一个交换涉及最终元素时，不清楚该怎么做，因为它没有合作伙伴。
教科书似乎没有特别注意这个问题，所以我假设当交换涉及最后一个元素时，那么不要在上半场对伙伴进行任何镜像移动全部。结果，最后一个元素只是 "steals" 与它交换的任何人的伙伴。但是，在这种情况下，是否有一种简单的方法可以查看算法是否仍然正确？如果当最后一个元素窃取了其他人的伙伴时，伙伴实际上是第 k 阶统计数据，并且稍后被交换到无法访问的位置怎么办？涉及顺序统计选择的递归和分区机制对我来说非常不透明，因此我不能自信地排除这种情况。
我认为您对算法的描述并不完全准确（但是您链接到的解释远非清晰）。据我了解，算法对奇数长度数组正确的原因如下：
我们先来看几个长度为偶数的数组的例子，其中n=10，k=3（即我们正在寻找第三小的元素，也就是2）：
a. 5 2 7 6 1 9 3 8 4 0
b. 5 1 7 6 2 9 3 8 4 0
c. 5 0 7 6 2 9 3 8 4 1
d. 5 0 7 6 2 9 3 8 1 4
如果我们将数组分成两部分，我们得到：
a. 5 2 7 6 1 9 3 8 4 0
b. 5 1 7 6 2 9 3 8 4 0
c. 5 0 7 6 2 9 3 8 4 1
d. 5 0 7 6 2 9 3 8 1 4
还有这些夫妇：
a. (5,9) (2,3) (7,8) (6,4) (1,0) <- 0 coupled with 1
b. (5,9) (1,3) (7,8) (6,4) (2,0) <- 0 coupled with 2
c. (5,9) (0,3) (7,8) (6,4) (2,1) <- 1 coupled with 2
d. (5,9) (0,3) (7,8) (6,1) (2,4) <- 0, 1 and 2 not coupled with each other
在比较和交换这对夫妇之后，使他们的最小元素在第一组中，我们得到：
a. 5 2 7 4 0 9 3 8 6 1
b. 5 1 7 4 0 9 3 8 6 2
c. 5 0 7 4 1 9 3 8 6 2
d. 5 0 7 1 2 9 3 8 6 4
您会看到最小的元素 0 总是在第一组中。第二小的元素 1 要么在第一组中，要么在第二组中（如果它与最小的元素 0 耦合）。第三小的元素 2 要么在第一组中，要么在第二组中（如果它与最小的元素 0 耦合）与最小元素 0 或第二小元素 1 耦合。
所以最小的元素在第一组，第二和第三小的元素可以在任何一组。这意味着第三小的元素是第一组中的 3 个最小元素之一，或者是第二组中的 2 个（！）最小元素之一。
a. 5 2 7 4 0 9 3 8 6 1 -> 0 2 4 + 1 3
b. 5 1 7 4 0 9 3 8 6 2 -> 0 1 4 + 2 3
c. 5 0 7 4 1 9 3 8 6 2 -> 0 1 4 + 2 3
d. 5 0 7 1 2 9 3 8 6 4 -> 0 1 2 + 3 4
所以如果我们说整个数组的第 k 个最小元素现在是任一组中第 k 个最小元素之一，则第二组中有一个可用位置，这就是为什么，在奇数长度的数组中，我们将未耦合的元素添加到第二组。无论未耦合的元素是否是我们正在寻找的元素，它肯定是任一组中第 k 个最小的元素之一。
其实更正确的说法是，第k小的元素要么是第一组中k个最小的元素之一，要么是k/2+1个最小的元素之一第二组中的元素。我实际上不确定该算法是否是最优的，甚至是正确的。有很多重复的比较和交换正在进行，并且在交换另一组中的相应元素时跟踪一对和交换一组中的元素的想法似乎没有意义。