教授先生给我们分配了编写一个自定义快速排序算法的任务，我们必须使用他的大纲来实现该算法(我不能从头开始编写自己的算法，我必须使用他的大纲)。他称之为smartQuickSort ，这个算法“自定义”的原因是我们必须计算枢轴点每一侧的平均值，然后用于对数组进行排序。该算法使用一个名为 SmartQuickSortPivot 的类其中有 int 值 left和right分别将平均值保留在左侧/右侧。
我已经用多种语言编写了许多快速排序算法，但我一生都无法让这个算法正确排序。我花了三天时间重写和调试这个东西，但没有成功，所以我真的希望有人能帮助我，因为我即将把我所有的头发都拔出来。从他给我们的“骨架代码”(包括注释说明)开始，这是我最新的尝试:
/**
* split4SmartQuickSort splits the array (from first to last) into two subarrays, left and right, using the
* provided splitVal. It needs to calculate on the fly the average of all the elements of the left subarray
* and average of all elements of the right subarray, and store the two averages in the @pivot object.
* The following implementation is only copy of the code from
* the split function (from line 247) and you should enhance the function to implement what we need to calculate the averages
* as the pivot for the left and right subarray.
*
* Please be noted that splitVal may not even exist in the array since we choose the average.
* But this should not impact the correctness algorithm of splitting and sorting.
* @param first
* @param last
* @param splitVal
* @param leftRightAverages
* @return
*/
static int split4SmartQuickSort(int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
{
int saveF = first;
int leftAvg = 0;
int leftCount = 0;
int rightAvg = 0;
int rightCount = 0;
boolean onCorrectSide;
first++;
do
{
onCorrectSide = true;
while (onCorrectSide) // move first toward last
if (values[first] > splitVal)
onCorrectSide = false;
else
{
//I think my average calculations here are wrong,
//but nothing I have tried works correctly
leftAvg += first;
leftCount++;
first++;
leftRightAverages.left = leftAvg / leftCount;
onCorrectSide = (first <= last);
}
onCorrectSide = (first <= last);
while (onCorrectSide) // move last toward first
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
//I think my average calculations here are wrong,
//but nothing I have tried works correctly
rightAvg += last;
rightCount++;
last--;
leftRightAverages.right = rightAvg / rightCount;
onCorrectSide = (first <= last);
}
if (first < last)
{
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
//I think this is one of my problems. Not sure
//what I should be returning here
return last;
}
/**
* Smart quick sort allows the use of a better splitting value (the pivot value) when to split the array
* into two. In this algorithm, we will use the average of the array (subarray) of all elements as the pivot.
*
* Each call to split (split4SmartQuickSort method), the splitValue will be passed and also the split4SmartQuickSort
* will return the averages of left subarray and right subarray. The two averages, each will be used for the
* following calls to smartQuickSort.
*
* @param first the first element
* @param last the last element
* @param splitVal the pivot value for splitting the array
*/
static void smartQuickSort(int first, int last, int splitVal)
{
if (first < last)
{
int splitPoint;
SmartQuickSortPivot leftRightAverages = new SmartQuickSortPivot();
splitPoint = split4SmartQuickSort(first, last, splitVal, leftRightAverages);
if (first <= splitPoint)
{
smartQuickSort(first, splitPoint - 1, leftRightAverages.left);
}
if (last >= splitPoint)
{
smartQuickSort(splitPoint + 1, last, leftRightAverages.right);
}
}
}
这是用于存储枢轴点左/右平均值的类:
public class SmartQuickSortPivot {
public int left;
public int right;
}
最后是用于测试的主要方法:
public static void main(String[] args)
{
//initValues();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
//quickSort(0, values.length - 1);
/** you can either compute the average first as the first pivot or simplify choose the first one as the pivot */
smartQuickSort(0, values.length - 1, values[4]);
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
}
}
我注释掉的行，//quickSort(0, values.length - 1);是我写的算法，不包括 leftRightAverages对象参数，但本质上是相同的，而且它工作得很好，所以我很困惑为什么我不能得到“自定义”smartQuickSort上类。为了简单起见，我注释掉了 initValues()方法，而是使用如下所示的预设数组:
static int[] values = {2,5,1,66,89,44,32,51,8,6}; // values to be sorted
我尝试过的事情(但失败了):
1.) 移动行 leftRightAverages.left = leftAvg / leftCount; , leftRightAverages.right = rightAvg / rightCount;在 do-while 循环之外，(我认为)由于函数的递归性质，最终给我除以零 RTE。
2.) 更改 split4SmartQuickSort() 的返回值来自last rightLeftAverages.left 的不同组合和rightLeftAverages.right ，这会导致递归堆栈溢出。这就是我真正感到困惑的地方，因为我不确定这个方法在快速排序的特定实现中应该返回什么(更重要的是，如何正确计算它)。
我认为我的问题是双重的；我要么没有正确计算枢轴每一侧的平均值(我使用了许多枢轴点，但它们似乎都没有区别)，并且我没有从split4SmartQuickSort()返回正确的计算结果。方法本身。如果我删除 rightLeftAverages从方法参数中获取对象并使用更传统的方法进行快速排序，该算法运行良好。这就是为什么我认为我列出的这两个问题是算法无法正常运行的原因。 split4SmartQuickSort() 的返回值(我认为)充当排序的新枢轴点，使用 splitVal参数作为原始枢轴点。
是的，这是我的作业，但我在这件事上投入了数小时的真正努力，但没有运气。我的教授周末不回复电子邮件，而且他的办公时间是在我的另一门课期间，所以我无处可去。
最佳答案
我认为您对此有问题，因为在这种情况下很难使用一个整数分割点。原因如下:
想象一下，在某些算法中，您需要 44、51、89、66 进行划分，平均值为 62.5 ~ 62。如果您使用 62 作为主元元素，则不确定返回什么作为分割点(因为您可以返回索引 1 或 2(相应的值 51 或 89)。
假设您选择 2。这将导致无效的算法(请记住，分割点(枢轴) a_j 是将数组分为两个子数组的点，例如每个 i < j a_i < a_j 和每个 k > j a_j < a_k )，因为89 !< 66并且不能是分割点。
你需要做的就是返回中间的一些东西作为分割点。为此，您需要返回 SmartQuickSortPivot object 而不是 int 并使用它的左/右值作为左/右数组的结束/开始索引。
import java.util.Arrays;
public class Temp {
public static class SmartQuickSortPivot {
public int left;
public int right;
}
static int[] values = {2,5,1,66,89,44,32,51,8,6}; // values to be sorted
/**
* split4SmartQuickSort splits the array (from first to last) into two subarrays, left and right, using the
* provided splitVal. It needs to calculate on the fly the average of all the elements of the left subarray
* and average of all elements of the right subarray, and store the two averages in the @pivot object.
* The following implementation is only copy of the code from
* the split function (from line 247) and you should enhance the function to implement what we need to calculate the averages
* as the pivot for the left and right subarray.
*
* Please be noted that splitVal may not even exist in the array since we choose the average.
* But this should not impact the correctness algorithm of splitting and sorting.
* @param first
* @param last
* @param splitVal
* @param leftRightAverages
* @return
*/
static SmartQuickSortPivot split4SmartQuickSort(int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
{
int i = first,j = last;
int sumLeft = 0;
int sumRight = 0;
while (i < j) {
while (values[i] < splitVal){
sumLeft += values[i];
i++;
}
while (values[j] > splitVal){
sumRight += values[j];
j--;
}
if (i < j) {
swap(i, j);
}
}
leftRightAverages.left = (i - first == 0) ? values[first] : sumLeft / (i - first);
leftRightAverages.right = (last - j == 0) ? values[last] : sumRight / (last - j);
SmartQuickSortPivot smartQuickSortPivot = new SmartQuickSortPivot();
smartQuickSortPivot.left = i;
smartQuickSortPivot.right = j;
return smartQuickSortPivot;
}
private static void swap(int i, int j) {
int temp = values[i];
values[i] = values[j];
values[j] = temp;
}
/**
* Smart quick sort allows the use of a better splitting value (the pivot value) when to split the array
* into two. In this algorithm, we will use the average of the array (subarray) of all elements as the pivot.
*
* Each call to split (split4SmartQuickSort method), the splitValue will be passed and also the split4SmartQuickSort
* will return the averages of left subarray and right subarray. The two averages, each will be used for the
* following calls to smartQuickSort.
*
* @param first the first element
* @param last the last element
* @param splitVal the pivot value for splitting the array
*/
static void smartQuickSort(int first, int last, int splitVal)
{
if (first < last)
{
SmartQuickSortPivot splitPoint;
SmartQuickSortPivot leftRightAverages = new SmartQuickSortPivot();
splitPoint = split4SmartQuickSort(first, last, splitVal, leftRightAverages);
if (first < splitPoint.left)
{
smartQuickSort(first, splitPoint.left - 1, leftRightAverages.left);
}
if (last > splitPoint.right)
{
smartQuickSort(splitPoint.right + 1, last, leftRightAverages.right);
}
}
}
public static void main(String[] args)
{
/** you can either compute the average first as the first pivot or simplify choose the first one as the pivot */
smartQuickSort(0, values.length - 1, values[5]);
System.out.println(Arrays.toString(values));
}
}
关于java - 用Java实现自定义快速排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43419574/