QuickSort { public static <T> int partition(T[] array, int startIndex, int endIndex, Comparator<T> comparator, int pivotIndex) { if (pivotIndex == -1) { pivotIndex = getRandomPivotIndex(startIndex, endIndex); } com.github.kowshik.bigo.common.ArrayUtils.swap(array, pivotIndex, endIndex); int swapIndex = startIndex - 1; for (int index = startIndex; index <= endIndex - 1; index++) { if (comparator.compare(array[index], array[endIndex]) <= 0) { swapIndex++; com.github.kowshik.bigo.common.ArrayUtils.swap(array, swapIndex, index); } } com.github.kowshik.bigo.common.ArrayUtils.swap(array, swapIndex + 1, endIndex); return swapIndex + 1; }  static T[] quickSort(T[] array, Comparator<T> comparator); static int partition(T[] array, int startIndex, int endIndex,
			Comparator<T> comparator, int pivotIndex);  }
@Test public void onlyPivotsInArray() { Integer[] array = { 3, 3, 3, 3, 3 }; int pivotIndex = QuickSort.partition(array, 0, array.length - 1, ascOrderComparator, 3); assertEquals(4, pivotIndex); assertArrayEquals( "Failure => Array returned is not partitioned according to the pivot.", array, new Integer[] { 3, 3, 3, 3, 3 }); }
@Test public void smallerElementsAndPivotsInArray() { Integer[] array = { 3, 0, 2, 3, -1, -2, 0, 3 }; int pivotIndex = QuickSort.partition(array, 0, array.length - 1, ascOrderComparator, 3); assertEquals(7, pivotIndex); assertArrayEquals( "Failure => Array returned is not partitioned according to the pivot.", array, new Integer[] { 3, 0, 2, 3, -1, -2, 0, 3 }); }
@Test public void largerElementsAndPivotsInArray() { Integer[] array = { 3, 10, 4, 3, 5, 7, 7, 3 }; int pivotIndex = QuickSort.partition(array, 0, array.length - 1, ascOrderComparator, 3); assertEquals(2, pivotIndex); assertArrayEquals( "Failure => Array returned is not partitioned according to the pivot.", array, new Integer[] { 3, 3, 3, 10, 5, 7, 7, 4 }); }