سؤال
لذلك أحاول إنشاء طريقة 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++)
لا تنتمي إلى StackOverflow