>>"/>

关于不可知的语言:自然排序算法

关于不可知的语言:自然排序算法

Natural Sorting algorithm

您如何自然地以不同的编程语言对字符串数组进行排序? 发布您的实现及其答案中使用的语言。


这是在Python中如何获得类似浏览器的行为的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/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()

在某些语言环境中,例如在Windows 2的cp1252语言环境中的' xb2'('2'),对于Python 2上的字节串,.isdigit()可能也会失败(返回值,int()不接受)。


这是该问题链接到的文章中的代码的清理:

1
2
3
4
5
6
7
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


的JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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("");
}

资源


如果OP询问有关idomatic排序表达式的信息,那么并非所有语言都内置了自然表达式。对于c语言,我将转到并使用qsort。在以下方面:

1
/* non-functional mess deleted */

将参数按词汇顺序排序。不幸的是,对于那些不习惯使用c方式的人来说,这种习语很难解析。

适当地受到反对者的追捧,我实际上阅读了链接的文章。 Mea culpa。

在任何情况下,原始代码均不起作用,除非在我测试过的单个情况下。该死的。普通香草c没有此功能,在任何常用库中也没有。

下面的代码以链接的自然方式对命令行参数进行排序。警告购买者,因为它只是经过轻微测试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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
",(++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;
}

这种方法是蛮力的,但它很简单,可以用任何命令式语言复制。


在C中,此解决方案正确处理带有前导零的数字:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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一起使用,请使用以下辅助功能:

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

您可以按以下顺序进行操作

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


只是Eric Normand在Common Lisp中一些出色的工作的链接:

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


我只是使用StrCmpLogicalW。它正是Jeff想要的,因为它与资源管理器使用的API相同。不可否认,它不是便携式的。

在C ++中:

1
2
3
4
5
6
7
8
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);

在C ++中,我使用此示例代码进行自然排序。该代码需要boost库。


我在Clojure 1.1上的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(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")


Python,使用itertools:

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

结果:

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

排序:

1
2
>>> 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']


请注意,对于大多数此类问题,您只需查阅Rosetta Code Wiki。我从条目中调整了我的答案以对整数进行排序。

在系统的编程语言中,执行这种操作通常比使用专门的字符串处理语言要难看。幸运的是,对于Ada而言,最新版本具有用于此类任务的库例程。

对于Ada 2005,我相信您可以按照以下方式进行操作(警告,请勿编译!):

1
2
3
4
5
6
7
8
9
10
11
12
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
  );

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
    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;

php有一个简单的函数" natsort"可以做到这一点,我自己实现了它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
<?php
$temp_files = array('+====','-==',"temp15-txt","temp10.txt",
"temp1.txt","tempe22.txt","temp2.txt");
$my_arr = $temp_files;


natsort($temp_files);
echo"Natural order:";
print_r($temp_files);


echo"My Natural order:";
usort($my_arr,'my_nat_func');
print_r($my_arr);


function is_alpha($a){
    return $a>='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);
    }
}

对于Tcl,使用ldict的-dict(字典)选项:

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


推荐阅读

    金蝶凭证排序号乱了

    金蝶凭证排序号乱了,,1.金蝶的顺序号跟凭证号不一致怎么办没关系的,可以在凭证过滤界面选择按凭证号或者凭证顺序号来排序,一般都选择凭证号

    探探语言设置|探探怎么设置语言

    探探语言设置|探探怎么设置语言,,1. 探探怎么设置语言打开探探软件,然后就有消息提示的红点,点开就行了!其实这些软件都是挺简单的操作的,都是

    git设置编码|git语言设置

    git设置编码|git语言设置,,git设置编码点击cap4j搜索从git直接链接上拉代码。git语言设置Git是一个开源的分布式版本控制系统,可以有效、高

    word图标排序快捷键|word的快捷图标

    word图标排序快捷键|word的快捷图标,,1. word的快捷图标1、大家说的都是如何打开word,而不是像建空白文件夹那样,因为没有直接新建空白word

    区域语言设置|区域语言设置工具

    区域语言设置|区域语言设置工具,,区域语言设置工具你好,大致的方法如下,可以参考:1、按下键盘的windows 图标,再开始菜单中单击“设置”;出现的

    在excel中如何排序

    在excel中如何排序,排序,如何,excel,先选定工作表要排序的数据范围,然后点击上方的“数据”选项,选中“排序”,出现如下画面选择好“主要

    c4d语言设置|c4d汉语设置

    c4d语言设置|c4d汉语设置,,1. c4d汉语设置mac版的C4D是这样的,中文字体是有的,但是是以拼音的形式存在,比如黑体就是ht。中文字体以拼音方式