闲着无聊发几个排序的代码

#ifndef _INSERTIONSORT_H_
#define _INSERTIONSORT_H_

#include <iterator>

template <typename RanIt>
void InsertionSort(RanIt first, RanIt last)
{
    RanIt j;
    typename std::iterator_traits<RanIt>::value_type key;
    for (RanIt i = first; ++i < last; *j = key)
    {
        key = *i;
        for (j = i; j > first && key < *(j - 1); ++j)
            *j = *(j - 1);
    }
}

#endif

#ifndef _MERGESORT_H_
#define _MERGESORT_H_

#include <iterator>
#include <vector>
#include <algorithm>

template <typename RanIt>
void MergeSort(RanIt first, RanIt last)
{
    if (last - first <= 1)
        return;

    RanIt mid = first + (last - first) / 2;
    
    MergeSort(first, mid);
    MergeSort(mid, last);

    std::vector<typename std::iterator_traits<RanIt>::value_type> buffer;
    buffer.reserve(last - first);
    
    RanIt i = first, j = mid;

    while (i < mid || j < last)
    {
        if (i >= mid)
        {
            buffer.push_back(*j);
            ++j;
        }
        else if (j >= last)
        {
            buffer.push_back(*i);
            ++i;
        }
        else
        {
            if (*i < *j)
            {
                buffer.push_back(*i);
                ++i;
            }
            else
            {
                buffer.push_back(*j);
                ++j;
            }
        }
    }
    
    std::copy(buffer.begin(), buffer.end(), first);
}

#endif

#ifndef _HEAP_H_
#define _HEAP_H_

#include <algorithm>
#include <iterator>

namespace
{
    template <typename T>
    inline T PARENT(T n)
    {
        return (n - 1) / 2;
    }

    template <typename T>
    inline T LEFT(T n)
    {
        return n * 2 + 1;
    }

    template <typename T>
    inline T RIGHT(T n)
    {
        return n * 2 + 2;
    }
}

template <typename RanIt>
void PushHeap(RanIt first, RanIt last)
{
    --last;

    while (*(first + PARENT(last - first)) < *last)
    {
        std::iter_swap(first + PARENT(last - first), last);
        last = first + PARENT(last - first);
    }
}

template <typename RanIt>
void PopHeap(RanIt first, RanIt last)
{
    std::iter_swap(first, --last);

    for (RanIt curr = first; curr < first + PARENT(last - first);)
    {
        if (*curr < *(first + RIGHT(curr - first)) && *(first + LEFT(curr - first)) < *(first + RIGHT(curr - first)))
        {
            std::iter_swap(curr, first + RIGHT(curr - first));
            curr = first + RIGHT(curr - first);
        }
        else if (*curr < *(first + LEFT(curr - first)) && *(first + RIGHT(curr - first)) < *(first + LEFT(curr - first)))
        {
            std::iter_swap(curr, first + LEFT(curr - first));
            curr = first + LEFT(curr - first);
        }
        else
            return;
    }
}

template <typename RanIt>
void MakeHeap(RanIt first, RanIt last)
{
    for (RanIt curr = first; ++curr <= last; PushHeap(first, curr));
}

template <typename RanIt>
void HeapSort(RanIt first, RanIt last)
{
    MakeHeap(first, last);
    for (RanIt curr = last; first < curr; --curr)
        PopHeap(first, curr);
}

#endif

#ifndef _QUICKSORT_H_
#define _QUICKSORT_H_

#include <iterator>
#include <algorithm>
#include "InsertionSort.h"

namespace {
    template <typename T>
    inline T MEDIAN(T x, T y, T z)
    {
        if (x < y)
        {
            if (y < z)
                return y;
            else if (x < z)
                return z;
            else
                return x;
        }
        else
        {
            if (x < z)
                return x;
            else if (y < z)
                return z;
            else
                return y;
        }
    }

    template <typename RanIt>
    RanIt UnguardedPartition(RanIt first, RanIt last, typename std::iterator_traits<RanIt>::value_type pivot)
    {
        for (;; std::iter_swap(first, last))
        {
            while (*first < pivot)
                ++first;
            while (pivot < *--last);

            if (last < first)
                return first;
        }
    }

    template <typename RanIt>
    void QuickSortAux(RanIt first, RanIt last)
    {
        if (last - first < 20)
            return;
        RanIt middle = UnguardedPartition(first, last, MEDIAN(*first, *(last - 1), *(first + (last - first) / 2)));
        QuickSortAux(first, middle);
        QuickSortAux(middle, last);
    }
}

template <typename RanIt>
void QuickSort(RanIt first, RanIt last)
{
    QuickSortAux(first, last);
    InsertionSort(first, last);
}


#endif

=!=支持下...

其实还可以优化
懒得�

哈哈 很少看见 Leeroy 发代码啊?

我这不无聊这么……

想写个红黑树的类但是一直懒的动= =

- -!

最近很无聊呢 写C++的代码又提不起精神 写ASM又不知道写什么呢 ....

楼主,请允许我先顶下你的贴子，然后copy你的代码去研究研究
o(T_T)o

顺便问一下，怎么用C++实现一个自己的哈希表呢？请给个思路，谢谢了�

继承了 algorithm 的优良传统……
使用RanIt first，RanIt last而不是int a[] size_t size这样的形式
有好有坏，对insertion较好，而其他的为了计算size得做减法…�

2楼的怎么没有用 xxx方法？
merge怎么用了copy？

 Leeroy为什么不优化一下，方便别人（比如我�

因为我所说的优化……STL中的sort()已经做得很好了

那个UnguardedPartition就是受了STL的启发

merge用copy是因为我太懒了……那里的vector和copy直接用数组和for是一样的效果，如果还要和copy做一样的优化的话还要再调用一个模板函数，针对T*进行特化（使用memcpy）


Dev-C++中的STL很容易读懂，当然你要忽略那些concept检查宏