我有一种通用数组的代码。唯一的问题是,我希望输出带有索引,而不是实际的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);
但是,输入列表中的元素位置不会更改。相反,指定按排列数组排序。数组中的元素数与输入数据列表中的元素数相同。每个τ 元素指定排序后对应输入元素的索引。在内部,您只使用排列数组,而不使用输入元素的进一步列表。
3条答案
按热度按时间at0kjp5o1#
您可以创建如下所示的类(请注意,它是伪代码)
您可以使用double、integer(无论实现什么)的输入数组创建这个对象的数组,并对objectwithindex的新数组进行排序。
排序后,您可以打印索引(其中将包含您输入的原始索引)
vktxenjb2#
如果索引是整数类型而不是本机int,则可以使用lambda比较。只有索引数组需要是整数类型,值数组可以是基元类型。
siotufzp3#
不修改合并算法的最简单方法是:
创建要排序的数组的副本;
对数组进行排序;
比较副本和排序的数组,找出索引。
例如:
如果出于某种奇怪的原因,只能使用数组和基本运算符,则上述逻辑仍然成立:
副本:
排序:
获取索引: