Метод сравнения сравнения() сортировка путаницы

Question

Я делаю вопрос самотестирования из книги Кэти и Сейрры. Один из вопросов пошел не так, поэтому я пытался в IDE. Мое замешательство можно найти на этом изображении. Главный вопрос, когда я отлаживал его, я поставил точку отладки в методе сравнения. Если всплывающая подсказка может быть замечена, o1 содержит значение pen. Я думал, что o1 должен быть картой, а o2 - ручкой. Может ли кто-нибудь объяснить мне эту путаницу?

Answer 1

Я не знаю, почему вы ожидаете o1 должны быть карта и o2 должна быть ручка. Для этого нет никакой гарантии, и на самом деле вам не следует заботиться об этом, когда вы применяете метод compare().

Answer 2

Вы можете проверить источник метода Arrays.sort на grepcode и понять его лучше:

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Arrays.java#Arrays.sort%28java.lang.Object%5B%5D%2Cjava.util.Comparator%29

Answer 3

Порядок не имеет значения, когда вы реализуете Comparator, вы просто должны соответствовать тому, что Договор класса и реализовать его по мере необходимости. Вы можете только вывести порядок вызовов, зная ввод и реализацию.

Просто для полноты картины, от OpenJDK 7, это реализация Arrays.sort, который использует сортировка слиянием (анализ ниже):

public static <T> void sort(T[] a, Comparator<? super T> c) { 
    T[] aux = (T[])a.clone(); 
    if (c==null) 
     mergeSort(aux, a, 0, a.length, 0); 
    else 
     mergeSort(aux, a, 0, a.length, 0, c); 
} 

И Arrays::mergeSort:

private static final int INSERTIONSORT_THRESHOLD = 7; 

private static void mergeSort(Object[] src, 
           Object[] dest, 
           int low, int high, int off, 
           Comparator c) { 
    int length = high - low; 

    // Insertion sort on smallest arrays 
    if (length < INSERTIONSORT_THRESHOLD) { 
     for (int i=low; i<high; i++) 
      for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) 
       swap(dest, j, j-1); 
     return; 
    } 

    // Recursively sort halves of dest into src 
    int destLow = low; 
    int destHigh = high; 
    low += off; 
    high += off; 
    int mid = (low + high) >>> 1; 
    mergeSort(dest, src, low, mid, -off, c); 
    mergeSort(dest, src, mid, high, -off, c); 

    // If list is already sorted, just copy from src to dest. This is an 
    // optimization that results in faster sorts for nearly ordered lists. 
    if (c.compare(src[mid-1], src[mid]) <= 0) { 
     System.arraycopy(src, low, dest, destLow, length); 
     return; 
    } 

    // Merge sorted halves (now in src) into dest 
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) { 
     if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) 
      dest[i] = src[p++]; 
     else 
      dest[i] = src[q++]; 
    } 
} 

В вашем примере , это верно: length < INSERTIONSORT_THRESHOLD, поэтому сортировка вставки будет фактически выполнена для этого небольшого массива из 4 элементов.

Редактировать: Неверный mergeSort, исправлено.

Answer 4

Как возник вопрос? Каков был исходный вопрос?

Arrays.sort (Object []) использует Mergesort, но это не имеет большого значения, если все, о чем вы беспокоитесь, получает отсортированный массив. Если вы согласны с требованиями интерфейса Comparator (http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html), ваш массив будет отсортирован правильно.