带有可自定义交换的快速排序算法

• 下载源代码文件 - 1 KB

引言

我最近需要根据特定列的数据值来排序矩阵中的行。 这些数据不是来自数据库，所以一个漂亮的 "order by" SQL 子句无法使用。 我也没有使用 DataTable 及其相关的 DataView 类，所以 Sort 属性也不是一个选项 - 我使用的是我自己的 Matrix 类。 我的第一个想法是，这很简单，当我调用列 ArrayList 的 Sort 方法时，我只需指定我自己的 IComparer，并查找允许我交换项目的接口。 它可能被称为 ISwap!

不是! 没有 ISwap 或类似的接口。 没有办法覆盖数组中元素的交换！ 更糟糕的是，当我开始手动挖掘时，甚至没有提供像好的 'ol qsort 这样的排序算法！

后退两步，前进一步

首先要做的是找到一个快速排序算法。 我偶然发现了两个，但其中一个只能在 Google 上缓存找到。 另一个来自 MSDN 学术联盟： http://www.msdnaa.net/Resources/Display.aspx?ResID=952. (不，我没有在 Code Project 上找到 C# 实现)。 这个算法的缺点是它围绕比较一个 string 数组构建的，不支持外部比较器，当然也不支持外部交换器。

ISwap 接口

所以，首先我创建了 ISwap 接口

// my own interface, allowing control over the swap process
public interface ISwap
{
  void Swap(ArrayList array, int left, int right);
}

快速排序的实现

然后，我大量修改了上面链接中的代码，使其与对象而不是字符串一起使用，并允许应用程序指定一个 IComparer。 为了便于使用，提供了一个内置的基于 string 的比较器和内置的交换器。 static 构造函数允许各种用法语法

// The basic constructor does a quicksort using the built in comparer 
// and swapper
public static void QuickSort(ArrayList array)
{
  Sort s=new Sort();
  Sort.comparer=s;
  Sort.swapper=s;
  QuickSort(array, 0, array.Count-1);
}

// Specifies my own swapper, but the default comparer
public static void QuickSort(ArrayList array, ISwap swapper)
{
  Sort.comparer=new Sort();
  Sort.swapper=swapper;
  QuickSort(array, 0, array.Count-1);
}

// Specifies my own comparer, but the default swapper
public static void QuickSort(ArrayList array, IComparer comparer)
{
  Sort.comparer=comparer;
  Sort.swapper=new Sort();
  QuickSort(array, 0, array.Count-1);
}

// Specifies both my comparer and my swapper
public static void QuickSort(ArrayList array, IComparer comparer, 
                             ISwap swapper)
{
  Sort.comparer=comparer;
  Sort.swapper=swapper;
  QuickSort(array, 0, array.Count-1);
}

该实现是基本的 quicksort，您可以在 这里 阅读更多相关信息（您可以在互联网上找到的众多描述之一）。 代码中唯一显著的部分是调用比较器和交换器的地方，它位于 Pivot 方法中

private static int Pivot(ArrayList array, int lower, int upper)
{
  // Pivot with first element
  int left=lower+1;
  object pivot=array[lower];
  int right=upper;

  // Partition array elements
  while (left <= right)
  {
    // Find item out of place
    while ( (left <= right) && (comparer.Compare(array[left], pivot) <= 0) )
    {
      ++left;
    }

    while ( (left <= right) && (comparer.Compare(array[right], pivot) > 0) )
    {
      --right;
    }

    // Swap values if necessary
    if (left < right)
    {
      swapper.Swap(array, left, right);
      ++left;
      --right;
    }
  }

  // Move pivot element
  swapper.Swap(array, lower, right);
  return right;
}

用法

使用该算法非常简单。 例如，在我的 Matrix 类中，它管理一个列的集合，其中每个列元素都是一个行的集合，我提供了一个根据列中的数值排序行的方法

// sort the cells in the specified column in numeric order.
// if the cell in the column needs to be moved, then all other cells in the 
// other columns need to be moved also
public void SortNumeric(int col)
{
    // sort the rows in the specified column
    Sort.QuickSort(((ColumnList)columnList[col]).Rows, 
                   new NumericComparer(), this);
}

一个 sealed 类实现了数值比较器

sealed class NumericComparer: IComparer
{
  public int Compare(object x, object y)
  {
    return Convert.ToInt32(((Cell)x).Val) - Convert.ToInt32(((Cell)y).Val);
  }
}

并且矩阵实现了 ISwap 方法

public void Swap(ArrayList array, int left, int right)
{
  foreach (ColumnList col in columnList)
  {
    string obj=col[right];
    col[right]=col[left];
    col[left]=obj;
  }
}

此方法忽略传递给该方法的数组，因为它实际上需要交换两行中的所有元素。 （是的，细心的观察者会注意到我的矩阵类管理 string。 我可能很快应该对此做些什么！）

结论

我认为最有趣的是这段旅程本身。 我可以理解，出于性能原因，排序算法通常不希望在自身之外定义交换函数，但这并没有完全说服我，因为当然可以为特定需求定义比较函数。 我还对 C# 中快速排序示例的匮乏感到惊讶，并且没有人之前做过这件事。 当然，完成我想要做的事情就像后退两步，前进一步！ 好吧，这里可能就是您正在寻找的解决方案！

历史

• 2004 年 1 月 20 日：初始版本

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。