3

这是我一个星期以来一直在努力完成的实验室家庭作业。这个问题还有更多，我迷路了。我可以在某个方向使用提示，而不是要求答案。如果我发布了不正确的东西，我很抱歉，我的大脑被炸了。任何帮助将不胜感激。

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

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

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

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

e. 将枢轴元素本身复制到结果中。

F。将更大的元素复制到结果中。

G。返回分区数组结果。

编写一个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;
}
}
4

2 回答 2

3

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

然后你应该创建两个数组lesser和greater长度l-1（因为所有值都可能小于或大于枢轴）。

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

之后，只需（如您的练习）将数据复制到这些数组中。跟踪两个数组的长度，例如lesserlength = 0; greaterlength = 0;每次插入值时递增。这样您就知道可以在哪里插入下一个值lesserand greater。

最终，您可以将 lesser 复制到一个新的 length 数组中l。

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

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

您可以使用System.arraycopy(source, srcpos, dest, dstpos, len)复制lesser并greater进入结果。

这应该足以帮助你。

于 2013-07-30T14:36:57.700 回答
2

这应该可以解决问题：

private static double[] partition(double[] a) {

    //choose some pivot, perhaps randomly?
    Random r = new Random();
    double pivot = a[r.nextInt(a.length)];

    //create lesser and greater arrays
    double[] lesser = new double[a.length];
    double[] greater = new double[a.length];

    //loop through members of a
    int lesserIndex = 0;
    int greaterIndex = 0;

    for (double number : a) {
        if (number < pivot) {
            lesser[lesserIndex++] = number;
        } else {
            greater[greaterIndex++] = number;
        }
    }

    //create result array
    double[] result = new double[a.length];
    int resultIndex = 0;

    //copy in lesser
    for (int i=0; i<lesserIndex; i++) {
        result[resultIndex++] = lesser[i];
    }

    //copy in pivot
    result[resultIndex++] = pivot;

    //copy in greater
    for (int i=0; i<greaterIndex; i++) {
        result[resultIndex++] = greater[i];
    }

    //return result
    return result;

}
于 2013-07-30T14:49:50.550 回答