1

我正在尝试设置快速排序，并且我希望它对分数数组进行排序。
目前，它不能正确排序具有相等值的分数（例如 1/2 和 2/4）
1/2 需要在 2/4 之前，但它最终完全随机。

我正在使用的代码是这样的： 

   public static void quicksort(Fraction[] f, int p, int r)
    {
        if (p < r)
        {
            int q = partition(f, p, r);
            quicksort(f, p, q - 1);
            quicksort(f, q + 1, r);
        }
    }

    public static int partition(Fraction[] f, int p, int r)
    {
        Fraction pivot = f[r];
        int i = p - 1;
        for (int j = p; j < r; j++)
        {
            if (f[j].Value < pivot.Value)
            {
                i++;
                Fraction wissel = f[i];
                f[i] = f[j];
                f[j] = wissel;
            }
            else
                if (f[j].Value < pivot.Value && f[j].Teller < pivot.Teller)
                {
                    i++;
                    Fraction wissel = f[i];
                    f[i] = f[j];
                    f[j] = wissel;
                }
        }
        Fraction wisselt = f[i + 1];
        f[i + 1] = f[r];
        f[r] = wisselt;
        return i + 1;

    }

谁能阐明如何做到这一点？

编辑：David Archer 的建议修复了它，谢谢你们。

4

4 回答 4

1

我认为你想要的比较是这样的：

static int CompareFractions(Fraction a, Fraction b)
{
    // compare the value of the fractions
    int c = (a.numerator * b.denominator).CompareTo(a.denominator * b.numerator);
    if (c == 0)
        // break ties with "lowest numerator first"
        c = a.numerator.CompareTo(b.numerator);
    return c;
}

您也可以将其用作普通 Sort 方法的排序委托。

于 2012-08-12T16:11:24.847 回答
1

您的问题是您正在设计快速排序以<进行比较。

您可以通过将 1/2 重新定义< 为小于 2/4 来立即解决它，但这会弄乱所有其他<用作分数的情况。

您应该以正常的 .NET 方式定义您的排序，其中您有一个采用System.Comparison委托的表单，一个采用 a 的表单System.IComparer和不使用它们的重载，由这些实现。

internal class DelegateComparer<T> : IComparer<T>
{
  private Comparison _del;
  public DelegateComparer(Comparison del)
  {
    _del = del;
  }
  public int Compare(T x, T y)
  {
    return _del(x, y);
  }
}
public static void Quicksort(Fraction[] f, int p, int r, IComparer<Fraction> cmp)
{
  /* This is the only method with the real implementation */
}
public static void Quicksort(Fraction[] f, int p, int r)
{
  QuickSort(f, p, r, Comparer<Fraction>.Default);
}
public static void Quicksort(Fraction[] f, int p, int r, Comparison<Fraction> cmp)
{
  QuickSort(f, p, r, new DelegateComparer(cmp));
}
public static void QuickSort(Fraction[] f)
{
  QuickSort(f, 0, f.Length, Comparer<Fraction>.Default);
}

完成后，对于将 1/2 放在 2/4 之前的奇怪情况，您需要做的就是执行此操作的自定义比较器。假设您的Fraction课程类似于：

public class Fraction
{
  public int Denominator{get;set;}
  public int Numerator{get;set;}
  public double Value
  {
    return (double) Numerator / (double) Denominator;
  }
}

然后，您可以快速编写一个IComparer<Fraction>或一个Comparison<Fraction>来解决问题。让我们采取第二个选项：

private static int CompareSepDenom(Fraction x, Fraction y)
{
  int cmp = x.Value.CompareTo(y.Value);//normal comparison first
  if(cmp == 0)//same value;
    return x.Numerator.CompareTo(y.Numerator);//put lower numerator (also lower denum) first
  return cmp;
}

如果这是真正的代码，而不是实验，那么我们也不会费心实现快速排序，因为Array.Sort无论如何List<T>.Sort都要使用快速排序。所以我们可以这样做：

Array.Sort(arrayOfFractions, CompareSepDenom);

或者，如果您不打算重用 CompareSepDenom，而是希望有一个来自 lambda 的匿名委托，您可以使用：

Array.Sort(arrayOfFractions, (x, y) =>
    {
      int cmp = x.Value.CompareTo(y.Value);//normal comparison first
      if(cmp == 0)//same value;
        return x.Numerator.CompareTo(y.Numerator);//put lower numerator (also lower denum) first
      return cmp;
    });

另一方面，如果您正在编写快速排序作为实验或从代码中学习，请注意，您所依赖的事实ICmparer<Fraction>意味着您不再局限于编写方法来接受<已定义的特定类型.

这意味着您可以编写一个方法：

public static void QuickSort<T>(T[] arr, int p, int r, IComparer<T> cmp)

这适用于所有类型。

完成此操作后，就该与库中内置的版本进行比较了。

编辑：

顺便说一句，以防你还没有这样做。你的Fraction类应该实现IComparable<Fraction>and IComparable（为了与 .NET1.0 向后兼容），以便不想创建自己的比较器委托或类的人可以获得分数的正常排序（其中 1/2 和 2/4是等价的）。一旦你实施了第一个：

CompareTo(Fraction other)
{
  if(other == null)//take out this of Fraction is a struct
    return 1;
  return Value.CompareTo(other.Value)
}
CompareTo(object obj)
{
  if(other == null)
    return 1;
  Fraction fract = other as Fract;
  if(fract == null)
    throw new ArgumentException("Can only compare with other factions", "obj");
  return CompareTo(fract);
}

因为Comparer<Fraction>.Default将反过来使用它，所以不采用比较器的排序方法的版本将起作用，其他依赖于以其他方式排序的代码也将起作用。真的，对于任何“正常的排序方式”有意义的类，或者你定义<的类，>等等<=，都应该有它们。您还可以通过CompareTo（在实践中最终会被内联，因此没有性能损失`）路由所有这些运算符重载，这意味着相同的代码几乎适用于任何此类。

于 2012-08-12T16:13:10.417 回答
1

我不确定您使用的是哪个 Fraction 类，但如果您需要区分 1/2 和 2/4（在严格的数学术语中是相等的），我建议您创建自己的比较方法并使用这些方法而不是内置大于和小于运算符。

bool IsLessThan(Fraction a, Fraction b)
{
    // Your code here that results in 1/2 being less than 2/4
}

bool IsGreaterThan(Fraction a, Fraction b)
{
    // Your code here that results in 2/4 being greater than 1/2
}
于 2012-08-12T15:50:56.313 回答
1

为什么不直接使用List<T>.Sort()？它是快速排序的一个实现。如果你有一个IComparable<Fraction>实现，那么你可以调用Sort(). 如果您想传递特定方法，您也可以使用接受委托的覆盖。

例如，如果你的Fraction班级是这样的：

    public class Fraction : IComparable<Fraction>
    {
     public int CompareTo(Fraction other)
     {
       // if other equals this, return 0
       // if other is greater than this, return -1
       // if other is less than this, return 1
     }
//...
    }

然后你可以有一个 List 变量并调用它的 Sort 方法：

myList.Sort();
于 2012-08-12T16:01:15.993 回答