1. 快速排序
快排最优复杂度是 O(n*log(n))，但是要使用辅助栈，总共要排序n次，每次查找中间值复杂度是O(logn)
75 快速排序, 此题用快排会超时，经典3种颜色，需要特殊处理
// 快排
void quick_sort(int[]arr, int low, inthigh){
if (low>=high) return;
// for找出中间值，O(logn)
int i = partition(arr, low, high);
// f(n/2) - 分治左
quick_sort(arr, low, i-1);
// f(n/2) - 分治右
quick_sort(arr, i+1, high);
}
private int partition(int[] nums, int lo, int hi) {
// 每次交换后， 都还是以p为中心点
int p=nums[lo];
while(lo<hi) {
while(lo<hi && p<=nums[hi]) hi--;
nums[lo]=nums[hi];
// lo++; // 这里会导致数组为2时错误交换
while(lo<hi && p>=nums[lo]) lo++;
nums[hi]=nums[lo];
}
nums[lo]=p;
return lo;
}
// 空间换时间
private static void sortA(int[] nums) {
Map<Integer, Integer> cs = new HashMap<>();
for (int i : nums) {
cs.put(i, cs.getOrDefault(i, 0) + 1);
}
int p = 0;
for (Map.Entry<Integer, Integer> entry : cs.entrySet()) {
Integer k = entry.getKey();
Integer v = entry.getValue();
for (int i = 0; i < v; i++) {
nums[p++] = k;
}
}
}
// 三色排序的特色，只需要2个标识能代表三色
// 中等值排在最前方，最小值每次出现都和中等值交换位置
// 最大值每次出现，都和最后k位交换位置
private void quickB(int []nums) {
// j 代表 1 开始的位置
// k 代表 2 开始的位置
int j=0, k=nums.length;
for(int i=0; i<k; i++) {
if(nums[i]==0) {
swap(nums, i, j++);
} else if(nums[i] == 2) {
swap(nums, i--, --k);
}
}
}
