Question

c++请教 vector sort怎么写

1,使用vector类模板用于执行sort整数型的vectors
2.测试array size分别为10，20，100(使用void random_fill (vector<int> &v, int lb, int ub)
{
for(int i = 0; i < (int) v.size() ;i++)
{
v[i] = random(lb,ub);
}
}
int random (int lb, int ub)
{
int x;
x = rand();
x = x % (ub - lb + 1);
x = x + lb;
return x;
} 来表示用任意数代表的一个整数的vector)
3.如果vector包含一个分子或者为空，那就保留它；否则，从vector里面拿出第一个分子，叫它x，创建两个新vectors: left,right,left 包含所有小于x的，但除了x；right包含所有大于x的，然后执行一个quick_sort在left,right递归，最后把left,分子x,right放进一个新的vector；思路是把一个array分成两部分，分别存进两个objects of type vector,一个包含所有小于或等于x的分子，另一个包含所有大于 x的分子；
另外一个方法是去执行一个memory _efficient _quicksort ,并且测试它，这个执行不需要额外的memory 分配，处理重新排列的原始vector里面的所有分子，比如x移到合适的位置，所有比x小或等于x的分子移到x的左边，所有大于x的移到x的右边，它 实行了一个递归调用在原始vector的部分中，所以在整个运算中不需要创建额外的vector object.
需要大家帮帮我，写一下，第三个 需要写出两种方法

Answer 1

对于C++的模板库中本来就可以使用<algorithm>这个头文件，其中对于STL的sort函数就是使用quick sort，直接使用就可以了啊。

追问

ni可以具体写一下吗 ,因为是用两个方法,一个是quick_sort,一个是memory _efficient _quicksort

追答

实现快速排序相对来说比较麻烦，而且你这里要求要两个程序，需要和不需要开辟额外内存空间的两种方法，建议你参考数据结构里面快速排序看一下。