logo标签列表

自然排序算法

algorithmlanguage-agnosticsortingnatural-sort
23

如何在不同的编程语言中对字符串数组进行自然排序？请在回答中发布您的实现和所使用的编程语言。

1
实际上，有趣的部分是比较函数，它可以用于任何你喜欢的排序算法。 - Svante
2
阅读该博客文章的评论，似乎自然排序方式定义不够明确。 - David Thornley
15个回答
7
这是如何在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 https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/"""
    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()。
在某些环境中，例如Python 2中的cp1252区域设置下的Windows系统上，.isdigit()也可能失败（返回一个int()不接受的值），比如字节串中的'\xb2' ('²')。
如果有人找到了这篇2008年的帖子而不是较新的两个Python帖子，我想添加一个警告：'int'适用于许多有用的情况（例如，image3.jpg和image10.jpg），但对于['elm1'，'Elm2']和['0.501'，'0.55']和[0.01,0.1,1]等情况则失败...请参见https://dev59.com/aG445IYBdhLWcg3we6V9#27430141，以了解lower()和我更一般的Python自然排序解决方案。 - Scott Lawton
@ScottLawton：将您的解决方案与StrCmpLogicalW函数进行比较。请阅读问题中链接的博客文章。 - jfs
5

这是对问题链接中文章中的代码进行的清理：

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

但实际上我还没有机会以这种方式对任何东西进行排序。

只是想提醒一下，我在另一个答案中使用了你的代码：https://dev59.com/6UzSa4cB1Zd3GeqPmmwo#22685365。目标软件将在GitHub上公开，并注明出处。如果这有问题，请回复我。 - Nuno Furtado
没问题。请注意，当您查看目录并尝试创建文件之间，可能会有其他进程创建该文件的情况发生。 - Darius Bacon
你说得没错，但不确定如何解决那个竞态条件。当你确定在那个位置是唯一写入该模式的人时，这也不是一个问题。 - Nuno Furtado
我在那里添加了一个建议，尽管我手头没有详细信息。 - Darius Bacon
5

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

Source

这段代码的第三行与其来源不同。第三行应替换为：this[z] = []; var x = 0，y = -1，n = 0，i，j; - Bryce Thomas
5
对于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。
3

如果OP问的是关于惯用排序表达式的问题，那么并非所有语言都内置了自然表达式。对于C语言，我会去使用<stdlib.h>中的qsort。类似于：

/* non-functional mess deleted */

将参数按词法顺序排序。不幸的是，对于那些不习惯c语言的人来说，这个习惯用语很难解析。

受到负评的惩罚，我实际上读了链接的文章。我的错。

无论如何，原始代码并没有起作用，除了我测试过的单个案例。该函数不在普通的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;
}

这种方法相当暴力，但它很简单，可能可以在任何命令式语言中复制。
2
在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);
2
我刚刚使用了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);
2
2

在C++中，我使用这个示例代码来进行自然排序。该代码需要使用boost库。

1

我在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")

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接