0

我有一个创建 10 个随机整数的数组，然后使用快速排序对它们进行排序。我的问题是，当我将其更改为创建 1,000,000 个随机整数时，它不会这样做..你能帮忙吗？

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RepeatAssignmentQ2
{
class Program
{
    static public int Partition(int[] myArray, int left, int right)
    {
        int pivot = myArray[left];
        while (true)
        {
            while (myArray[left] < pivot)
                left++;

            while (myArray[right] > pivot)
                right--;

            if (left < right)
            {
                int temp = myArray[right];
                myArray[right] = myArray[left];
                myArray[left] = temp;
            }
            else
            {
                return right;
            }

        }
    }

    static public void QuickSort_Recursive(int[] arr, int left, int right)
    {
        // For Recusrion
        if (left < right)
        {
            int pivot = Partition(arr, left, right);

            if (pivot > 1)
                QuickSort_Recursive(arr, left, pivot - 1);

            if (pivot + 1 < right)
                QuickSort_Recursive(arr, pivot + 1, right);
        }
    }

    static void Main(string[] args)
    {
        Random rnd = new Random();
        DateTime startTime = DateTime.Now;

        int ind = 0;
        int length = 1000000;
        int[] myArray = new int[length];

        while (ind < 1000000)
        {
            myArray[ind] = rnd.Next(1000000);
            ind++;
        }

        int lengthTwo = 10;

        Console.WriteLine("QuickSort by recursive method");

        QuickSort_Recursive(myArray,0, lengthTwo - 1 );



        for (int i = 0; i < 1000000; i++)
        {

            Console.WriteLine(myArray[i]);

        }
        Console.WriteLine("Total Time: {0}\n", DateTime.Now - startTime);
        Console.WriteLine();



    }
}
}

谢谢

编辑 - 当我使用具有 10 个数字的数组调整程序时，它将显示它们并对其进行排序。当我将其更改为 1,000,000 并运行程序时，没有任何显示。

编辑 2 - 好吧，出于某种奇怪的原因，它正在这样做。我更改了上面的代码以显示更改，它现在显示它随机生成的数字，但它没有对它们进行排序。但是，当 IT 只需要创建 10 个随机数时，它会对其进行排序。

4

4 回答 4

2

填充和排序 1,000,000 个元素仍然应该非常快。

您的算法中有错误，在分区方法中。如果left小于right你应该增加left和减少right：

if (left < right)
{
    int temp = myArray[right];
    myArray[right] = myArray[left];
    myArray[left] = temp;
    left++;
    right--;
}

分析您的程序在myArray[left]大于或等于pivot、myArray[right]小于或等于pivot以及left小于时的行为right。你有一个无限循环while (true)，因为两个whiles 被忽略并且if不会改变leftor的值right。如果数组中有重复项，就会出现这种情况。例如，当您尝试仅使用 1,000 个数字填充 1,000,000 个元素时，就会发生这种情况。

顺便提一句。如果您将每 1000000 替换为变量length并且lengthTwo可以替换为length. 为什么？在这种情况下，当您想要检查更大数组的程序行为时。改变一个变量的值比改变五个数字更容易。

我希望我有所帮助。

于 2013-08-22T19:34:39.200 回答
0

我刚刚偶然发现了这个，错误就在这里

QuickSort_Recursive(myArray,0, lengthTwo - 1 );

将其更改为

QuickSort_Recursive(myArray,0, length - 1 );

对于您的分区，我认识到 hoare 算法（比替代算法更快）https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto这是它们的伪代码（你会看到 i =p+1 和 j=p-1 在开始，否则很好）

于 2013-12-28T20:15:30.077 回答
0

对不起，你等了多久？我怀疑填充 1 百万个整数数组的 while 循环需要很长时间，因为它调用 Next 方法 1,000,000 次。您是否看到以下输出：'QuickSort by recursive method'？

于 2013-08-22T18:41:49.530 回答
0

虽然这个回复离提问的时间很远，但是下面的内容对于任何阅读问题的人来说都是有用的。

问题中提到的代码的问题是，只要枢轴元素在两端（左和右）相似，它就会在分区函数上产生无限循环

这是修改后的代码以使其正常工作：

static int Partition(int[] myArray, int left, int right)
    {
        int pivot = myArray[left];
        while (true)
        {
            while (myArray[left] < pivot)
                left++;

            while (myArray[right] > pivot)
                right--;

            if (left < right && myArray[left] == myArray[right])
                left++;
            else if (left < right)
            {
                int temp = myArray[right];
                myArray[right] = myArray[left];
                myArray[left] = temp;
            }
            else
            {
                return right;
            }

        }
    }
于 2018-01-28T12:14:20.767 回答