Arrays.sort (Object [] a) - как это реализовано? - PullRequest
Новая
       15

Arrays.sort (Object [] a) - как это реализовано?

6 голосов
/ 07 февраля 2010

Существуют ли какие-либо ресурсы о том, как реализована функция mergeSort, используемая Arrays.sort (Object [] a)? Хотя это задокументировано довольно хорошо, мне трудно понять это (особенно почему src и dest переключаются, когда mergeSort () get вызывается рекурсивно).

Ответы [ 2 ]

11 голосов
/ 07 февраля 2010

Вот источник из java.util.Arrays.

На самом деле, у вас есть этот исходный код в JDK - просто откройте java.util.Arrays в вашей IDE и в исходном коде + появятся комментарии. Если у вас нет IDE, посмотрите на JDK_HOME\src.zip

Затем поместите его в IDE и проследите, как он работает.

  • установить точки останова (и запустить программу в режиме отладки)
  • использовать System.out.println(..)
  • измените его части, чтобы увидеть, как они отражаются.
  • прочитайте статью в Википедии о сортировке слиянием
  • обратите внимание на этот комментарий: // Recursively sort halves of dest into src
0 голосов
/ 19 ноября 2010

У меня когда-либо было такое же замешательство с вами.Насколько я понимаю, причина такого переключения очень проста - упростить последующий шаг слияния.Никакой магии. 

    private static void mergeSortWithoutSwitch(Object[] src, Object[] dest, int low, int high, int off) {
    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 && ((Comparable) dest[j - 1]).compareTo(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;
    mergeSortWithoutSwitch(src, dest, low, mid, off);
    mergeSortWithoutSwitch(src, dest, mid, high, off);

    // 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 (((Comparable) dest[mid - 1]).compareTo(dest[mid]) <= 0) {
        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 && ((Comparable) dest[p]).compareTo(dest[q]) <= 0)
            src[i] = dest[p++];
        else
            src[i] = dest[q++];
    }

    // copy back
    for (int i = destLow; i < destHigh; i++) {
        dest[i] = src[i];
    }

}

Выше приведена реализация без переключения из кода, вы можете видеть, что нам нужно сделать еще один шаг в объединении - скопировать обратно.Я думаю, что именование параметров в mergeSort немного запутано, так как src является вспомогательным массивом, который используется только на этапе слияния, будет лучше назвать его с помощью aux (мы можем даже удалить его из сигнатуры метода и создать локальную переменнуюпри слиянии).И dest - это массив результатов.

...