C++:设计排序典型算法（冒泡与快速排序）

Question

基本要求：
（1）要求用C++模块化设计的思想来完成程序的设计；
（2）要求各个功能分别使用函数来完成，各个函数分别放在不同的文件中。
（3）源代码程序要求必要的注释。
主要技术问题的描述
根据以上的分析，主要解决的技术问题在于：
（1）“冒泡法”排序的实现。
（2）“quicksort法”排序的实现。
“quicksort法”排序算法采用的是递归方法，要求分界值的选定采用数组中间项的值。
工作过程如下：
第一步：选择一个分界值，把数组分成两部分，大于等于分界值的元素集中到数组的某一部分，小于分界值的元素集中到数组的另一部分。
第二步：对分出来的两部分，又分别重复第一步的过程，直到整个数组排序完毕。
例如：设定字符数组A为：f e d a c b
（1）选定 d作为分界值，则在第一遍划分后数组重新安排如下：b c a d e f
（2）在第一遍划分b c a和 d e f两部分后，又分别对这两部分进行划分，过程是递归。

Answer 1

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

vector<int> quick_sort( vector<int> a )
{
if ( a.size() == 0 || a.size() == 1 )
{
return a;
}

int k = a[ 0 ];
vector<int> pre, suc;
for ( int i = 1; i < a.size(); ++i )
{
if ( a[ i ] <= k )
{
pre.push_back( a[ i ] );
}
else
{
suc.push_back( a[ i ] );
}
}

pre = quick_sort( pre );
suc = quick_sort( suc );

a = pre;
a.push_back( k );
for ( i = 0; i < suc.size(); ++i )
{
a.push_back( suc[ i ] );
}

return a;
}

void main()
{
srand( time( 0 ) );
vector<int> a;

for ( int i = 0; i < 10; ++i )
{
a.push_back( rand() % 100 + 1 );
}

for ( i = 0; i < 10; ++i )
{
cout << a[ i ] << " ";
}
cout << endl;

a = quick_sort( a );

for ( i = 0; i < 10; ++i )
{
cout << a[ i ] << " ";
}
cout << endl;

return;
}