Ordenação de Strings com Números em Java

A ordenação de Strings em Java normalmente é utilizada com o java.util.Comparator da própria classe String, mas existe um pequeno detalhe quando os nossos textos possuem números em sua composição.
Imagine o seguinte conjunto de Strings:
"img_1", "img_5", "img_10"
Ao ordenar estas Strings com a ordenação padrão do Java teremos:
"img_1", "img_10", "img_5"
Mas este resultado não é útil quando se espera uma ordenação conceitual onde os números devem representar uma ordem dentro do conjunto de informações. Então, nesta postagem venho compartilhar uma solução para este problema.

A pesquisa

Bem, primeiramente temos que tentar não reinventar a roda certo? Então fui ao Google...
A melhor página que encontrei foi esta: http://blog.gomilko.com/2007/05/31/natural-order-for-strings-with-numbers-in-java
Nesta postagem o colega blogueiro detalha um pouco do problema também, e comenta que ele também foi a busca de soluções, encontrando algumas e depois fazendo um comparativo entre as soluções que ele encontrou com base na performance de execução.
A informação mais importante que ele compartilha, na minha opinião, é a não existência de solução dos grandes contribuidores de códigos Java como Apache, Google e Eclipse, e durante a minha pesquisa esta situação se manteve, então, caso alguém tenha novidades sobre esta área, por favor compartilhe conosco.

A solução

Como não existe solução confiável, parti para a análise das soluções listadas pelo colega blogueiro (com exceção da primeira que está com o link quebrado). Particularmente, não gostei muito das soluções, então, pensei em fazer um código meu para comparação.
O resultado, que apresento logo abaixo, foi testado em contrabalanço com o código do Stephen Friedrich e eu apenas precisei adicionar o controle de nulos que o código dele não possui. Meus testes demonstraram que meu código foi mais rápido mas teve maior custo de memória, e a ordenação apresentou diferenças em textos com ponto e sublinhado ('.' e '_').
Como conclusão reforço que minha solução não é um algoritmo limpo e extensivamente testado, e também não classifico como código confiável, mas sinta-se livre para utilizar este código do jeito que está, bem como pode alterá-lo a vontade. Dentro das possibilidades de alteração destaco alguns dos conceitos que utilizei:
- Nulos são tratados e aparecem primeiro na classificação;
- Zeros a esquerda são considerados e implicam na ordenação ("1" < "01" < "1.1");
- Espaços são considerados como partes de texto puro e influenciam na ordenação ("img1" < "img2" < "img 1");
- A comparação com "ignore case" pode ser removida em alguns casos;
- Pode ser interessante adicionar um controle para ordenação decrescente.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class NaturalOrdering {

 public static void main(String[] args) {
  String[] versoes = { "v1.1", "v1.2.1", "v1.11", "v2.0", "v11.0", "img1", "img 2", "img11", "img2", "1.1", "1.2.1", "1.11", "2.0", "11.0", "1_1", "1_2_1", "1_11", "2_0", "1", "01", "2a", "1a", "0001", "00012", null };

  ArrayList<String> aOrdenar = new ArrayList<String>();
  for(String s : versoes) {
   aOrdenar.add(s);
  }

  Collections.shuffle(aOrdenar);

  System.out.println(System.currentTimeMillis());

  for(int i = 0; i < 100000; i++) {
   Collections.sort(aOrdenar, new NaturalComparator());
  }
  System.out.println(System.currentTimeMillis());
  System.out.println(aOrdenar);
 }
 
}

class NaturalComparator implements Comparator<String> {
 private boolean ignoreCase;

 public NaturalComparator() {
  this(false);
 }

 public NaturalComparator(boolean ignoreCase) {
  super();
  this.ignoreCase = ignoreCase;
 }

 @Override
 public int compare(String o1, String o2) {
  int result = 0;

  // trantando nulos, nulos em primeiro
  if(o1 == null && o2 == null) {
   return 0;
  } else if(o1 == null) {
   return -1;
  } else if(o2 == null) {
   return 1;
  }

  // strings iguais, não é necessário o resto do teste
  if(ignoreCase) {
   result = o1.compareToIgnoreCase(o2);
  } else {
   result = o1.compareTo(o2);
  }
  if(result == 0) {
   return result;
  }

  // string vazia é menor
  if(o1.isEmpty()) {
   return -1;
  }
  if(o2.isEmpty()) {
   return 1;
  }

  // daqui em diante consideramos uma "parte" como um conjunto contínuo de números ou não-números 

  // extraindo primeira parte de o1
  int o1i = 0;
  boolean o1IsDigit = Character.isDigit(o1.charAt(o1i++));
  for(; o1i < o1.length(); o1i++) {
   if(Character.isDigit(o1.charAt(o1i)) != o1IsDigit) {
    break;
   }
  }
  String o1Part = o1.substring(0, o1i);

  // extraindo primeira parte de o2
  int o2i = 0;
  boolean o2IsDigit = Character.isDigit(o2.charAt(o2i++));
  for(; o2i < o2.length(); o2i++) {
   if(Character.isDigit(o2.charAt(o2i)) != o2IsDigit) {
    break;
   }
  }
  String o2Part = o2.substring(0, o2i);

  // comparando ambas as partes
  if(ignoreCase) {
   result = o1Part.compareToIgnoreCase(o2Part);
  } else {
   result = o1Part.compareTo(o2Part);
  }
  // armazenar resultado nível 1
  int resultL1 = result;
  // se as partes são iguais, ignorar teste numérico
  if(result != 0) {
   // se ambas as partes são numéricas, então realizar teste numérico
   if(o1IsDigit && o2IsDigit) {
    try {
     Integer n1 = Integer.parseInt(o1Part);
     Integer n2 = Integer.parseInt(o2Part);
     // se números obtidos não são iguais, então teste numérico, senão, considerar teste textual
     if(n1 != n2) {
      result = n1.compareTo(n2);
     } else {
      result = 0;
      // inverter resultado nível 1 pois zeros a esquerda são relevantes
      resultL1 *= -1;
     }
    } catch(NumberFormatException nbe) {
     // não deve entrar aqui pois nós testamos para partes numéricas
     result = resultL1;
    }
   }
  }

  // se partes não são iguais
  if(result != 0) {
   return result;
  }

  // partes são iguais, então continuar teste do resto da string
  String o1Rest = o1.substring(o1i);
  String o2Rest = o2.substring(o2i);
  result = compare(o1Rest, o2Rest);
  // se o teste do resto retornar igual levar em consideração o resultado nível 1
  if(result == 0) {
   return resultL1;
  } else {
   return result;
  }
 }
}