|
|
Beschreibe hier die neue Seite. |
|
Von SoftwareDenkSport 1 Auflösung Der folgende Ausschnitt stammt aus dem Originalsource von "class Arrays" und sollte alle Fragen beantworten, die sich in Bezug auf eine weitere Optimierbarkeit von "sort" stellen: [[Code] public static void sort(Object[] a) { Object aux[] = (Object[])a.clone(); mergeSort(aux, a, 0, a.length); } /** * Sorts the specified range of the specified array of objects into * ascending order, according to the natural ordering of its * elements. All elements in this range must implement the * Comparable interface. Furthermore, all elements in this range * must be mutually comparable (that is, e1.compareTo(e2) * must not throw a ClassCastException? for any elements * e1 and e2 in the array).<p> * * This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort.<p> * * The sorting algorithm is a modified mergesort (in which the merge is * omitted if the highest element in the low sublist is less than the * lowest element in the high sublist). This algorithm offers guaranteed * n*log(n) performance, and can approach linear performance on nearly * sorted lists. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @throws IllegalArgumentException? if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException? if fromIndex < 0 or * toIndex > a.length * @throws ClassCastException? if the array contains elements that are * not mutually comparable (for example, strings and * integers). * @see Comparable */ public static void sort(Object[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); Object aux[] = (Object[])a.clone(); // Optimization opportunity mergeSort(aux, a, fromIndex, toIndex); } private static void mergeSort(Object src[], Object dest[], int low, int high) { int length = high - low; // Insertion sort on smallest arrays if (length < 7) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int mid = (low + high)/2; mergeSort(dest, src, low, mid); mergeSort(dest, src, mid, high); // 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)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) { System.arraycopy(src, low, dest, low, length); return; } // Merge sorted halves (now in src) into dest for(int i = low, p = low, q = mid; i < high; i++) { if (q>=high || p<mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } } /** * Swaps x[a] with x[b]. */ private static void swap(Object x[], int a, int b) { Object t = x[a]; x[a] = x[b]; x[b] = t; } ] KategorieJava |
|
|