ArrayList 排序教程

• 下载演示项目 - 17.6 Kb
• 下载源代码 - 20.2 Kb

目录

• 引言
• 一些理论
• IComparable 与 IComparer
• 简单类型的标准排序
• 使用 IComparable 进行标准排序
• 使用 IComparer 进行复杂排序
  • 包含混合字符串和数字内容的行
  • 需要根据不同方面动态排序的行
• 国际字符串的排序
  • 标准排序
  • 二级算法排序
• 备注
• 历史

引言

在处理一个用于显示和比较源代码的项目时，我需要对 ArrayList 中的对象进行排序。因为我以前从未做过，所以对这方面几乎一无所知。因此，我搜索了 Google，得到了数百个结果。

我在 The Code Project 上找到的两篇好文章

• 接口第二部分——实现 IComparable 和 IComparer
• 排序存储在 ArrayList 中的自定义类型元素

但是，我读过的所有文章都没有包含我所需的所有信息。因此，我花了好几个小时查阅了许多查询结果，并进行了一些测试，直到我觉得自己了解得足够多了。

然后，我决定在这里写一篇总结，以帮助其他新手理解排序问题。您应该下载演示程序，以便能够看到此处描述的操作结果。

一些理论

要对项目进行排序，您可以使用任何您想要的条件。除了“通常”的条件（如大小、高度、重量等）之外，还可以是亮度、甜度、年龄等。排序算法的内部规则是 Bill G. 的秘密。您只需要比较两个项目。您的决定取决于 Compare 方法的整数结果。

• 如果您选择项目 #2，结果为正
• 如果项目相等，结果为 0
• 如果您选择项目 #1，结果为负

负结果不一定就是 -1。这提供了一种简单的方法，只需返回两个数字的差值即可比较它们。

IComparable 与 IComparer

在浏览 Google 结果时，您会找到 IComparable 接口。在接下来的文章中，您将看到 IComparer。

印刷错误？

不！这两个接口都可以用于对简单类型进行排序，也可以用于进行非常复杂的多步排序。区别在于

	IComparer	IComparable
实现方式	在 ArrayList 的子类中或单独的类中	要排序的项目
由...实现	IComparer 类 <comparername> 方法 "Compare(Object x, Object y)"	方法 "CompareTo (object x)"
由...执行	ArrayList.Sort(<comparername>)	ArrayList.Sort()
发生	多个可能	仅一个
国际字符串	可能	可能

实际上，通过使用这两个接口中的任何一个，都可以达到几乎所有的结果。

实际测试

现在让我们对一些 ArrayList 进行排序。最左边的 ListBox 是通过单击左边或中间的某个 Button 生成的。Click 事件会将所有 lstOrig ListBox 项复制到一个标准的 ArrayList，sArl，然后对 sArl 调用 sArl.Sort()，并将 sArl 的内容写入 lstStandard Listbox。

Private Sub standardSort()
  Dim sArl As New ArrayList
  lblType.Text = lstOrig.Items.Item(0).GetType().ToString()
  ' puts all lstOrig items into the ArrayList sArl 
  origToArray(sArl)
  Try
    sArl.Sort()
    ' puts the sorted items into the middle Listbox
    arrayToListBox(sArl, lstStandard)
  Catch ex As Exception
    MsgBox(ex.Message)
  End Try
End Sub

简单类型的标准排序

可以看到，前三个简单类型 Int32、String 和 DateTime 在没有编写任何排序算法的情况下就能正确排序。但是当尝试 Color 类型时，会抛出异常。所以对于这种类型，我们需要做一些编码。

使用 IComparable 进行标准排序

我们创建一个类 MyColor。由于结构 System.Color 是 sealed（密封的），我们不能直接从 System.Color 派生，必须定义一个字段 m_color。类 MyColor 实现 IComparable 接口。

要编写实现，我们需要定义一个比较方法，int IComparable.CompareTo(object x)。

在此方法中，类实例需要将“传入”的对象 x 与自身进行比较。

  public class MyColor : IComparable
  {
    private Color m_color;

    #region Constructor
    public MyColor(Color myColor)
    {
      m_color = myColor;
    }
    #endregion

    #region Overrides
    /// 
    /// base.ToString() returns "MyColor".
    /// So we return m_color.ToString()
    /// 
    public override string ToString()
    {
      return m_color.ToString();
    }
    #endregion

    #region Standard Comparer
    /// 
    /// MyColor Standard Compare method: compare names
    /// 
    int IComparable.CompareTo(object x)
    {
      MyColor myX = (MyColor)x;
      return string.Compare(this.m_color.Name, myX.m_color.Name);
    }
    #endregion
  }

通过单击 MyColor 按钮，可以对这个简单的用户自定义类进行排序。只需为简单的用户自定义类定义一个方法 int IComparable.CompareTo(object x)。

使用 IComparer 进行复杂排序

这里的复杂性 **不是** 使用 IComparer 接口的原因。使用 IComparable 也可以达到同样的效果。此处选择它只是为了演示如何使用这种技术。

通常，有两种方法可以使用带有 IComparer 比较器的 ArrayList。

• 将比较器定义为外部类，并调用重载的 Sort 方法：<standardArrayList>.Sort(<myComparer>)。
• 将比较器定义为派生 ArrayList 的内部类，并覆盖 Sort() 方法以使用内部比较器。

我更喜欢第二种方法，因为它更透明。用户不一定需要知道使用了哪个比较器。

包含混合字符串和数字内容的行

如果单击 Ifline 按钮，您将看到示例图片中显示的输出。如果您将这些行视为字符串，它们会正确排序。但如果您将它们视为语句，那么逻辑顺序就是错误的。所以我们需要为 If-Lines 定义一个特殊的排序算法。

首先，我们创建一个类 IfLine，以及一个从 ArrayList 派生的类 IfLineList，其中包含 IfLine 对象。

为了排序，我们需要将 IfLine 字符串分成三个部分

• 前导 string 部分，StartPart
• int 部分，NumVal
• 尾随 string 部分，EndPart

利用这些部分，我们定义了一个三步比较算法。

private class IfLineSort : IComparer
{
  /// <summary>
  /// IfLineSort Compare method
  /// </summary>
  int IComparer.Compare(object x, object y)
  {
    IfLine src = new IfLine(x.ToString());
    IfLine trg = new IfLine(y.ToString());
    int result;
    // first alpha sort by StartPart
    result = string.Compare(src.StartPart, trg.StartPart);
    if (result != 0)
      return result; // different, compare done
    // if result is 0, StartParts are identical.
    // then numerical sort by NumVal
    result = src.NumVal - trg.NumVal;
    if (result != 0)
      return result;// different, compare done
    // if result is 0, NumVals are identical, too.
    // then do final alpha sort by EndParts
    result = string.Compare(src.EndPart, trg.EndPart);
    return result;
  }
}

最后，在 IfLineList 类中，我们必须覆盖 Sort() 方法以使用我们的 IComparer，IfLineSort。

/// <summary>
/// IfLineList class standard sort
/// </summary> 
public override void Sort()
{
  base.Sort(new IfLineSort());
}

需要根据不同方面动态排序的行

想象一下您有一些变量定义。在您的应用程序中，您希望动态地选择按名称、类型和访问级别进行排序，或它们的组合。（为了举例，我们只限制在这三个项目上，没有更多属性。）

一个定义行看起来像：“private int myValue;”。我们创建一个类 VarLine 来表示这样一个定义行，以及一个从 ArrayList 派生的类 VarLineList，其中包含 VarLine 对象。变量类型和访问级别由 enum（枚举）描述。对于示例，enum 也被限制了。

  public enum EType
  {
    // order is my personal choice
    typInt = 1,
    typString,
    typBool
  }
  public enum EAccess
    // order is 'by publicity'
  {
    accessPublic = 1,
    accessInternal,
    accessPrivate
  }

为了告知应用程序排序方法和顺序，我们定义

• T 表示类型升序排序
• t 表示类型降序排序
• A 表示访问级别降序排序
• a 表示访问级别降序排序
• N 表示名称降序排序
• n 表示名称降序排序

任何组合，如“TAN”或“aTn”，都是可能的。由于名称是唯一的，因此在“N”或“n”之后添加排序步骤没有意义。

“组合字符串”被提供给 VarLineList 的 SortAlgoritm 属性，该属性在构造函数中将其传递给内部的 IComparer，VarLineSort。

/// <summary>
/// CustVarLineSort Compare method
/// compare step by step, algorithm is stored as symbolic string in m_Algo
/// </summary>
int IComparer.Compare( object x, object y )
{
  VarLine src = new VarLine(x.ToString());
  VarLine trg = new VarLine(y.ToString());
  int result = 0;
  int i;
  string step;
  string stepU;
  for (i=0;i<m_Algo.Length;i++)
  {
    step = m_Algo.Substring(i,1);
    stepU = step.ToUpper();
    switch (stepU)     {
      case "A":
        result = src.VarAccess - trg.VarAccess;
        break;
      case "T":
        result = src.VarType - trg.VarType;
        break;
      case "N":
        result = string.Compare(src.VarName, trg.VarName);
        break;
    }
    if (result != 0)
    {
      if (!step.Equals(stepU))
        // descending sort
        return -result;
      else
        return result;
    }
  }
  // if we come here the objects are equivalent
  return 0;
}

国际字符串的排序

前言：以下文本适用于源自拉丁字母的字符集。我不知道它是否适用于阿拉伯语、东亚语、希腊语、西里尔语等字符集。

对包含外文字符的字符串进行排序相对容易：在 IComparer 或 IComparable 中，使用 string.Compare 方法，并使用带有额外参数“bool ignoreCase”（忽略大小写）和“System.Globalization.CultureInfo culture”（区域性）的重载版本。

/// <summary>
/// StringList Compare method
/// </summary>
int IComparer.Compare(object x, object y)
{
  string src = x.ToString();
  string trg = y.ToString();
  int result = string.Compare(src, trg, m_ignoreCase, m_Culture);
  return result;
}

在这里，您可以定义要排序字符串的语言（通过定义一个 'Culture'）。您有两种选择：

• 带有区域性名称的字符串，如“en-US”
• 带有区域性标识符的数字，如“0x0409”

所有标识符的完整列表可以在 MSDN 上找到。

标准排序

如果您尝试“Intl. Text 1”，您通常（取决于您的语言）不会看到“invariant”、“local PC”和“en-US”之间的任何区别。只有“da-DK”才会带来差异。原因是，在大多数语言中，特殊字符会按与其相关联的字符的邻近位置排序。然而，在丹麦语中，这些字符被排序为符号，即排在标准字符之后。

结论：

在大多数情况下，使用 CultureInfo 对字符串进行排序不是必需的。当然，使用它也不会有坏处。

二级算法排序

有些语言有两种不同的官方排序算法。

例如：德语有两种

• 字典排序
• 电话簿排序

区别在于如何处理变音符号（即带两个点的 a、u、o，看起来像 ä Ä ö Ö ü Ü）。

在字典排序（这是标准排序）中，变音符号排在相应元音字母之后。

T, U, Ü, V ...

在电话簿排序中，变音符号被替换为相应的元音字母加上一个“e”。

Ua, Ub, Uc, Ud, Ue, Ü, Uf ...

要执行二级排序算法，您必须定义一个特殊的区域性标识符（不幸的是，没有特殊的区域性名称）。对于德语，它是 0x10407，而不是标准的 0x0407。

现在尝试“Intl. Text 2”并查看结果。

这里是所有二级算法的完整列表：MSDN。

备注

在 .NET 框架中，存在一个名为 'CaseInsensitiveComparer' 的类，我故意没有使用或提及它。在我看来，string.Compare 方法提供了所需的所有功能。

历史

• 2006 年 6 月 17 日 - 发布第一个版本。