¿Cómo ordenar la matriz de cadenas que contiene números negativos y positivos en c ++.?

String str[]={"-123","89","-10","456"};

stres una matriz de cadenas, con cada cadena en el formato de un entero, y debe realizar la clasificación en esta matriz a O(n log n)tiempo.

Las cadenas en strpueden representar enteros positivos y negativos. La longitud máxima de estas cadenas es de 1024 caracteres.

Sé que una solución de este problema es convertir las cadenas en números, luego compararlos aparte de esto; ¿Hay alguna otra solución a este problema?

Otra solución es implementar su propia función de comparación:

• Verifique el primer carácter de ambas cadenas. Si uno comienza con un dígito y el otro comienza con un -, entonces la cadena que comienza con - es el número más pequeño.
• Si ambas cadenas comienzan con un dígito, compare la longitud de las cadenas. La cadena más corta es el número más pequeño. Si ambas cadenas tienen la misma longitud, realice una comparación de cadena estándar.
• Si ambas cadenas comienzan con -, entonces compare la longitud de las cadenas. La cadena más larga es el número más pequeño. Si ambas cadenas tienen la misma longitud, realice una comparación de cadena estándar, pero niegue el resultado.

Aquí hay un ejemplo mínimo y potencialmente insuficiente (no maneja ceros iniciales, espacios en blanco, etc.) que hace lo que desea.

Los comentarios explican lo que está haciendo. :)

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

int main() {
  std::vector<std::string> strings = {
      "-1", "-1", "-20", "-4", "3", "0", "-0", "1", "20", "20", "44020",
  };

  // Assumes everything in "strings" has no whitespace in it.
  // Assumes everything in "strings" does not have leading zeroes.
  // Assumes everything in "strings" is an ascii representaion of an integer.
  // Assumes everything in "strings" is nonempty.
  std::sort(strings.begin(), strings.end(),
            [](const std::string &a, const std::string &b) {
              const bool a_is_negative = a[0] == '-';
              const bool b_is_negative = b[0] == '-';
              if (a_is_negative != b_is_negative) {
                // If they have different signs, then whichever is negative is
                // smaller.
                return a_is_negative;
              } else if (a.length() != b.length()) {
                // If they have the same sign, then whichever has more
                // characters is larger in magnitude. When the sign is negative,
                // the longer (more digits) number is "more negative". When
                // positive, the longer (more digits) number is "more positive".
                return (a.length() < b.length()) != a_is_negative;
              } else {
                // Otherwise a lexicographic comparison of "a" and "b" will
                // determine which string is larger in magnitude. Using the same
                // logic above, we account for the "negative vs. positive"
                // comparison.
                return (a < b) != a_is_negative;
              }
            });

  for (const auto &str : strings) {
    std::cout << str << " ";
  }
  std::cout << std::endl;
}