怎么实现迭代器还不会，另外上面的heapsort只能用数组。

myajax95又消失了

这星期比较忙，周末也不在，可能下周开始。wfpb说的list control那个问题我看到了。大概是少设了一个always show selection的参数。
同时我正在作一个排序的UI上用到的显示没个数据的小方块的控件。

实话，这种项目既然没有策划人，就应该有领头人，myajax95，等你忙完了这阵子，再就要真正的搞一场了。

快速排序已经有了，就不再写了。


[CODE]template <class T>
class MergaSort: public Action<T>
{
T *p, *tmp;

void mergasort(int begin, int end)
{
int middle;
if(begin < end-1)
{
middle = (begin + end)/2;
mergasort(begin, middle);
mergasort(middle, end);
merga(begin, middle, end);
}
}

void merga(int begin, int middle, int end)
{
int i = 0; //tmp* index
int i1 = begin;
int i2 = middle;

while(i1!=middle && i2!=end)
{
if(lessthan(p[i1], p[i2]))
move(tmp[i++], p[i1++]);
else
move(tmp[i++], p[i2++]);
}

while(i1 < middle)
move(tmp[i++], p[i1++]);
while(i2 < end)
move(tmp[i++], p[i2++]);

for(i=0,i1=begin; i1!=end; i++,i1++)
move(p[i1], tmp[i]);
}

public:

pair<int,int> operator()(T *begin, T *end)
{
p = begin;
int size = end - begin;
tmp = new T[size];
mergasort(0,size);
delete[]tmp;
return Action<T>::result;
}

};[/CODE]

感觉移动次数太多，不知道有没有错误。

我这段时间在看泛型编程，有时间我试着把它改成泛型的，锻炼一下。

//end  是超尾

/*插入排序 
最好时间复杂度O(n)，最坏时间复杂度O(n^2)，随机序列的复杂度接近后者。*/
template <class BidirectionalIterator>
//因为需要迭代器的有(++、--、=、!=)这几个功能，所以需要BinaryIterator这种concept
void insertionsort(BidirectionalIterator begin, BidirectionalIterator end)
{
    BidirectionalIterator p, q;
    typedef  typename iterator_traits<BidirectionalIterator>::value_type value_type;  //迭代器所指的对象的型别
    value_type tmp;
    begin++;
    p=begin;
    begin--;
    for(; p!=end; p++)
    {
        tmp = *p;
        for(q=p; q!=begin && tmp<*(q-1); q--)
            *q = *(q-1);
        *q = tmp;
    }
}
/*选择排序 
最好最坏复杂度都是O(n^2),优点是移动次数较少*/
template <class BidirectionalIterator>    //同上
void selectionsort(BidirectionalIterator begin,BidirectionalIterator end)
{
    BidirectionalIterator p, q, least;
    end--;
    BidirectionalIterator end_It=end;
    end++;
    for(p=begin; p!=end_It; 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 BidirectionalIterator>
void bubblesort(BidirectionalIterator begin, BidirectionalIterator end)
{
    BidirectionalIterator p, q;
    end--;
    for(p=begin; p!=end; p++)
        for(q=end; q>p; q--)
            if(*q < *(q-1))
                swap(*q, *(q-1));
}

我没有使用Random Access Iterator,因为这里使用Bidirectional Iterator就足够了。

[此贴子已经被作者于2006-10-9 14:16:26编辑过]

value_type是每个都会有的，iterator为每个预定义的Iterator都typedef好了。也为指针特化了。所以可以直接使用。
template<class It>
struct iterator_traits;
template<class T>
struct iterator_traits<T *>;

template<class RandomAccessIterator,class Distance>
void movedown(RandomAccessIterator data, Distance first,Distance last)
{
    Distance 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 RandomAccessIterator>
void heapsort(RandomAccessIterator begin,RandomAccessIterator end)
{
    typedef typename iterator_traits<RandomAccessIterator>::distance_type distance_type;
    distance_type size = end - begin;
    for(distance_type i=size/2-1; i>=0; i--)
        movedown(begin, i, size-1);
    for(distance_type j=size-1; j>0; j--)
    {
        swap(*begin, *(begin+j)); //--
        movedown(begin, 0, j-1);
    }
}

---------------------------------------------------------------------------
To Woodhead:
我应该没有改变你的意思吧~！
不知道有没有哪里疏忽了，如果发现就在这个帖子回复吧！

[此贴子已经被作者于2006-10-9 17:02:35编辑过]

试过能运行就可以吧，我这方面确实不行。