2

我创建它是为了更好地理解排序算法和通用函数。我已经实现了一个基本的插入排序算法，并且我试图让它与多个数据结构（至少列表和数组）一起工作。

因为我可以访问这样的列表：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;
}

不幸的是，我似乎根本无法让这个通用函数正确排序。我一直在看这个很长一段时间没有运气。想法？

4

3 回答 3

8

发布仅供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. 享受。

于 2013-08-26T22:57:45.670 回答
3

我认为您对取消引用迭代器/指针感到困惑。这应该有效：

template <class T>
T insertionsort(T a)
{
    if(a.begin() == a.end()) // return a when it's empty
        return a;
    for(auto i = a.begin() + 1; i < a.end(); ++i)
    {
        auto k = *i; // k is the value pointed by i
        auto j = i - 1;
        while(j >= a.begin() && *j > k)  
        {
            *(j + 1) = *j; // writen in 2 lines for clarity
            j--;
        }
        *(j + 1) = k;
    }  
    return a;
}
于 2013-08-26T22:24:12.693 回答
3

对于更通用的解决方案，最好传递要排序的范围而不是要排序的东西，就像标准算法一样std::sort()：

template <typename BIDIRECTIONAL_ITERATOR>
void insertionsort(BIDIRECTIONAL_ITERATOR begin , BIDIRECTIONAL_ITERATOR end) //Note that the iterators
{                                                                             //are passed by value
    if( begin == end ) return; //If the range is empty, abort

    for(auto i = begin + 1; i < end; ++i)
    {
        auto j = i - 1;
        bool flag = false; //Used to abort the loop after j == begin case
        while(!flag && (j != begin || (flag = j == begin)) && *j > *i)  
        {
          *(j + 1) = *j;
          j -= !flag; //If j == begin, don't decrement (Without branch)
        }
        *(j + 1) = *i;
    }  
}

该函数是一个过程，不返回任何内容，对原始范围进行排序。

于 2013-08-26T22:36:27.723 回答