在 Java 中实现自定义快速排序算法
Implementing a custom quick sort algorithm in Java
教授先生分配给我们的任务是编写一个自定义的 quksort 算法，我们必须使用他的大纲来实现（我不能从头开始自己写，我必须使用他的）。他称之为 smartQuickSort，而这个算法 "custom" 的原因是我们必须计算枢轴点每一侧的平均值，然后用于对数组进行排序。该算法使用一个名为 SmartQuickSortPivot 的 class，它具有整数值 left 和 right 分别保存 left/right 侧的平均值。
我已经用多种语言编写了许多快速排序算法，但我终其一生都无法使这个算法正确排序。我已经花了 3 天时间重写和调试这个东西但没有成功，所以我真的希望有人能帮助我，因为我正要把我所有的头发都拔出来。从他给我们的 "skeleton code" 开始（包括注释说明），这是我最近的尝试：
/**
* 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);
}
}
}
这里是class用来存储平均值到枢轴点的left/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对象参数，但本质上是一样的，而且运行完美，所以我很困惑为什么我无法让 "custom" 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()的return值从last更改为rightLeftAverages.left和rightLeftAverages.right的不同组合，这会导致堆栈溢出递归。这是我真正感到困惑的地方，因为我不确定在这个快速排序的特定实现中应该 return 使用什么方法（更重要的是，如何正确计算它）。
我认为我的问题是双重的；我要么没有正确计算枢轴每一侧的平均值（我使用了许多枢轴点，其中 none 似乎有所作为），而且我没有 return split4SmartQuickSort() 方法本身的正确计算。如果我从方法参数中删除 rightLeftAverages 对象并使用更传统的方法进行快速排序，则该算法可以正常工作。这就是为什么我认为我列出的这两个问题是算法无法正常运行的原因。来自 split4SmartQuickSort() 的 return 值（我认为）充当新的排序轴心点，使用 splitVal 参数作为原始轴心点。
是的，这是我的作业，但我已经为此付出了数小时的努力，但没有成功。我的教授周末不回复电子邮件，他的办公时间正好在我的另一个 class 期间，所以我无处可求。
我认为您对此有疑问，因为在这种情况下很难使用一个整数分割点。原因如下：
想象一下，在某些算法中，您得到 44、51、89、66 以 62.5 ~ 62 的平均值进行划分。如果您使用 62 作为枢轴元素，则不确定 return 是什么拆分点（因为您可以 return 索引 1 或 2（相应值为 51 或 89））。
假设您选择 2。这将导致算法无效（让我们记住分割点（枢轴）a_j 是将数组分成两个子数组的点，例如每个 i < j a_i < a_j并且对于每个 k > j a_j < a_k) 因为 89 !< 66 并且不能成为分割点。
你需要做的是 return 中间的东西作为分割点。为此，您需要 return SmartQuickSortPivot 对象而不是 int 并将其 left/right 值用作 left/right 数组的 ending/starting 索引。
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));
}
}
多亏了下面的好建议，我的算法开始工作了，但它仍然没有正确地对重复项进行排序（遇到重复项时会无限循环）。玩完代码后，我现在有了一个完整的工作算法。更改仅在 split4SmartQuickSort() 中，因此这里更新了该方法：
static SmartQuickSortPivot split4SmartQuickSort
(int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
{
int f = first;
int l = last;
int sumLeft = 0;
int sumRight = 0;
while (f < l)
{
while (values[f] < splitVal)
{
sumLeft += values[f];
f++;
}
while (values[l] > splitVal)
{
sumRight += values[l];
l--;
}
if (f <= l)
{
swap(f, l);
//handling duplicates in the list
if (values[f] == values[l])
{
f++;
}
}
}
if (f - first == 0)
{
leftRightAverages.left = values[first];
}
else
{
leftRightAverages.left = sumLeft / (f - first);
}
if (last - l == 0)
{
leftRightAverages.right = values[last];
}
else
{
leftRightAverages.right = sumRight / (last - l);
}
//create SmartQuickSortPivot object to be returned. Used in
//smartQuickSort as the split point for sorting
SmartQuickSortPivot sqsp = new SmartQuickSortPivot();
sqsp.left = f;
sqsp.right = l;
return sqsp;
}
最后，smartQuickSort() 算法：
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);
}
}
}
再次感谢@shyyko-serhiy，因为他们让这个东西运行起来应该得到大部分的赞誉:)
教授先生分配给我们的任务是编写一个自定义的 quksort 算法，我们必须使用他的大纲来实现（我不能从头开始自己写，我必须使用他的）。他称之为 smartQuickSort，而这个算法 "custom" 的原因是我们必须计算枢轴点每一侧的平均值，然后用于对数组进行排序。该算法使用一个名为 SmartQuickSortPivot 的 class，它具有整数值 left 和 right 分别保存 left/right 侧的平均值。
我已经用多种语言编写了许多快速排序算法，但我终其一生都无法使这个算法正确排序。我已经花了 3 天时间重写和调试这个东西但没有成功，所以我真的希望有人能帮助我，因为我正要把我所有的头发都拔出来。从他给我们的 "skeleton code" 开始（包括注释说明），这是我最近的尝试：
/**
* 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);
}
}
}
这里是class用来存储平均值到枢轴点的left/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对象参数，但本质上是一样的，而且运行完美，所以我很困惑为什么我无法让 "custom" 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()的return值从last更改为rightLeftAverages.left和rightLeftAverages.right的不同组合，这会导致堆栈溢出递归。这是我真正感到困惑的地方，因为我不确定在这个快速排序的特定实现中应该 return 使用什么方法（更重要的是，如何正确计算它）。
我认为我的问题是双重的；我要么没有正确计算枢轴每一侧的平均值（我使用了许多枢轴点，其中 none 似乎有所作为），而且我没有 return split4SmartQuickSort() 方法本身的正确计算。如果我从方法参数中删除 rightLeftAverages 对象并使用更传统的方法进行快速排序，则该算法可以正常工作。这就是为什么我认为我列出的这两个问题是算法无法正常运行的原因。来自 split4SmartQuickSort() 的 return 值（我认为）充当新的排序轴心点，使用 splitVal 参数作为原始轴心点。
是的，这是我的作业，但我已经为此付出了数小时的努力，但没有成功。我的教授周末不回复电子邮件，他的办公时间正好在我的另一个 class 期间，所以我无处可求。
我认为您对此有疑问，因为在这种情况下很难使用一个整数分割点。原因如下：
想象一下，在某些算法中，您得到 44、51、89、66 以 62.5 ~ 62 的平均值进行划分。如果您使用 62 作为枢轴元素，则不确定 return 是什么拆分点（因为您可以 return 索引 1 或 2（相应值为 51 或 89））。
假设您选择 2。这将导致算法无效（让我们记住分割点（枢轴）a_j 是将数组分成两个子数组的点，例如每个 i < j a_i < a_j并且对于每个 k > j a_j < a_k) 因为 89 !< 66 并且不能成为分割点。
你需要做的是 return 中间的东西作为分割点。为此，您需要 return SmartQuickSortPivot 对象而不是 int 并将其 left/right 值用作 left/right 数组的 ending/starting 索引。
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));
}
}
多亏了下面的好建议，我的算法开始工作了，但它仍然没有正确地对重复项进行排序（遇到重复项时会无限循环）。玩完代码后，我现在有了一个完整的工作算法。更改仅在 split4SmartQuickSort() 中，因此这里更新了该方法：
static SmartQuickSortPivot split4SmartQuickSort
(int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
{
int f = first;
int l = last;
int sumLeft = 0;
int sumRight = 0;
while (f < l)
{
while (values[f] < splitVal)
{
sumLeft += values[f];
f++;
}
while (values[l] > splitVal)
{
sumRight += values[l];
l--;
}
if (f <= l)
{
swap(f, l);
//handling duplicates in the list
if (values[f] == values[l])
{
f++;
}
}
}
if (f - first == 0)
{
leftRightAverages.left = values[first];
}
else
{
leftRightAverages.left = sumLeft / (f - first);
}
if (last - l == 0)
{
leftRightAverages.right = values[last];
}
else
{
leftRightAverages.right = sumRight / (last - l);
}
//create SmartQuickSortPivot object to be returned. Used in
//smartQuickSort as the split point for sorting
SmartQuickSortPivot sqsp = new SmartQuickSortPivot();
sqsp.left = f;
sqsp.right = l;
return sqsp;
}
最后，smartQuickSort() 算法：
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);
}
}
}
再次感谢@shyyko-serhiy，因为他们让这个东西运行起来应该得到大部分的赞誉:)