22

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

4

14 回答 14

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 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 上的字节串也可能会失败（返回值不被 接受），例如Windows 上 cp1252 语言环境中的 '\xb2' ('²')。

于 2008-12-04T19:24:41.293 回答
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("");
}

资源

于 2008-08-29T16:01:29.880 回答
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

于 2008-08-29T16:03:47.940 回答
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)]

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

于 2008-12-04T19:18:53.333 回答
3

If the OP is asking about idomatic sorting expressions, then not all languages have a natural expression built in. For c I'd go to <stdlib.h> and use qsort. Something on the lines of :

/* non-functional mess deleted */

to sort the arguments into lexical order. Unfortunately this idiom is rather hard to parse for those not used the ways of c.

Suitably chastened by the downvote, I actually read the linked article. Mea culpa.

In anycase the original code did not work, except in the single case I tested. Damn. Plain vanilla c does not have this function, nor is it in any of the usual libraries.

The code below sorts the command line arguments in the natural way as linked. Caveat emptor as it is only lightly tested.

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

This approach is pretty brute force, but it is simple and can probably be duplicated in any imperative language.

于 2008-08-29T17:16:45.690 回答
2

只是 Eric Normand 在 Common Lisp 中一些不错的工作的链接：

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

于 2008-12-07T20:35:48.727 回答
2

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

于 2008-08-30T14:02:52.073 回答
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);
于 2009-08-27T22:23:43.410 回答
2

我只是使用StrCmpLogicalW。它完全符合 Jeff 的要求，因为它与 explorer 使用的 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);
于 2008-12-04T18:19:37.540 回答
1

请注意，对于大多数此类问题，您只需查阅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;
于 2009-04-15T21:10:53.840 回答
1

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']
于 2010-10-22T21:22:00.393 回答
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”）

于 2011-08-03T09:45:21.600 回答
0

对于 Tcl，lsort 的 -dict（字典）选项：

% lsort -dict {a b 1 c 2 d 13}
1 2 13 a b c d
于 2009-04-15T20:26:41.030 回答
0

php 有一个简单的函数“natsort”可以做到这一点，我自己实现了它：

<?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);
    }
}
于 2014-10-21T03:55:45.410 回答