請教一個C++的數(shù)字和字符混合排序的算法

不用 inplace (直接分成兩個數(shù)組排序，再合并) 的話就太簡單了，要 inplace 的話其實也可以不用手寫 iterator，手寫一個 reference 的 wrapper 就行了（然后直接調用任意 常規(guī) 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

我的想法是先用一個數(shù)組標注對應的位置是數(shù)字還是字符串，例如對 [2, Banana, 1, Apple, 3, Pear]，有[0,1,0,1,0,1],然后把數(shù)字和字符串分別排序放到兩個數(shù)組nums和strings里，然后按照表示數(shù)組放入合適的元素。

這道題主要思路是要用原址排序，例如快排，

• 同時你所有的關于迭代器/或者指針的運算要重載，譬如數(shù)字排序時指針加一的含義變?yōu)閷ふ蚁乱粋€數(shù)字的指針。
• 進行兩次排序，第一次數(shù)字，第二次字符串。

我這里實現(xiàn)了自定義的迭代器，然后用std::sort排序，你也可以自己實現(xiàn)快排，當然可能更簡單一些，不過要小心邊界。

#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");
}