请教一个C++的数字和字符混合排序的算法

Question

请教一个C++的数字和字符混合排序的算法。

输入是一个string array，所有元素本质上都是string，比如 [2, Banana, 1, Apple, 3, Pear]。现在给它排序，要求排序之后的输出是 [1, Apple, 2, Banana, 3, Pear]。总之就是数字与数字排序，字符与字符排序，原来是string的位置放string，是integer的位置放integer（话说回来，其实所有元素本质上都是string，只不过有些是数字形式而已）。

我觉得必须要实现一下判断字符串是否是数字。C++应该直接可以用::isdigit吧？但是请问一下，应该怎么实现原来是string的位置放string、是integer的位置放integer呢？

也许可以用堆排序来实现这个算法。所以另外再请教一个最小堆priority_queue的定义问题。

struct cmp
    {
    bool operator () (int a, int b)
        { return a>b; }
    };
void heaping1()
    {
    priority_queue<int, vector<int>, cmp> pq;

这样定义priority_queue是可以通过编译的。但是，如果改为以下定义：

void heaping2()
    {
    priority_queue<pair<int, char>, cmp> pq;

这样定义priority_queue就无法通过编译了！当然，如果删除了cmp改为最大堆，那么一切正常。所以，请问上面函数中的最小堆应该如何定义呢？cmp应该放在哪里呢？谢谢了先！

Answer 1

不用 inplace (直接分成两个数组排序，再合并) 的话就太简单了，要 inplace 的话其实也可以不用手写 iterator，手写一个 reference 的 wrapper 就行了（然后直接调用任意 常规 inplace 排序算法即可）:

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

template <typename T>
class Ref {
  T & t;

public:

  Ref(T & t) : t(t) {
  }

  Ref(Ref & o) : t(o.t) {
  }

  Ref(Ref && o) : t(o.t) {
  }

  Ref & operator = (Ref & o) {
    t = o.t;
    return *this;
  }

  Ref & operator = (Ref && o) {
    t = move(o.t);
    return *this;
  }

  bool operator < (Ref const & o) const {
    return t < o.t;
  }

  friend void swap(Ref & a, Ref & b) {
    using std::swap;
    swap(a.t, b.t);
  }
};

void solution(vector<string> & ret) {
  vector<Ref<string>> a;
  vector<Ref<string>> b;

  for (auto & c : ret) {
    bool numeric = true;
    for (auto const & d : c) {
      if (!isdigit(d)) numeric = false;
    }
    if (numeric) a.emplace_back(c); else b.emplace_back(c);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  vector<string> v;

  string l;
  getline(cin, l);

  stringstream ss;
  ss << l;

  string s;
  while (ss >> s) {
    v.emplace_back(move(s));
  }

  solution(v);

  bool first = true;
  for (auto const & c : v) {
    if (first) first = false; else cout.put(' ');
    cout << c;
  }
  cout << '\n';
}

测试：

输入

2 Banana 1 Apple 3 Pear

输出

1 Apple 2 Banana 3 Pear

Answer 2

我的想法是先用一个数组标注对应的位置是数字还是字符串，例如对 [2, Banana, 1, Apple, 3, Pear]，有[0,1,0,1,0,1],然后把数字和字符串分别排序放到两个数组nums和strings里，然后按照表示数组放入合适的元素。

Answer 3

这道题主要思路是要用原址排序，例如快排，

• 同时你所有的关于迭代器/或者指针的运算要重载，譬如数字排序时指针加一的含义变为寻找下一个数字的指针。
• 进行两次排序，第一次数字，第二次字符串。

我这里实现了自定义的迭代器，然后用std::sort排序，你也可以自己实现快排，当然可能更简单一些，不过要小心边界。

#include <iterator>
#include <iostream>
#include <cctype>
#include <algorithm>

bool sortNum = true;
bool isNum(const char* num)
{
    while (*num)
    {
        if (!std::isdigit(*num))
            return false;
        ++num;
    }
    return true;
}

class Myiter :public std::iterator<std::random_access_iterator_tag,const char *>
{
    
    const char** ptrStr_= nullptr;
    const char** end_ = nullptr;
    const char** begin_ = nullptr;
public:
    explicit Myiter(const char** ptr=nullptr):ptrStr_(ptr) {}
    Myiter(const Myiter& that) :ptrStr_(that.ptrStr_),end_(that.end_) {}
    Myiter& setEnd(const char** end) { end_ = end; return *this; }
    Myiter& setBegin(const char** begin) { begin_ = begin; return *this; }

    Myiter& operator++()
    {
        ++ptrStr_;
        while ( ptrStr_!= end_)
        {
            auto str = *ptrStr_;
            if (sortNum)
            {
                if (isNum(*ptrStr_))
                    return *this;
            }
            else
            {
                if (!isNum(*ptrStr_))
                    return *this;
            }
            ++ptrStr_;
        }
        return *this;
    }

    Myiter operator++(int)
    {
        Myiter tmp(*this);
        ++tmp;
        return tmp;
    }

    Myiter& operator+=(difference_type n)
    {
        while (--n != 0)
            ++*this;
        return *this;
    }

    Myiter operator+(difference_type n)
    {
        Myiter tmp(*this);
        tmp += n;
        return tmp;
    }

    Myiter& operator--()
    {
        while (--ptrStr_!=begin_)
        {
            auto str = *ptrStr_;
            if (sortNum)
            {
                if (isNum(*ptrStr_))
                    return *this;
            }
            else
            {
                if (!isNum(*ptrStr_))
                    return *this;
            }
        }
        return *this;
    }

    Myiter operator--(int)
    {
        Myiter tmp(*this);
        --tmp;
        return tmp;
    }

    Myiter& operator-=(difference_type n)
    {
        while (--n != 0)
            --*this;
        return *this;
    }

    Myiter operator-(difference_type n)
    {
        Myiter tmp(*this);
        tmp -= n;
        return tmp;
    }

    reference operator*() const { return *ptrStr_; }
    bool operator!=(const Myiter& that) { return ptrStr_ != that.ptrStr_; }
    bool operator==(const Myiter& that) { return ptrStr_ == that.ptrStr_; }
    bool operator<(const Myiter& that) { return ptrStr_ < that.ptrStr_; }
    bool operator>(const Myiter& that) { return ptrStr_ > that.ptrStr_; }
    bool operator<=(const Myiter& that) { return ptrStr_ <= that.ptrStr_; }
    bool operator>=(const Myiter& that) { return ptrStr_ >= that.ptrStr_; }
    difference_type operator-(const Myiter& that)
    {
        Myiter tmp(that);
        difference_type n = 0;
        while ((*this)!= tmp)
        {
            ++n;
            ++tmp;
        }
        return n;
    }
};

template<size_t N>
void sortAndPrint(const char* (&test)[N] )
{
    std::cout << "Before sort:\n";
    for (auto i : test)
    {
        std::cout << i << " ";
    }
    std::cout << "\n";
    auto size = N;
    auto end = test + size;
    auto begin = test;
    auto startNum = test;
    auto startStr = test;
    bool gotStartNum = false;
    bool gotStartStr = false;
    for (; begin != end; ++begin)
    {
        if (gotStartNum&&gotStartStr) break;

        if (isNum(*begin))
        {
            if (gotStartNum) continue;
            startNum = begin;
            gotStartNum = true;
        }
        else
        {
            if (gotStartStr) continue;
            startStr = begin;
            gotStartStr = true;
        }
    }
    sortNum = true;
    std::sort(Myiter(startNum).setBegin(startNum).setEnd(end), Myiter(end).setBegin(startNum).setEnd(end), [](const char* a, const char *b)
    {
        auto aNum = atoi(a);
        auto bNum = atoi(b);
        return aNum < bNum;
    });
    sortNum = false;
    std::sort(Myiter(startStr).setBegin(startStr).setEnd(end), Myiter(end).setBegin(startStr).setEnd(end), [](const char* a, const char *b)
    {
        return strcmp(a, b) < 0;
    });
    std::cout << "After sort:\n";
    for (auto i : test)
    {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

int main()
{
    const char * test[] = { "3","1","Charlie","Alpha","Bravo" };
    const char * test2[] = { "2", "Banana", "1", "Apple", "3", "Pear" };
    sortAndPrint(test);
    sortAndPrint(test2);
    system("PAUSE");
}