C++通用插入排序

Question

我正在创建它以尝试更好地理解排序算法和通用函数.我已经实现了一个基本的插入排序算法,我试图使它适用于多个数据结构(至少列表和数组).

因为我可以访问这样的列表:list [N]来获取值,我想我需要使用迭代器.所以我试图转换我的解决方案.这是我试图修改的基本插入排序算法:

int *insertionsort(int *a)
{
  for (int i = 1; i<length(a); ++i)
  {
    int k = a[i];
    int j = i-1;
    {
      while (j>=0 && a[j] > k)
      { 
        a[j+1] = a[j--];
      }
    a[j+1] = k;
  }
  return a;
}

这是我迄今为止通用版本的内容:

template <class T>
T insertionsort(T a)
{
  for (auto i = a.begin()+1; i<a.end(); ++i)
  {
    auto k = i;
    auto j = i-1;
    while (j>=a.begin() && *j>*k)  
    {
      (j + 1) = j--; 
    }
    (j + 1) = k;
  }  
   return a;
} 

Unfortunatley我似乎无法让这个通用函数正确排序.我一直在看这个,没有运气.想法？

Answer 1

发布仅供OP参考,不太可能过上长寿.如果您倾向于使用C++ 11并且不喜欢打字,那么这可能就行了.

template<typename Iter>
void insertion_sort(Iter first, Iter last)
{
    for (Iter it = first; it != last; ++it)
        std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}

所用函数的相关链接:

std::upper_bound,std::next和std::rotate.请享用.