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

基本要求:
(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两部分后,又分别对这两部分进行划分,过程是递归。

#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;
}
温馨提示:答案为网友推荐,仅供参考
相似回答
大家正在搜