带置换数组的通用mergesort

nkhmeac6  于 2021-07-07  发布在  Java
关注(0)|答案(3)|浏览(399)

我有一种通用数组的代码。唯一的问题是,我希望输出带有索引,而不是实际的int、float或其他什么。你们知道怎么做吗?以下是我目前掌握的代码:

class MergeSortGeneric<T extends Comparable<? super T>> {
public static void main(String[] args)
    {
    // example using Strings
    String[] arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", 
 "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", 
"Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
    MergeSortGeneric<String> stringSorter   = new MergeSortGeneric<>();
    stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);
    System.out.println(java.util.Arrays.toString(arrayOfStrings));

    // example using Doubles
    Double[] arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 
0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
    MergeSortGeneric<Double> doubleSorter   = new MergeSortGeneric<>();
    doubleSorter.mergeSort(arrayOfDoubles, 0, arrayOfDoubles.length - 1);
    System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    // main function that sorts array[start..end] using merge()
    void mergeSort(T[] array, int start, int end)
    {
    // base case
    if (start < end)
    {
       // find the middle point
       int middle = (start + end) / 2;

       mergeSort(array, start, middle); // sort first half
       mergeSort(array, middle + 1, end);  // sort second half

      // merge the sorted halves
      merge(array, start, middle, end);
    }
    }

    // merges two subarrays of array[].
    void merge(T[] array, int start, int middle, int end)
    {
    T[] leftArray  = (T[]) new Comparable[middle - start + 1];
    T[] rightArray = (T[]) new Comparable[end - middle];

    // fill in left array
    for (int i = 0; i < leftArray.length; ++i)
    leftArray[i] = array[start + i];

    // fill in right array
    for (int i = 0; i < rightArray.length; ++i)
    rightArray[i] = array[middle + 1 + i];

    /* Merge the temp arrays */

    // initial indexes of first and second subarrays
    int leftIndex = 0, rightIndex = 0;

    // the index we will start at when adding the subarrays back into the main array
    int currentIndex = start;

    // compare each index of the subarrays adding the lowest value to the currentIndex
    while (leftIndex < leftArray.length && rightIndex < rightArray.length)
    {
    if (leftArray[leftIndex].compareTo(rightArray[rightIndex]) <= 0)
    {
    array[currentIndex] = leftArray[leftIndex];
    leftIndex++;
    }
    else
    {
    array[currentIndex] = rightArray[rightIndex];
    rightIndex++;
    }
    currentIndex++;
    }

    // copy remaining elements of leftArray[] if any
    while (leftIndex < leftArray.length) array[currentIndex++] = leftArray[leftIndex++];

    // copy remaining elements of rightArray[] if any
    while (rightIndex < rightArray.length) array[currentIndex++] = rightArray[rightIndex++];
    }
}

谢谢你们给我小费。顺便说一下,这就是任务:实现合并排序算法。该算法对任何元素的java.util.list进行排序。因此类必须是泛型的。为了排序它得到一个匹配的比较器。

var data = Arrays.asList(23, 42, 11, 1, 12);
var mergeSort = new MergeSort<Integer>();
mergeSort.setup(data, (i1, i2) -> i1 - i2);

但是,输入列表中的元素位置不会更改。相反,指定按排列数组排序。数组中的元素数与输入数据列表中的元素数相同。每个τ 元素指定排序后对应输入元素的索引。在内部,您只使用排列数组,而不使用输入元素的进一步列表。

at0kjp5o

at0kjp5o1#

您可以创建如下所示的类(请注意,它是伪代码)

import java.util.Arrays;

public class SomeClass {

    public static void main(String[] args) {
        double[] doubleArray = new double[] {2.3, 3.4, 1.2, 0.3, 4.3};
        ObjectWithIndex[] objectWithIndexAr = new ObjectWithIndex[doubleArray.length];
        for (int i = 0; i < doubleArray.length; i++) {
            objectWithIndexAr[i] = new ObjectWithIndex(i, doubleArray[i]);
        }

        Arrays.sort(objectWithIndexAr);

        for ( ObjectWithIndex obj : objectWithIndexAr) {
            System.out.println("index: " + obj.index + " value: " + obj.actualObject);
        }
    }
}

class ObjectWithIndex implements Comparable<ObjectWithIndex> {
    int index;
    Comparable actualObject;

    public ObjectWithIndex(int index, Comparable object) {
        this.index = index;
        this.actualObject = object;
    }

    @Override
    public int compareTo(ObjectWithIndex o) {
        return this.actualObject.compareTo(o.actualObject);
    }
}

您可以使用double、integer(无论实现什么)的输入数组创建这个对象的数组,并对objectwithindex的新数组进行排序。
排序后,您可以打印索引(其中将包含您输入的原始索引)

vktxenjb

vktxenjb2#

如果索引是整数类型而不是本机int,则可以使用lambda比较。只有索引数组需要是整数类型,值数组可以是基元类型。

package x;
import java.util.Arrays;
public class x {
    public static void main(String[] args) {
        int[] A = {3, 1, 2, 0};
        Integer[] I = {0, 1, 2, 3};
        Arrays.sort(I, (i, j) -> A[i]-A[j]);
        for (Integer i : I) {
            System.out.println(A[i]);
        }
    }
}
siotufzp

siotufzp3#

不修改合并算法的最简单方法是:
创建要排序的数组的副本;
对数组进行排序;
比较副本和排序的数组,找出索引。
例如:

String[] arrayOfStrings = {...};
List<String> copyArrayOfStrings = Arrays.stream(arrayOfStrings).collect(Collectors.toList());

...
stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);
...

List<Integer> index = Arrays.stream(arrayOfStrings).map(copyArrayOfStrings::indexOf).collect(Collectors.toList());
System.out.println(java.util.Arrays.toString(index.toArray()));

如果出于某种奇怪的原因,只能使用数组和基本运算符,则上述逻辑仍然成立:
副本:

String[] copyArrayOfStrings = new String[arrayOfStrings.length];
    for(int i  = 0; i < arrayOfStrings.length; i++){
       copyArrayOfStrings[i] = arrayOfStrings[i];
    }

排序:

stringSorter.mergeSort(arrayOfStrings, 0, arrayOfStrings.length - 1);

获取索引:

Integer[] index = new Integer[copyArrayOfStrings.length];
    int index_pos = 0;
    for(String s : arrayOfStrings) {
        for (int i = 0; i < copyArrayOfStrings.length; i++) {
            if(copyArrayOfStrings[i].equals(s)){
                index[index_pos++] = i;
                break;
            }
        }
    }

    System.out.println(java.util.Arrays.toString(index));

相关问题