сортировка слиянием слияния в Java

Question

Мне пришлось написать функцию сортировки слиянием в Java. Нет проблем. Ну, немного, но я пережил это. Тогда следующий вопрос я не получил.

Вопрос: Задан массив A[][], такой что A[i][0] является float, а A[i][1] является неотрицательным int, дающим кратность значения A[i][0] (здесь представьте большой вектор, который свернут сложив повторяющиеся записи и записав, сколько их было объединено), напишите версию сортировки слиянием, которая возвращает B[][], где B[i][0] < B[i+1][0] для всех i.

Есть идеи? Лучшее, что я мог сделать, это объединить сортировку и затем сгруппировать равные, но, очевидно, вы можете сделать все это за один шаг.

Answer 1

Strage вопрос ... и использование различных типов в этих массивах просто уродливо (личная точка зрения) .

Однако самое полезное, что нужно сделать, это переписать вашу функцию слияния с Comparator. Таким образом, вы можете сортировать, используя любое свойство, которое вы хотите. Вы бы в конечном итоге с подписью, как void merge(A[] arr, Comparator<? super A> comp). Кстати, Java-реализация sort очень похожа на это.

Чтобы решить свой вопрос, позвоните по номеру:

A[][] a = ...;
merge(a, new Comparator<A[]>() {
  int compare(A[] a, A[] b) {
    return ((Float)a[0]) - ((Float)b[0]);
  }
});