1

作为一项学校作业，我应该使用至少 2 个线程来执行多线程快速排序算法，但我的代码存在一些我似乎无法修复的问题。

编辑：这就是它不是多线程时的样子。我已经确认这有效。

public class Sorter
{
    private int[] mInts;

    public void QuickSort()
    {
        QuickSort(mInts, 0, mInts.Length - 1);
    }

    public Sorter(int[] ints)
    {
        mInts = ints;
    }

    private int Partition(int[] ints, int left, int right)
    {
        int pivotIndex = (right + left) / 2;
        int pivotValue = ints[pivotIndex];

        Swap(ints, right, pivotIndex);

        int storeIndex = left;

        for (int i = left; i <= right - 1; i++)
        {
            if (ints[i] < pivotValue)
            {
                Swap(ints, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(ints, storeIndex, right);

        return storeIndex;
    }

    private void Swap(int[] ints, int x, int y)
    {
        int temp = ints[x];
        ints[x] = ints[y];
        ints[y] = temp;
    }

    private void QuickSort(int[] ints, int left, int right)
    {
        if (left < right)
        {
            int newIndex = Partition(ints, left, right);


             QuickSort(ints, left, newIndex - 1);
             QuickSort(ints, newIndex + 1, right);
        }
    }

上面的工作正常，下面的代码没有。现在它没有正确排序，在我看来，加粗的代码段必须位于其他地方......还是什么？我很难理解线程编程，所以我希望有人能给我一些关于如何解决这个问题的指导，如果可能的话，不必重组我的整个程序。以下是我在线程版本方面取得的进展。

public class Sorter
{
    private int[] mInts;

    Thread myThread = null;
    int numThreads = 0;
    int maxThreads = 10;

    public void QuickSort()
    {
        QuickSort(mInts, 0, mInts.Length - 1);
    }

    public Sorter(int[] ints)
    {
        mInts = ints;
    }

    private int Partition(int[] ints, int left, int right)
    {
        int pivotIndex = (right + left) / 2;
        int pivotValue = ints[pivotIndex];

        Swap(ints, right, pivotIndex);

        int storeIndex = left;

        for (int i = left; i <= right - 1; i++)
        {
            if (ints[i] < pivotValue)
            {
                Swap(ints, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(ints, storeIndex, right);

        return storeIndex;
    }

    private void Swap(int[] ints, int x, int y)
    {
        int temp = ints[x];
        ints[x] = ints[y];
        ints[y] = temp;
    }

    private void QuickSort(int[] ints, int left, int right)
    {
        if (left < right)
        {
            int newIndex = Partition(ints, left, right);

            if (numThreads < maxThreads)
            {
                numThreads++;
                myThread = new Thread(new ParameterizedThreadStart(startSort));
                myThread.Start(new SortParameters(this, ints, left, newIndex - 1));
                **QuickSort(ints, newIndex + 1, right);**
            }
        }
    }

    static void startSort(Object obj)
    {
        SortParameters sortParams = (SortParameters)obj;
        sortParams.instance.QuickSort(sortParams.ints, sortParams.left, sortParams.right);
    }

    public class SortParameters
    {
        public Sorter instance;
        public int[] ints;
        public int left;
        public int right;

        public SortParameters(Sorter instance, int[] ints, int left, int right)
        {
            this.instance = instance;
            this.ints = ints;
            this.left = left;
            this.right = right;
        }
    }
}

谢谢你的帮助！

4

1 回答 1

0

问自己以下问题：

  1. 一个元素序列将运行多少个线程n？
  2. 该数字是否受到您的代码的某种限制？
  3. 当达到这个限制时会发生什么？

我在下面提供了我的解决方案，但您可能想先自己考虑一下。

以下是我的回答：

  1. 从理论上讲，您的代码将计算 log 2 (n) 个快速排序，因为它在分区后将每个排序划分为 2 个子调用。在您的线程版本中，您为每个子调用启动一个补充线程，因此您总共可以启动尽可能多的线程。

  2. 您提供的代码实际上使用该值限制了启动线程的数量maxThreads。所以事实上，如果 log 2 ( n) > maxThreads，即。如果n> 2 maxThreads，代码将达到可能的最大并发线程数。

  3. 在线程代码中，围绕突出显示的部分，对该最大值的测试决定了任何递归调用的执行。因此，如果n高于第 2 点中提到的限制，代码将停止正常工作。

修复很简单，添加一个else子句来完成当前线程的排序。

        if (numThreads < maxThreads)
        {
            numThreads++;
            myThread = new Thread(new ParameterizedThreadStart(startSort));
            myThread.Start(new SortParameters(this, ints, left, newIndex - 1));
        }
        else {
            QuickSort(ints,left,newIndex - 1);
        }
        QuickSort(ints, newIndex + 1, right);

正如你所看到的，我也从测试中移出了将由当前线程运行的部分。

于 2013-02-24T11:47:56.197 回答