0

我正在将书籍介绍中的 QuickSort 算法应用到我编写代码的算法中，但输出未正确排序

以下是算法

Quicksort(A, p, r)
{ 
  if (p < r)
  {
    q = Partition(A, p, r)
    Quicksort(A, p, q-1)
    Quicksort(A, q+1, r)
  }
}

Partition(A, p, r)
{
  pivot = A[r]
  i = p - 1
  for j = p to r – 1
  {
    do if A[j] <= pivot
      then
      {
        i = i + 1
        exchange A[i]  A[j]
      }
  }
  exchange A[i+1]  A[r] 
  return i+1
}

这是我的代码

 class Threads<T>
 {
    static bool IsLessThan(T x, T y) 
    {
        if (((IComparable)(x)).CompareTo(y)<=0)
        {
            return true;
        }
        else {
            return false;
        }
    }
    public int Partition(T[] myarray, int low, int high)
    {

        T x = myarray[high];
        T y;
        int i = low - 1;
        int j;
        for (j = low; j < high - 1; j++)
        {
            //**************Added Text after edit,I forgot to put this  

          if (IsLessThan(myarray[j], x))
            {
                i++;
                y = myarray[i];
                myarray[i] = myarray[j];
                myarray[j] = y;                

            }
        }

        y = myarray[i+1];
        myarray[i+1] = myarray[high];
        myarray[high] = y;
        return i + 1;
    }

    public void QuickSort(T[] myarray, int low, int high)
    {
        if (low < high)
        {
         // int q = Partition(myarray,highh, low);
            int q = Partition(myarray,low, high);
            QuickSort(myarray, low, q - 1);
            QuickSort(myarray, q + 1, high );
        }
    }
}

以下代码显示了如何使用快速排序方法

    private void button1_Click(object sender, EventArgs e)
    {
        int[] myarray ={9,8,7,6,5,4,3,2};
        textBox1.Text = "";
        Threads<int> t1 = new Threads<int>();
        t1.QuickSort(myarray, 0, myarray.Length-1);
        for(int i=0;i<myarray.Length;i++)
        textBox1.Text=textBox1.Text+" , "+myarray[i];
    }

执行程序时得到以下输出

8 , 7 , 6 , 5 , 4 , 3 , 9 , 2

回答

  1. i 的值必须比 j 小 1 并且在 Partition 函数开始时为低

  2. 我忘记在分区函数的循环之外交换 myarray[i+1] 和 myarray[high]。

现在代码对于字符串、int、char 等都可以正常工作

4

3 回答 3

1

尝试这个：

公共 int 分区（T []myarray，int 低，int 高）{

    T x = myarray[high];
    int i=low;
    int j=high;

    while(i< j)
    {
       while(i<j&& IsLessThan(myarray[i], x))
           i++;
           myarray[j]=myarray[i];
       while(i<j&& IsLessThan(x,myarray[j]))
           j--;
           myarray[i]=myarray[j];

    }

        myarray[i] = myarray[high];

        return i ;
}
于 2013-06-20T03:25:34.003 回答
1

首先这部分看起来完全错误，但即使在改变排序后也不起作用

    int q = Partition(myarray, high, low);

低和高应该改变

    int q = Partition(myarray, low, high);

我认为这个问题与算法无关，而与调试方法有关。所以我使用了我在网上找到的快速排序算法，并尝试在 C# 中实现它。我有自己的问题，但调试得相当快。下面的代码有一些有用的技术来帮助调试。（算法来自http://rosettacode.org/wiki/Sorting_algorithms/Quicksort。）

以下是我在比较您的代码时的一般评论：

  1. 在处理整数索引时，要测试一个整数数组也很令人困惑，所以我将数组更改为字符串。
  2. 我使用了很多 Console.WriteLine，所以我可以跟踪算法所采取的步骤。这就是快速帮助我找到低/高问题的原因。
  3. 我没有使用名为i的变量，而是使用 for 循环索引。这只是令人困惑，因为将它用作其他任何东西 - 不要那样做！
  4. 由于每个 QuickSort 算法都有多个交换，我创建了一个交换函数。即使您只在代码中执行一次，它也会混淆 Partition 方法的目的，以便在其中包含这样一个琐碎的模式。换句话说，为什么让 IsLessThan 成为一种方法而不是 Swap 对您来说有意义？
  5. 说到 IsLessThan，从技术上讲，您实际上为 IsLessThanOrEqual 编写了一个方法。不要错误地命名事物，因为如果有人使用它并假设它只是为了 Less Then，当他们有不可预测的结果时，他们将很难过。大多数人都可以理解 IsLSE。
  6. 您的 for 循环是您使用变量j的唯一地方，那么为什么要在 for 语句之外声明它呢？只需在不需要的范围内添加额外的行和变量即可。

这是我的快速排序。它似乎工作：

public partial class MainWindow : Window
{
    public MainWindow()
    {
        InitializeComponent();
        string[] myarray = { "g", "b", "e", "f", "a", "d", "c"};

        QuickSort<string> t1 = new QuickSort<string>();
        t1.Sort(myarray, 0, myarray.Length - 1);
    }
}

public class QuickSort<T>
{
    static int Compare (T x, T y)
    {
        return ((IComparable)(x)).CompareTo(y);
    }

    private void Swap(T[] myarray, int i, int j)
    {
        // swapping indices just for writeline purposes
        if (i > j)
        {
            int t = i;
            i = j;
            j = t;
        }
        Console.WriteLine("Swap: {0}:{1} with {2}:{3}",
            i, myarray[i], j, myarray[j]);

        T temp = myarray[i];
        myarray[i] = myarray[j];
        myarray[j] = temp;


        Console.WriteLine("Result: {0}", String.Join(",", myarray));
    }

    private int Partition(T[] myarray, int low, int high, int pivotIndex)
    {
        T pivotVal = myarray[pivotIndex];
        Swap(myarray, pivotIndex, high);
        int currentLow = low;

        while (low <= high) {
            while (Compare(myarray[low], pivotVal) < 0) {
                low++;
            }
            while (Compare(myarray[high], pivotVal) > 0) {
                high--;
            }
            if (low <= high) {
                Swap(myarray, low, high);
                low++;
                high--;
            }
        }

        return low;
    }

    public void Sort(T[] myarray, int low, int high)
    {
        if (low < high)
        {
            Console.WriteLine(("Start: {0}", String.Join(",", myarray));
            int pivotIndex = (low + high) / 2;
            Console.WriteLine("QuickSort: P: {0}, L: {1}, H: {2}", 
                pivotIndex, low, high);
            pivotIndex = Partition(myarray, low, high, pivotIndex);
            Sort(myarray, low, pivotIndex - 1);
            Sort(myarray, pivotIndex + 1, high);
        }
    }
}
于 2013-06-20T02:44:00.263 回答
1

尝试一些更改并调试我尝试遵循的代码

private static int Partition(int[] input, int left, int right) 
{     
int pivot = input[right];     
int temp;       
int i = left;     
for (int j = left; j < right; j++)     
{         
if (input[j] <= pivot)
{             
temp = input[j];
input[j] = input[i];
input[i] = temp;
i++;
}
}
input[right] = input[i];
input[i] = pivot;
return i;
}

如果 Pivot 元素是中间元素

private static List<int> QuickSort(List<int> a, int left, int right)
{
int i = left;
int j = right;
double pivotValue = ((left + right) / 2);
int x = a[Convert.ToInt32(pivotValue)];
int w = 0;
while (i <= j)
{
    while (a[i] < x)
    {
        i++;
    }
    while (x < a[j])
    {
        j--;
    }
    if (i <= j)
    {
        w = a[i];
        a[i++] = a[j];
        a[j--] = w;
    }
}
if (left < j)
{
    QuickSort(a, left, j);
}
if (i < right)
{
    QuickSort(a, i, right);
}
return a;
}
于 2013-06-20T04:03:15.167 回答