سؤال

لذلك أحاول إنشاء طريقة Quicksort ، ومع ذلك ، فهي لا يتم فرزها بشكل صحيح. هيريس مدخلاتي والمخرجات
المصفوفة الأصلية:
80.0 10.0 50.0 70.0 60.0 90.0 20.0 30.0 40.0 0.0
صفيف فرز:
0.0 30.0 20.0 80.0 40.0 60.0 70.0 10.0 90.0 50.0

حاولت تغيير الحلقة إلى for(int i = left; i < right; i++)
ولكن الآن الإخراج هو:
0.0 20.0 30.0 40.0 80.0 10.0 60.0 90.0 70.0 50.0

    public static void sort(double[] a)
    {
        quickSort(a, 0, a.length-1);
    }

    public static void quickSort(double [] a, int left, int right)
    {
        if (left < right)
        {
            int pivotIndex = (left+right)/2;
            int pos = partition(a,left,right,pivotIndex);
            quickSort(a,left,pos-1);
            quickSort(a,pos+1,right);
        }
    }

    private static int partition(double [] a, int left,int right,int pivotIndex)
    {
        double temp = a[pivotIndex];
        a[pivotIndex] = a[right];
        a[right] = temp;
        int pos = left;//represents boundary between small and large elements
        for(int i = left; i < right-1; i++)
        {
            if (a[i] <= a[pivotIndex])
            {
                double temp2 = a[i];
                a[i] = a[pos];
                a[pos] = temp2;
                pos++;
            }
        }
        double temp3 = a[pivotIndex];
        a[pivotIndex] = a[pos];
        a[pos] = temp3;
        return pos;
    }
هل كانت مفيدة؟

المحلول

هذا ما تريد القيام به:

private static void swap(double[] a, int i, int j) {
    double t = a[i];
    a[i] = a[j];
    a[j] = t;
}

private static int partition(double [] a, int left,int right,int pivotIndex)
{
    swap(a, pivotIndex, right);
    int pos = left;//represents boundary between small and large elements
    for(int i = left; i < right; i++)
    {
        if (a[i] < a[right])
        {
            swap(a, i, pos);
            pos++;
        }
    }
    swap(a, right, pos);
    return pos;
}

لقد أوضحت الكود من خلال وجود مساعد swap طريقة. كان لديك 3 أخطاء في الكود الأصلي:

  • الخطأ لمرة واحدة على حدود الحلقة
  • أنت تستخدم الفهرس الخاطئ للحصول على العنصر المحوري في الحلقة
  • قمت بتبديل العناصر في المؤشرات الخاطئة بعد الحلقة

نصائح أخرى

يتغيرون

for(int i = left; i < right-1; i++)

ل

for(int i = left; i < right; i++)
مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top