arrays - 算法:在$ O(n\log n)$中使用中位数和Just 1比较排序

Question

我试图编写一个排序算法，它接受一个输入数组并生成排序数组。以下是算法的约束条件。
时间复杂度= $O（n \ log n）$
整个算法中只有一个比较操作。
我们有一个函数可以为一组三个元素提供中值。
我试着找到解决办法，结果如下。
我们用中值函数得到最小和最大对。
例如：给一个数组A[1..n]，我们得到前三个元素的中值，我们称之为集合，然后得到$median$在下一次迭代中，我们从集合中移除接收到的中值，并将下一个元素添加到集合中，然后再次调用中值函数当在整个长度上重复此步骤时，将为整个数组生成一对最大和最小元素。
我们使用这一对，使用比较操作并将它们放在位置A[0]&A[n-1]。
我们对数组a[1..n-2]重复相同的操作，得到另一对最大和最小的数组。
我们用a[0]和新收到的对来计算中值。
中值放在A[1]处。
我们用A[n-1]和新收到的一对取中值。
中值放在a[n-2]处。
重复步骤3~7以获得排序数组。
该算法满足条件2和3，但不满足时间复杂度。我希望有人能提供一些指导，如何进一步进行。

Answer 1

快速排序（按相反顺序显示）的工作方式如下。假设您有一个数组：

 [1, 4, 5, 2, 3]

摘要中的quicksort基本上是通过从左侧和右侧向数组的中间滑动来工作的。当我们往里滑的时候，我们想交换一些东西，这样大的东西会移到右边，小的东西会移到左边。最终我们应该有一个数组，所有的小东西都在左边，所有的大东西都在右边。
这个过程的结果还保证了一个元素将被放置在正确的位置（因为它左边的所有元素都会更小，右边的所有元素都会更大，所以它必须处于正确的位置）这个值叫做 pivot。快速排序的第一步是确保轴位于正确的位置。
我们这样做的方法是选择一个随机元素作为我们的 pivot-我们想要放在正确位置的项目。对于这个简单的例子，我们将使用最后一个数字 (3)。 pivot是我们的比较值。
一旦我们选择了 pivot/比较值，我们就监视最左边的元素 (1)，最右边的元素 (3)。我们称之为 left-pointer和 right-pointer left-pointers的任务是向数组的中间滑动，当它找到大于 pivot的内容时停止。 right指针做同样的事情，但是它向内滑动寻找小于 pivot的值。代码中：

while (true) {
    while (array[++left] < pivot);
    while (array[--right] > pivot) if (left == right) break;

    if (left >= right) break;           // If the pointers meet then exit the loop
    swap(array[left], array[right]);    // Swap the values otherwise.
}

所以在上面的例子中，当 left-pointer点击 (4)时，它会识别出这个值高于pivot元素并停止移动。右枢轴从右侧执行相同的操作，但当它碰到 (2)时停止，因为它低于 pivot。当双方都停下来时，我们做一个交换，所以我们最终得到：

[1, 2, 5, 4, 3]

注意，我们离分类越来越近了我们继续向内移动两个指针，直到它们都指向同一个元素，或者它们交叉-以先到者为准当这种情况发生时，我们做一个最后的步骤，那就是把枢轴元素[cc]替换成“CC”指向的任何点，在这种情况下，这将是 (3)，因为它们都会在中间停止。然后我们交换，这样我们得到：

[1, 2, 3, 4, 5] 
(Notice that we swap the original pivot (3) with the value pointed to by both sides (5))

整个过程称为分区。在代码中，如下所示：

int partition(int *array, int lBound, int rBound) {
    int pivot = array[rBound];          // Use the last element as a pivot
    int left = lBound - 1;              // Point to one before the first element
    int right = rBound;             // Point to the last element;

    // We'll break out of the loop explicity
    while (true) {

        while (array[++left] < pivot);
        while (array[--right] > pivot) if (left == right) break;

        if (left >= right) break;    // If the pointers meet then exit the loop
        swap(array[left], array[right]);    // Swap the pointers otherwise.
    }

    swap(array[left], array[rBound]);   // Move the pivot item into its correct place
    return left;    // The left element is now in the right place
}

需要注意的是，尽管在本例中分区步骤对数组进行了完全排序，但这通常不是分区步骤的重点比较步骤的要点是将一个元素放在正确的位置，并确保该元素左边的内容更少，右边的内容更多。或者换句话说，将 left/right-pointers值移动到正确的位置，然后确保枢轴左侧的所有内容都小于该值，右侧的所有内容都大于该值。因此，尽管在本例中，数组是完全排序的，但一般来说，我们只能保证一个项和一个项位于正确的位置（左、右两边的内容分别是大/小）。这就是上面的 (5)方法返回 pivot的原因，因为它告诉调用函数这一个元素位于正确的位置（并且数组已正确分区）。
如果我们从这样的数组开始：

[1, 7, 5, 4, 2, 9, 3]

然后分区步骤将返回如下内容：

[1, 3, 2, [4], 7, 5, 9]

其中[4]是唯一保证位于正确位置的值，但左侧的所有值都小于[4]，右侧的所有值都更大（尽管不一定排序！）是的。
第二步是递归地执行这个步骤。也就是说，如果我们可以把一个元素放到它的正确位置，那么我们最终应该能够把所有的元素放到它们的正确位置。这就是 partition函数代码中：

int *quicksort(int *array, int lBound, int rBound) {
    if (lBound >= rBound) return array;   // If the array is size 1 or less - return.

    int pivot = partition(array, lBound, rBound);   // Split the array in two. 
    quicksort(array, lBound, pivot - 1);    // Sort the left size. (Recursive)
    quicksort(array, pivot + 1, rBound);    // Sort the right side. (Recursive) 

    return array;
}

注意，第一步是确保数组的边至少为2。处理任何小于该值的内容都没有意义，因此如果不满足该条件，我们将返回下一步是调用我们的分区函数，它将根据上述过程拆分数组。一旦我们知道数组中有一个元素位于正确的位置，我们只需再次调用quicksort，但这次是在轴的左侧，然后再次调用轴的右侧。注意，我们不包括轴，因为分区保证将其放在正确的位置！
如果我们继续递归调用 left，最终我们会将数组减半并对其进行分区，直到得到大小为1的数组（根据定义，数组已经排序）。所以我们进行分区，然后对半，分区，对半，等等，直到整个数组排序（到位）。这给了我们一个 quicksort时间的排序。太酷了！
下面是一个简单的使用示例：

int main() {
    int array [] {1, 0, 2, 9, 3, 8, 4, 7, 5, 6};

    quicksort(array, 0, 9); // Sort from zero to 9.

    // Display the results
    for (int index = 0; index != 10; ++index) {
        cout << array[index] << endl;
    }

    return 0;
}

一个好的视觉演示可以在这里找到： http://www.youtube.com/watch?v=Z5nSXTnD1I4