java - 使用此算法对数组进行分区

Question

这是一项实验室作业，我已经努力了一个星期了。这个问题还有更多，我迷路了。我可以在某个方向使用提示，而不是要求答案。如果我发布的内容不正确，我深表歉意，我的大脑被炸了。任何帮助都将不胜感激。

一个。创建两个名为 lesser 和 greater 的新数组。这些将分别用于存储“a”中小于或大于枢轴元素的元素。

遍历“a”中除枢轴之外的所有元素。如果元素小于枢轴，则将其复制到较小的数组中。如果元素大于或等于主元，则将其复制到更大的数组中。

创建一个名为 result 的新数组，其长度与“a”相同。

将 lesser 的元素复制到结果中。

将数据透视元素本身复制到结果中。

将 greater 的元素复制到结果中。

返回分区后的数组结果。

编写一个public static double[] partition(double[] a)方法来实现这个算法。

public class Lab6 {
public static void main(String[] args) {

}

public static double[] loadRandom(double[] randomNumbersArray)
{
    randomNumbersArray = new double[100000];

    // looping through to assign random values from 1 - 100000
    for (int i = 0; i < randomNumbersArray.length; i++) {
        randomNumbersArray[i] = (int)(Math.random() * 2000000000); 
    }

    return randomNumbersArray;
}

public static double[] partitionInPlace(double[] a)
{
    loadRandom(a);
    double pivotValue = a[0];
    int j = 0;  //j keeps track of which elements have already been placed

    //start by swapping the pivot value with the value at the rightmost index
    a[0] = a[a.length-1];
    a[a.length-1] = pivotValue;

    //go through the array (except for the rightmost index) to find the elements
    //that are < pivotValue
    for (int i = 0; i < a.length-1; i++) {
        //if a[i] is < pivotValue, then swap a[i] and a[j] and incremement j
        if (a[i] < pivotValue) {
            double temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            j++;
        }
    }

    //now move the pivot back from its position on the right
    double temp = a[j];
    a[j] = a[a.length-1];
    a[a.length-1] = temp;

    //return the partitioned array
    return a;
}

public static double[] partition(double[] a) 
{
    double lesser;
    double greater;
    double result;

    return a;
}
}

Answer 1

假设您从长度为 l 的数组 a 开始。

然后你应该创建两个数组 lesser 和 greater，长度为 l-1(因为所有值都可能小于或大于主元).

double[] lesser = new double[a.length() - 1];
double[] greater = new double[a.length() - 1];

之后，它只是(如您的练习中那样)将数据复制到这些数组中。跟踪两个数组的长度，如 lesserlength = 0; greaterlength = 0; 并在每次插入值时递增。这样您就知道可以在 lesser 和 greater 中的何处插入下一个值。

最终您可以将 lesser 复制到长度为 l 的新数组中。

double[] result = new int[a.length()];

你知道 lesserlength + 1 + greaterlength == a.length()

您可以使用 System.arraycopy(source, srcpos, dest, dstpos, len) 将 lesser 和 greater 复制到结果中。

这应该足以帮助您。