11. Sort
Sorting
Java use modified mergesort by java.util.Collections.sort to sort object
Guarantees O(nlogn) performance and O(n) extra space
Stable in all kinds of input
Java use quicksort in java.util.Arrays.sort
Avarage less than O(nlogn), worst case O(n^2)
Average O(logn) extra space, worst case O(n/2) extra space
Stable only in primitive type
Quicksort
private static int partition(int[] arr, int left, int right){
int pivot = arr[right];
int i = left; // index small or equal to left
for (int j = left; j < right; j++){
if (arr[j] <= pivot){
// swap
swap(arr, i ,j);
i++;
}
}
// swap pivot value and i index value;
swap(arr, i, right);
return i;
}
private static void quickSort(int[] arr, int left, int right){
if (left < right){
int pi = partition(arr, left, right);
quickSort(arr, left, pi - 1);
quickSort(arr, pi + 1, right);
}
}
Last updated
Was this helpful?