在 C++ 中快速排序数组而不修改它（可能不使用临时数组）

Question

通常情况下，我绝不会在 Whosebug 上问我的学校练习，但我认为如果不使用临时数组或修改数组，他们想要从我们这里得到的东西是不可能的。

他们对我们的要求是：

应该是递归的快速排序函数
它应该排序（这就是排序算法的作用，哈哈）但它应该保持数组完好无损，
不能使用临时数组
并且它必须 return 链表格式的排序列表。
函数应该是这样的：

LinkedList *quickSort(int *array, int startPosition, int endPosition)

返回链表很容易，排序很容易，但算法的每一步都不需要修改？我不这么认为。

我不是说请将解决方案发送给我。我只想让你回答这个，不是不可能吗？

编辑："Leaving the array intact"老师的意思是"dont change the size of the array, but you can modify the order of the array"，所以问题解决了

我会检查其中一个答案，只是为了让标签问题解决。

Answer 1

直接回答你的问题：快速排序可以就地完成（没有任何暂存区。）

因为我不想直接为你完成作业 :) 这里有一个资源可以帮助你。

参见 http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

中的第二个算法

Answer 2

根据我对题目的理解，quickSort可以定义为

std::list<int> quickSort(int * array, int startPosition, int endPosition) {
    std::list<int> result;
    for (int i = startPosition; i <= endPosition; ++i)
        result.push_back(array[i]);
    QuiskSort(result.begin(), result.end());
    return result;
}

其中 QuickSort 有定义

template <class Iterator>
inline void QuickSort(Iterator begin, Iterator end) {
    if (end <= begin) return;
    Iterator pivot = begin, middle = begin + 1;
    for (Iterator i = begin + 1; i < end; ++i) {
        if (*i < *pivot) {
            std::iter_swap(i, middle);
            ++middle;
        }
    }
    std::iter_swap(begin, middle - 1);
    QuickSort(begin, middle - 1);
    QuickSort(middle, end);
}

Answer 3

伙计们，我以为我遗漏了一些东西，有一种方法我不知道，在你的评论之后我打电话给助理，他说当然你需要修改数组，你不会可以不修改它。 但是在练习声明中它明确地说

b) 使用快速排序算法对给定位置之间的数组子数组中的数字进行排序 并保持数组不变（不能使用临时数组）

再次感谢所有的回答和评论。抱歉造成误会的各位。

在 C++ 中快速排序数组而不修改它（可能不使用临时数组）

QuickSort an array without modifying it (may not use a temporary array) in C++

c++

arrays

recursion

linked-list

quicksort