C++是一种十分优秀的语言，它的好处我就不在这里多说了。为了帮助大家更好的应用这们语言。C++区正在尝试联合编写程序。
如果大家有志于将来通过C++找工作，或者已经在工作中应用着这种语言，希望有更多提高。不妨参加我们的活动。一般从参加工作开始，每个人都要经过这样一个过程。先学习公司已有的程序，作最简单的修补。随着知识的积累可以改一些更重要的程序，甚至可以独立写一个feature。水平进一步提高，可以主持开发一个component。最后水平达到公司最高的时候可以成为公司的框架师。负责维护或重新开发整套系统。不是每一个人都能走到这一步。不过在这里，我们希望给大家一个互相学习的机会。给在不同阶段的网友一个在自己基础上进一步提高的机会。

我们这个活动几个月前开始搞，暑假阶段停了几个月。现在希望能继续坚持下去。编程环境选的是VC6.0
由于大家的起点可能不同，我们尽量从简单的开始。最先开始的是一个算法演示的小程序。这个程序还在不断的改进中。独立实现一个算法需要不少VC++/MFC的知识。大家如果觉得这部份知识不够的话可以在VC++区学习，或者先写只用C++的算法实现部份。就像我前面说的，从修修补补开始，逐渐能够实现一个单独的算法，在到能够设计更复杂的框架。

这里编程由于没有时间限制，希望大家尽量把自己的程序写到自己认为最满意的程度。先学的什么知识技巧尽量用上。这也是提高自己水平的必经之路。

希望大家想出更多更好的题目。同时欢迎各高手指点，或帮助设计框架。如果题目不在这个帖子的第一页，我们会把题目的链接放在这里。

[此贴子已经被作者于2006-9-24 1:48:29编辑过]

现在正在作的是一个算法演示的程序。源程序如下(更新：09/23)

[此贴子已经被作者于2006-9-24 1:58:17编辑过]

#include \"stdafx.h\"
#include <iostream>
#include <ctime>
#include <fstream>
using namespace std;
class Timer
{     clock_t start_time;
public:
    Timer(){start_time=clock();}
    void elaspe()
        /*计算时间*/
    {
        clock_t end_time=clock();
        cout<<\"It takes \"<<(double)(end_time-start_time)/(double)CLK_TCK<<\"seconds\n\";
    }
    /*时间归零*/
    void reset(){start_time=clock();}
};
#define maxSortNum 4    /*定义排序算法的个数（种类）*/
class CCompositor
{     int *a;
public:
    CCompositor(){a=NULL;}
    ~CCompositor(){delete []a;}
    void FileMenu();
    void Initional(int i);
    void GetFile(ifstream&is,int size);
    void doCompose(int n);
    void sort_1();
    void sort_2();
    void sort_3();
    void sort_4();
};
typedef void (CCompositor::*sort)();
sort g_x[] = {CCompositor::sort_1, CCompositor::sort_2, CCompositor::sort_3, CCompositor::sort_4};
struct SortStruct 
{     int m_iIndex;    //索引
char* m_pChoice; //文件类型
char* m_pFile;     //文件路径
int m_iInfoSize; //文件大小
};
SortStruct sortArr[]={
    1, \"      1. 数据长度20个，   顺序\n\",    \"order20.txt\",            20,
        2, \"      2. 数据长度200个，  顺序\n\",    \"order200.txt\",            200,
        3, \"      3. 数据长度2000个， 顺序\n\",      \"order2000.txt\",            2000,
        4, \"      4. 数据长度20个，   逆序\n\",      \"unOrder20.txt\",            20,
        5, \"      5. 数据长度200个，  逆序\n\",      \"unOrder200.txt\",            200,
        6, \"      6. 数据长度2000个， 逆序\n\",      \"unOrder2000.txt\",        2000,
        7, \"      7. 数据长度20个，   随机\n\",      \"noOrder20.txt\",            20,
        8, \"      8. 数据长度200个，  随机\n\",      \"noOrder200.txt\",            200,
        9, \"      9. 数据长度2000个， 随机\n\",      \"noOrder2000.txt\",        2000,
        10,\"      10.数据长度20个，   部分排序\n\",\"partlyOrder20.txt\",        20,
        11,\"      11.数据长度200个，  部分排序\n\",\"partlyOrder200.txt\",        200,
        12,\"      12.数据长度200个，  部分排序\n\",\"partlyOrder2000.txt\",    2000,
};
void CCompositor::sort_1()
{     //增加代码，完成你的算法
} 
void CCompositor::sort_2()
{     //增加代码，完成你的算法
} 
void CCompositor::sort_3()
{     //增加代码，完成你的算法
} 
void CCompositor::sort_4()
{     //增加代码，完成你的算法
} 
void CCompositor::GetFile(ifstream&is,int size)
{     //if(!is)exit(1);
    delete a;a=NULL;
    a=new int[size];
    for(int i=0;i<size;i++)
        is>>a[i];
} 
void CCompositor::FileMenu()
/*列出所有不同类型的数据*/
{     cout<<\"         算法比较数据文件目录\n\";
cout<<\"      ——————————————\"<<endl;
for (int i=0;i<sizeof(sortArr)/sizeof(SortStruct);i++)
{
    cout<<sortArr[i].m_pChoice;
}
cout<<\"请选择...\";
} void CCompositor::Initional(int i)
/*根据不同的文件数据进行数据加载*/
{     ifstream is;
is.open(sortArr[i-1].m_pFile);
GetFile(is,sortArr[i-1].m_iInfoSize);
is.close();
} 
int _tmain(int argc, _TCHAR* argv[])
{     CCompositor compose;
compose.FileMenu();
int choice;cin>>choice;
compose.Initional(choice);
Timer time;
for(int j=0;j<sizeof(g_x)/4;j++)
{
    g_x[j];    
    time.elaspe();
    time.reset();
}
return 0;
}

不知道这个有用没

效率比较可以用模板的。

参与的数据也应该是多种

应该差不多，我把它改成MFC下的，另外算效率的时候我再加上单步演示的算出各种算法各交换多少次。

三个基本排序，这段时间没什么长进，别的还不行。
高效排序明天吧。


[CODE]//end 是超尾

/*插入排序
最好时间复杂度O(n)，最坏时间复杂度O(n^2)，随机序列的复杂度接近后者。*/

template <class T>
void insertionsort(T *begin, T *end)
{
T *p, *q;
T tmp;
for(p=begin+1; p!=end; p++)
{
tmp = *p;
for(q=p; q!=begin && tmp<*(q-1); q--)
*q = *(q-1);
*q = tmp;
}
}
/*选择排序
最好最坏复杂度都是O(n^2),优点是移动次数较少*/

template <class T>
void selectionsort(T *begin, T *end)
{
T *p, *q, *least;
for(p=begin; p!=end-1; p++)
{
for(q=p+1,least=p; q!=end; q++)
if(*q < *least)
least = q;
if(p != least)
swap(*p, *least);
}
}

/*冒泡排序
时间复杂度是O(n^2),缺点是移动次数较多，认为是三种基本排序中最差的。*/

template <class T>
void bubblesort(T *begin, T *end)
{
T *p, *q;
end--;
for(p=begin; p!=end; p++)
for(q=end; q>p; q--)
if(*q < *(q-1))
swap(*q, *(q-1));
}[/CODE]

[CODE]template <class T>
inline void movedown(T *data, int first, int last)
{
int largest = 2*first + 1;
while(largest <= last)
{
if(largest<last && data[largest]<data[largest+1])
largest++;
if(data[first] < data[largest])
{
swap(data[first], data[largest]);
first = largest;
largest = largest*2 + 1;
}
else
break;
}
}

template <class T>
void heapsort(T *begin, T *end)
{
int size = end - begin;
for(int i=size/2-1; i>=0; i--)
movedown(begin, i, size-1);
for(int j=size-1; j>0; j--)
{
swap(*begin, *(begin+j));
movedown(begin, 0, j-1);
}
}[/CODE]

有没有MFC的变量类型说明, 我一直没分清.

myajax：你的那个首页有点问题，比如我双击以后进入hannuo，然后点首页返回，再点一下其他地方，然后再点hannuo就会发现，hannuo上没有焦点。

我的关于性能测试的想法

先定义一个基类Action，定义比较，移动的方法，同时有记录的变量。

[CODE]template <class T>
class Action
{
public:
pair<int,int> result;

Action() { result.first = 0; result.second = 0; }

bool lessthan(T &a, T &b)
{
result.first++;
return a < b;
}

void move(T &dest, T &source)
{
dest = source;
result.second++;
}

void Swap(T &a, T &b)
{
swap(a, b);
result.second += 3;
}
};[/CODE]

然后每种排序定义为一个由Action派生的类型，其中的比较，移动用基类的方法，如
[CODE]template <class T>
class InsertionSort : public Action<T>
{
void insertionsort(T *begin, T *end)
{
T *p, *q;
T tmp;
for(p=begin+1; p!=end; p++)
{
move(tmp, *p); //--
for(q=p; q!=begin && lessthan(tmp, *(q-1)); q--) //--
move(*q, *(q-1)); //--
move(*q, tmp); //--
}
}
public:

pair<int,int> operator()(T *begin, T *end)
{
Action<T>::result.first = 0;
Action<T>::result.second = 0;
insertionsort(begin, end);
return Action<T>::result;
}

};[/CODE]

[CODE]template <class T>
class HeapSort : public Action<T>
{
void movedown(T *data, int first, int last)
{
int largest = 2*first + 1;
while(largest <= last)
{
if( largest<last && lessthan(data[largest],data[largest+1]) ) //--
largest++;
if( lessthan(data[first], data[largest]) ) //--
{
Swap(data[first], data[largest]); //--
first = largest;
largest = largest*2 + 1;
}
else
break;
}
}
void heapsort(T *begin, T *end)
{
int size = end - begin;
for(int i=size/2-1; i>=0; i--)
movedown(begin, i, size-1);
for(int j=size-1; j>0; j--)
{
Swap(*begin, *(begin+j)); //--
movedown(begin, 0, j-1);
}
}
public:
pair<int,int> operator()(T *begin, T *end)
{
Action<T>::result.first = 0;
Action<T>::result.second = 0;
heapsort(begin, end);
return Action<T>::result;
}
};[/CODE]

我又加了一个函数，这个也许没有必要。
[CODE]template <class T, class U>
pair<int,int> Test(T *begin, T *end, U func)
{
return func(begin, end);
}[/CODE]

测试的主函数，
[CODE]int main()
{
const int N = 1000;
int ar[N], br[N];

for(int i=0; i<N; i++)
ar[i] = br[i] = Random::get().random();

for(int i=0; i<N; i++)
cout<<ar[i]<<' ';
cout<<endl;

pair<int, int> performance = Test(ar, ar+N, HeapSort<int>());
for(int i=0; i<N; i++)
cout<<ar[i]<<' ';
cout<<endl;
cout<<"\nheapsort\ncompare "<<performance.first<<"\nmove "<<performance.second<<endl;

performance = Test(br, br+N, InsertionSort<int>());
for(int i=0; i<N; i++)
cout<<ar[i]<<' ';
cout<<endl;
cout<<"\ninsertionsort\ncompare "<<performance.first<<"\nmove "<<performance.second<<endl;
cin.get();
return 0;
}[/CODE]

在 dev cpp编译通过，vc6不知道怎么样。

woodhead可以试着尽量不用T*
这样，很多时候就必须是数组了
比如容器什么的（一些STL容器），就不能用了

还是学着泛型编程上的那样做吧，一般化些。

PS：虽然我也是才开始看这本书，呵呵，不过觉得它上面说的很有道理