Алгоритм естественной сортировки

Вот как вы можете получить поведение, подобное проводнику в 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 locale в Windows .

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

Источник

Вот очистка кода в статье, связанная с:

 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')

Ниже приведено описание функции: http://drupalcode.org/project/natsort.git/blob/refs/heads/5.x-1.x:/README.txt

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

 /* non-functional mess deleted */ 

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

Подходящий под удар, я действительно прочитал связанную статью. Моя вина.

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

Нижеприведенный код сортирует аргументы командной строки естественным образом как связанные. Предостережение emptor, поскольку оно только слегка проверено.

 #include  #include  #include  #include  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; } в #include  #include  #include  #include  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; } 

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

Я просто использую StrCmpLogicalW . Он делает именно то, что хочет Джефф, поскольку это тот же API, что использует исследователь. По общему признанию, он не переносится.

В C ++:

 bool NaturalLess(const wstring &lhs, const wstring &rhs) { return StrCmpLogicalW(lhs.c_str(), rhs.c_str()) < 0; } vector strings; // ... load the strings sort(strings.begin(), strings.end(), &NaturalLess); 

Просто ссылка на хорошую работу в Common Lisp от Эрика Норманда:

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

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

 #include  #include  /* 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); 

В C ++ я использую этот пример кода для естественной сортировки. Для этого кода требуется библиотека ускорения.

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

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

Для Ada 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; 

Python, используя itertools:

 def natural_key(s): return tuple( int(''.join(chars)) if isdigit else ''.join(chars) for isdigit, chars in itertools.groupby(s, str.isdigit) ) 

Результат:

 >>> natural_key('abc-123foo456.xyz') ('abc-', 123, 'foo', 456, '.xyz') 

Сортировка:

 >>> sorted(['1.1.1', '1.10.4', '1.5.0', '42.1.0', '9', 'banana'], key=natural_key) ['1.1.1', '1.5.0', '1.10.4', '9', '42.1.0', 'banana'] 

Моя реализация на Clojure 1.1:

 (ns alphanumeric-sort (:import [java.util.regex Pattern])) (defn comp-alpha-numerical "Compare two strings alphanumerically." [ab] (let [regex (Pattern/compile "[\\d]+|[a-zA-Z]+") sa (re-seq regex a) sb (re-seq regex b)] (loop [seqa sa seqb sb] (let [counta (count seqa) countb (count seqb)] (if-not (not-any? zero? [counta countb]) (- counta countb) (let [c (first seqa) d (first seqb) c1 (read-string c) d1 (read-string d)] (if (every? integer? [c1 d1]) (def result (compare c1 d1)) (def result (compare cd))) (if-not (= 0 result) result (recur (rest seqa) (rest seqb))))))))) (sort comp-alpha-numerical ["a1" "a003" "b2" "a10" "a2" "1" "10" "20" "2" "c100"]) 

Результат:

(“1” “2” “10” “20” “a1” “a2” “a003” “a10” “b2” “c100”)

Для Tcl параметр -dict (dictionary) для lsort:

 % lsort -dict {ab 1 c 2 d 13} 1 2 13 abcd 

php имеет простую функцию «natsort», чтобы сделать это, и я реализую ее самостоятельно:

 ='0'&&$a<='9' ; } function my_nat_func($a,$b){ if(preg_match('/[0-9]/',$a)){ if(preg_match('/[0-9]/',$b)){ $i=0; while(!is_alpha($a[$i])) ++$i; $m = intval(substr($a,$i)); $i=0; while(!is_alpha($b[$i])) ++$i; $n = intval(substr($b,$i)); return $m>$n?1:($m==$n?0:-1); } return 1; }else{ if(preg_match('/[0-9]/',$b)){ return -1; } return $a>$b?1:($a==$b?0:-1); } }