QuickSort数组而不修改它(不能使用临时数组)在C++中
QuickSort数组而不修改它(不能使用临时数组)在C++中
提问于 2015-07-15 08:38:46
通常，我不会要求我的学校练习堆叠溢出，但我认为如果不使用临时数组或修改数组，他们就不可能从我们这里得到什么。
他们想要的是：
- 应该是递归的QuickSort函数
- 它应该排序(这就是排序算法所做的lol)，但是它应该保持数组完整，
- 可能不使用临时数组。
- 它必须以链接列表格式返回排序列表。
- 职能应如下：
LinkedList *quickSort(int *array, int startPosition, int endPosition)
返回链接列表很容易，排序很容易，但是算法的每一步都没有变化？我不这么认为。
，我不是说请把解决方案寄给我。我只想让你回答这个问题，难道这不可能吗？
编辑：“保持数组完整”老师的意思是“不要改变数组的大小，但是你可以修改数组的顺序”，所以问题解决了。
我将检查其中一个答案，以使标签问题得到解决。
回答 3
Stack Overflow用户
回答已采纳
发布于 2015-07-15 09:21:15
伙计们，我以为我错过了什么，但有一种方式我不知道，在你的评论之后，我打电话给助理，他说，你当然需要修改数组，如果不修改数组，你就做不到。，但在练习声明中，它清楚地写着
( b)使用快速排序算法对给定位置之间的数组子数组中的数字进行排序，并保留数组完整的(不能使用临时数组)。
再次感谢所有的回答和评论。对不起那些男的。
Stack Overflow用户
发布于 2015-07-15 08:46:45
Stack Overflow用户
发布于 2015-07-15 09:17:20
根据我对这个问题的理解，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);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31425432
复制相关文章
相似问题
腾讯云开发者
