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

Question

Как вы сортируете массив строк естественно в разных языках программирования? Опубликуйте свою реализацию и на каком языке она написана в ответе.

Answer 1

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

Answer 2

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

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

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

Answer 3

Для MySQL я лично использую код из модуля Drupal, который доступен по адресу h http://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

Answer 4

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

Источник

Answer 5

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

/* non-functional mess deleted */

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

---

Соответственно наказанный понижением, я фактически прочитал связанную статью. Mea culpa.

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

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

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

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

Answer 6

В 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);

Answer 7

Просто ссылка на замечательную работу Эрика Норманда в Common Lisp:

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

Answer 8

Я просто использую StrCmpLogicalW . Он делает именно то, что хочет Джефф, так как это тот же 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);

Answer 9

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

Answer 10

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

(ns alphanumeric-sort
  (:import [java.util.regex Pattern]))

(defn comp-alpha-numerical
  "Compare two strings alphanumerically."
  [a b]
  (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 c d)))
             (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")