Естественный алгоритм Сортировки

Вот то, как можно получить подобное проводнику поведение в Python:

#!/usr/bin/env python
"""
>>> items = u'a1 a003 b2 a2 a10 1 10 20 2 c100'.split()
>>> items.sort(explorer_cmp)
>>> for s in items:
...     print s,
1 2 10 20 a1 a2 a003 a10 b2 c100
>>> items.sort(key=natural_key, reverse=True)
>>> for s in items:
...     print s,
c100 b2 a10 a003 a2 a1 20 10 2 1
"""
import re

def natural_key(astr):
    """See http://www.codinghorror.com/blog/archives/001018.html"""
    return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', astr)]

def natural_cmp(a, b):
    return cmp(natural_key(a), natural_key(b))

try: # use explorer's comparison function if available
    import ctypes
    explorer_cmp = ctypes.windll.shlwapi.StrCmpLogicalW
except (ImportError, AttributeError):
    # not on Windows or old python version
    explorer_cmp = natural_cmp        

if __name__ == '__main__':
    import doctest; doctest.testmod()

Для поддержки строк Unicode, .isdecimal() должен использоваться вместо .isdigit().

.isdigit() может также перестать работать (возвращаемое значение, которое не принято int()) для строки байтов на Python 2 в некоторых локалях, например, '\xb2' ('ВІ') в cp1252 локали в Windows .

В C++ я использую этот пример кода , чтобы сделать естественную сортировку. Код требует библиотеки повышения.

Я просто использую StrCmpLogicalW. Это делает точно, что желает Jeff, так как это - тот же API тот проводник использование. По общему признанию это не портативно.

В C++:

bool NaturalLess(const wstring &lhs, const wstring &rhs)
{
    return StrCmpLogicalW(lhs.c_str(), rhs.c_str()) < 0;
}

vector<wstring> strings;
// ... load the strings
sort(strings.begin(), strings.end(), &NaturalLess);

Если OP спрашивает о idomatic выражениях для сортировки, то не все языки имеют естественный , выражение встроило. Для c я перешел бы в <stdlib.h> и использование qsort. Что-то на строках:

/* non-functional mess deleted */

для сортировки аргументов в лексический порядок. К сожалению, эту идиому довольно трудно проанализировать для не используемых способы c.

Соответственно наказанный downvote, я на самом деле прочитал связанную статью. Моя вина.

В anycase исходный код не работал, кроме единственного случая, который я протестировал. Чертовски. Простая ваниль c не имеет этой функции, ни является ею в любой из обычных библиотек.

код ниже видов параметры командной строки в естественный путь, как связано. Принцип "качество на риск покупателя" , поскольку это только слегка тестируется.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int naturalstrcmp(const char **s1, const char **s2);

int main(int argc, char **argv){
  /* Sort the command line arguments in place */
  qsort(&argv[1],argc-1,sizeof(char*),
    (int(*)(const void *, const void *))naturalstrcmp);

  while(--argc){
    printf("%s\n",(++argv)[0]);
  };
}

int naturalstrcmp(const char **s1p, const char **s2p){
  if ((NULL == s1p) || (NULL == *s1p)) {
    if ((NULL == s2p) || (NULL == *s2p)) return 0;
    return 1;
  };
  if ((NULL == s2p) || (NULL == *s2p)) return -1;

  const char *s1=*s1p;
  const char *s2=*s2p;

  do {
    if (isdigit(s1[0]) && isdigit(s2[0])){ 
      /* Compare numbers as numbers */
      int c1 = strspn(s1,"0123456789"); /* Could be more efficient here... */
      int c2 = strspn(s2,"0123456789");
      if (c1 > c2) {
    return 1;
      } else if (c1 < c2) {
    return -1;
      };
      /* the digit strings have equal length, so compare digit by digit */
      while (c1--) {
    if (s1[0] > s2[0]){
      return 1;
    } else if (s1[0] < s2[0]){
      return -1;
    }; 
    s1++;
    s2++;
      };
    } else if (s1[0] > s2[0]){
      return 1;
    } else if (s1[0] < s2[0]){
      return -1;
    }; 
    s1++;
    s2++;
  } while ( (s1!='\0') || (s2!='\0') );
  return 0;
}

Этот подход является довольно грубой силой, но это просто и может, вероятно, быть дублировано на любом императивном языке.

Вот очистка код в статья вопрос, связанный с:

def sorted_nicely(strings): 
    "Sort strings the way humans are said to expect."
    return sorted(strings, key=natural_sort_key)

def natural_sort_key(key):
    import re
    return [int(t) if t.isdigit() else t for t in re.split(r'(\d+)', key)]

, Но на самом деле у меня не было случая для сортировки чего-либо этот путь.

Для MySQL я лично использую код от модуля Drupal, который доступен в hhttp://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/natsort.install.mysql

В основном, Вы выполняете отправленный сценарий SQL для создания функций, и затем использовать ORDER BY natsort_canon(field_name, 'natural')

Вот readme о функции: http://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/README.txt

источник JavaScript

Array.prototype.alphanumSort = function(caseInsensitive) {
  for (var z = 0, t; t = this[z]; z++) {
    this[z] = [], x = 0, y = -1, n = 0, i, j;

    while (i = (j = t.charAt(x++)).charCodeAt(0)) {
      var m = (i == 46 || (i >=48 && i <= 57));
      if (m !== n) {
        this[z][++y] = "";
        n = m;
      }
      this[z][y] += j;
    }
  }

  this.sort(function(a, b) {
    for (var x = 0, aa, bb; (aa = a[x]) && (bb = b[x]); x++) {
      if (caseInsensitive) {
        aa = aa.toLowerCase();
        bb = bb.toLowerCase();
      }
      if (aa !== bb) {
        var c = Number(aa), d = Number(bb);
        if (c == aa && d == bb) {
          return c - d;
        } else return (aa > bb) ? 1 : -1;
      }
    }
    return a.length - b.length;
  });

  for (var z = 0; z < this.length; z++)
    this[z] = this[z].join("");
}

Просто ссылка на некоторую хорошую работу в языке Common LISP Eric Normand:

http://www.lispcast.com/wordpress/2007/12/human-order-sorting/

Для Tcl, опция -dict (словарь) для lsort:

% lsort -dict {a b 1 c 2 d 13}
1 2 13 a b c d

Обратите внимание, что по большинству таких вопросов вы можете просто обратиться к Rosetta Code Wiki . Я адаптировал свой ответ из записи для сортировки целых чисел.

На языке программирования системы делать что-то подобное, как правило, будет сложнее, чем с помощью специализированного языка обработки строк. К счастью для Ады, в самой последней версии есть подпрограмма библиотеки только для такого рода задач.

Для Ады 2005 я считаю, что вы могли бы сделать что-то вроде следующего (предупреждение, не скомпилировано!):

type String_Array is array(Natural range <>) of Ada.Strings.Unbounded.Unbounded_String;
function "<" (L, R : Ada.Strings.Unbounded.Unbounded_String) return boolean is
begin
   --// Natural ordering predicate here. Sorry to cheat in this part, but
   --// I don't exactly grok the requirement for "natural" ordering. Fill in 
   --// your proper code here.
end "<";
procedure Sort is new Ada.Containers.Generic_Array_Sort 
  (Index_Type   => Natural;
   Element_Type => Ada.Strings.Unbounded.Unbounded_String,
   Array_Type   => String_Array
  );

Пример использования:

    using Ada.Strings.Unbounded;

    Example : String_Array := (To_Unbounded_String ("Joe"),
                               To_Unbounded_String ("Jim"),
                               To_Unbounded_String ("Jane"),
                               To_Unbounded_String ("Fred"),
                               To_Unbounded_String ("Bertha"),
                               To_Unbounded_String ("Joesphus"),
                               To_Unbounded_String ("Jonesey"));
begin
    Sort (Example);
    ...
end;

В C это решение правильно обрабатывает числа с ведущими нулями:

#include <stdlib.h>
#include <ctype.h>

/* like strcmp but compare sequences of digits numerically */
int strcmpbynum(const char *s1, const char *s2) {
  for (;;) {
    if (*s2 == '\0')
      return *s1 != '\0';
    else if (*s1 == '\0')
      return 1;
    else if (!(isdigit(*s1) && isdigit(*s2))) {
      if (*s1 != *s2)
        return (int)*s1 - (int)*s2;
      else
        (++s1, ++s2);
    } else {
      char *lim1, *lim2;
      unsigned long n1 = strtoul(s1, &lim1, 10);
      unsigned long n2 = strtoul(s2, &lim2, 10);
      if (n1 > n2)
        return 1;
      else if (n1 < n2)
        return -1;
      s1 = lim1;
      s2 = lim2;
    }
  }
}

Если вы хотите использовать его с qsort , используйте эту вспомогательную функцию:

static int compare(const void *p1, const void *p2) {
  const char * const *ps1 = p1;
  const char * const *ps2 = p2;
  return strcmpbynum(*ps1, *ps2);
}

И вы можете сделать что-то в порядке

char *lines = ...;
qsort(lines, next, sizeof(lines[0]), compare);