什么是错在C＃这个快速排序算法？ [英] What is wrong with this QuickSort algorithm in C#?

问题描述

可悲的是，我有问题，快速排序为好。我已经讨论过与其他学生，并试图在标准的故障排除方法。但是我无法找到我在做什么错了......

Sadly, I've got problems with Quicksort as well. I've discussed it with other students and tried the standard troubleshooting methods. But I can't find what I'm doing wrong...

static int partition(int[] A)
    {
        int pivot, i, j;
        i = 0;
        j = A.Length;
        pivot = A[i];

        do
        {
            do
            {
                i++;
            }
            while (A[i] < pivot || i < j);
            do
            {
                j--;
            }
            while (A[j] > pivot);

            swap(ref A[i], ref A[j]);
        }
        while (i < j);

        if (i <= j)
        {
            swap(ref A[i], ref A[j]);
            swap(ref A[0], ref A[j]);
        }

        return j;
    }

    static void swap(ref int a, ref int b)
    {
        int aCopy = a;
        a = b;
        b = aCopy;
    }

    static int[] QuickSort(int[] A)
    {
        int s;
        int left = 0;
        int right = A.Length;
        int[] B, C;

        if (A.Length == 0 || A.Length == 1)
            return A;
        else
        {
            s = partition(A);
            B = new int[s];
            C = new int[right - s];

            for (int i = left; i < s; i++)
            {
                B[i - left] = A[i];
            }
            for (int i = s; i < right; i++)
            {
                C[i - s] = A[i];
            }

            QuickSort(B);
            QuickSort(C);
            return A;
        }
    }

调试器不断地给了我一个IndexOutOfRangeException与J变量。我试着调整

The debugger constantly gives me an 'IndexOutOfRangeException' with the j variable. I've tried adjusting the

while (A[i] < pivot || i < j);

部分。但是，这并没有做什么（当然，这导致StackOverflowException一次）。

part. But that didn't do anything (well, it resulted in a StackOverflowException once).

推荐答案

好了，有太多的失误，像你换回来你已经交换等方面的内容。这是你做的没有错误，也包括什么在previous答案和评论已经说的方法解决方案。尼斯编码！

Well, there are too many mistakes, like you are swapping back the elements you have already swapped and so on. This is your solution with your way of doing it without mistakes that also includes what has been said in previous answers and comments. Nice coding!

    static int partition(int[] A)
    {
        int pivot, i, j;
        i = 0;
        j = A.Length-1;
        pivot = A[0];

        while (i < j)
        {
            while (A[i] < pivot && i < j)
            {
                i++;
            }

            while (A[j] > pivot && j > i)
            {
                j--;
            }
            swap(ref A[i], ref A[j]);
        }

        return j;
    }

    static void swap(ref int a, ref int b)
    {
        int aCopy = a;
        a = b;
        b = aCopy;
    }

    static int[] QuickSort(int[] A)
    {
        int s;
        int left = 0;
        int right = A.Length;
        int[] B, C;

        if (A.Length == 0 || A.Length == 1)
            return A;
        else
        {
            s = partition(A);
            B = new int[s];
            C = new int[right - s - 1];

            for (int i = left; i < s; i++)
            {
                B[i - left] = A[i];
            }
            for (int i = s + 1; i < right; i++)
            {
                C[i - s - 1] = A[i];
            }

            B = QuickSort(B);
            C = QuickSort(C);
            for(int i = 0; i < s;i++)
                A[i] = B[i - left];
            for (int i = s + 1; i < right; i++)
            {
                A[i] = C[i - s - 1];
            }
            return A;
        }
    }

这篇关于什么是错在C＃这个快速排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！