看雪恶意程序分析与高级对抗技术
快速排序
每次将等待排序的数据划分成两部分
递归进行
直到所有数据有序
import java.util.ArrayList;import java.util.Arrays;import java.util.Collection;import java.util.List;import java.util.stream.Collectors;import java.util.stream.Stream;public class QuickSort {
public static void main(String[] args) {
int[] array = {5, 1, 6, 2, 4, 2, 3};
List<Integer> list = quickSort(Arrays.asList(5, 1, 6, 2, 4, 2, 3));
quickSortForInPlace(array);
System.out.println(list);
}
// 分治法(Divide and conquer)需要O(n)的额外空间
public static List<Integer> quickSort(List<Integer> list) {
if (list.size() <= 1) {
return list;
}
List<Integer> left = new ArrayList<>(), pivot = new ArrayList<>(), right = new ArrayList<>();
Integer pivotValue = list.get(0);
for (Integer element : list) {
if (element < pivotValue) {
left.add(element);
} else if (element.equals(pivotValue)) {
pivot.add(element);
} else {
right.add(element);
}
}
return Stream.of(quickSort(left), pivot, quickSort(right)).flatMap(Collection::stream).collect(Collectors.toList());
}
// 原地(in-place)分割版本
public static void quickSortForInPlace(int[] array) {
quickSortPartition(array, 0, array.length - 1);
}
// 对数组中的某个区域进行排序
public static void quickSortPartition(int[] array, int left, int right) {
if (right > left) {
// 将 [left - right] 区域分成了
// [left, pivotIndex - 1] 和 [pivotIndex + 1, right] 两个
int pivotIndex = partition(array, left, right);
quickSortPartition(array, left, pivotIndex - 1);
quickSortPartition(array, pivotIndex + 1, right);
}
}
public static int partition(int[] array, int left, int right) {
// 挑选最右侧的作为基准值
int pivotValue = array[right];
int storeIndex = left;
for (int i = left; i < right; i++) {
if (array[i] <= pivotValue) {
swap(array, i, storeIndex);
storeIndex += 1;
}
}
swap(array, storeIndex, right);
return storeIndex;
}
private static void swap(int[] x, int a, int b) {
int t = x[a];
x[a] = x[b];
x[b] = t;
}}
