java实现的一个【快速排序 】算法【原创】

时间:2022-02-07 15:08:02
import java.util.Arrays;
import org.apache.commons.lang.ArrayUtils; public class Test { public static void main(String[] args) {
int[] sortedArrays = quickSort(new int[]{3, 5, 1, 2});
System.out.println(ArrayUtils.toString(sortedArrays));
} /**
* Run time is O(nlogn)
*
* @param source source array
* @return sorted array
*/
private static int[] quickSort(int[] source) { int sourceSize = source.length; final byte baseLen = 2; // An array that is empty or contains only one element is ordered
if (sourceSize < baseLen) {
return source;
} // pivot value
int pivotVal = source[sourceSize / 2]; return combineList(quickSort(sortLeft(source, pivotVal)), pivotVal, quickSort(sortRight(source, pivotVal)));
} private static int[] sortLeft(int[] source, int pivotVal) {
return sort(source, pivotVal, true);
} private static int[] sortRight(int[] source, int pivotVal) {
return sort(source, pivotVal, false);
} private static int[] sort(int[] source, int pivotVal, boolean isLeft) {
int[] subArray = new int[source.length - 1];
int j = 0;
for (int value : source) {
boolean condition = isLeft && value < pivotVal || !isLeft && value > pivotVal;
if (condition) {
subArray[j++] = value;
}
}
return Arrays.copyOf(subArray, j);
} private static int[] combineList(int[] less, int pivotVal, int[] greater) {
int[] a1 = ArrayUtils.add(less, pivotVal);
return ArrayUtils.addAll(a1, greater);
} }