我正在尝试编写一个排序算法，它接受一个输入数组并生成排序后的数组。以下是算法的约束。
我试图找到一个解决方案，以下是我的结果。
我们使用中值函数来获得最小和最大的对。例子：给一个数组 A[1..n]，我们得到前三个元素的中位数，我们称它为一个集合，我们得到一个 $Median$。在下一次迭代中，我们从集合中删除接收到的中值并将下一个元素添加到集合中，然后再次调用 Median 函数。当在长度上重复此步骤时，会为整个数组生成一对最大和最小元素。
我们使用这对，使用比较操作并将它们放在位置 A[0] 和 A[n-1]。
我们对数组 A[1..n-2] 重复相同的操作以获得另一对最大和最小的。
我们用 A[0] 和新收到的对取中位数。
重复第 3~7 步，得到有序数组。
该算法满足条件 2 和 3，但不满足时间复杂度。我希望有人可以提供一些指导如何进一步进行。
快速排序（以相反的顺序呈现）就像这样工作。假设你有一个数组：
[1, 4, 5, 2, 3]
抽象中的快速排序基本上是通过从左侧和右侧向数组中间滑动来工作的。当我们向内滑动时，我们想要交换项目，使得大的东西移到右边，小东西移到左边。最终我们应该有一个数组，其中所有的小东西都在左边，所有的大东西都在右边。
这个过程的结果也保证了一个元素将被放置在正确的位置（因为它左边的所有东西都会更小，而右边的所有东西都会更大，所以它必须在正确的位置）。该值称为pivot。快速排序的第一步是确保枢轴在正确的位置。
我们这样做的方法是选择一个随机元素作为我们的pivot- 我们想要放入正确位置的项目。对于这个简单的示例，我们将只使用最后一个数字(3)。这pivot是我们的比较值。
一旦我们选择了我们的pivot/comparison 值，我们就会监控最左边的元素(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)它识别出高于我们的枢轴元素并停止移动时。右枢轴从右侧做同样的事情，但在击中时停止，因为(2)它低于pivot. 当双方都停止时，我们进行交换，所以我们最终得到：
[1, 2, 5, 4, 3]
请注意，我们越来越接近排序了。我们继续向内移动两个指针，直到它们都指向同一个元素，或者它们交叉——以先到者为准。当这种情况发生时，我们进行最后一步，即用它们指向(3)的任何点替换枢轴元素left/right-pointers，在这种情况下，这将是(5)因为它们都将停在中间。然后我们交换，这样我们得到：
[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
}
重要的是要注意，尽管在这个例子中，分区步骤对我们的数组进行了完全排序，但这通常不是分区步骤的重点。分区步骤的重点是将一个元素放入正确的位置，并确保该元素左侧的所有内容都是less而右侧的所有内容都是more。或者换句话说，将pivot值移动到正确的位置，然后保证枢轴左侧的所有内容都小于它，而右侧的所有内容都更大。所以虽然在这个例子中数组是完全排序的，但一般我们只能保证一项和一项仅项目位于正确的位置（左侧和右侧的所有内容分别更大/更小）。这就是partition上面的方法返回left的原因，因为它告诉调用函数这个元素位于正确的位置（并且数组已被正确分区）。
也就是说，如果我们从如下数组开始：
[1, 7, 5, 4, 2, 9, 3]
然后分区步骤将返回如下内容：
[1, 3, 2, [4], 7, 5, 9]
其中 [4] 是唯一保证在正确位置的值，但左侧的所有内容都小于 [4] 而右侧的所有内容都更大（尽管不一定要排序！）。
第二步是递归地执行这一步。也就是说，如果我们可以将一个元素放入正确的位置，那么我们最终应该能够将所有项目放入正确的位置。这就是quicksort功能。在代码中：
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递归调用，最终我们会将数组减半并对其进行分区，直到我们得到大小为 1 的数组（根据定义，它已经排序）。所以我们分区，然后减半，分区，减半等，直到整个数组排序（到位）。这给了我们一个时间排序O(n lg(n))。凉爽的！
这是一个使用它的简单示例：
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
步骤 1 和 2 确实是正确解决方案的第一步。但是，一旦您知道了最小和最大的元素，中位数预言机就是比较预言机；如果你想与 比较a[i]，a[j]那么最小的元素到底是什么a[i] < a[j]时候。所以你可以直接运行快速排序或合并排序或whathaveyou。a[i] = median(a[i], a[j], a[0])a[0]