快排算法

• 按照某个条件，把数据分成三段；例如【正数、负数、零】或者【小于2、等于2、大于2】；
• 进一步来讲，也就是快排的一次partition找基准的过程；以中间的作为基准，例如负数、等于2作为基准

class Solution {
    public void sortColors(int[] nums) {
        
        int left = 0, i = left, right = nums.length - 1;
        while(right >= i){
            if(nums[i] == 0){
                swap(nums, i++, left++);
            }else if(nums[i] == 2){
                swap(nums, i, right--);
            }else{
                i++;
            }
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

美团一面算法：

package com.hshuo;

import java.util.Arrays;

import static com.hshuo.QuickSort.swap;

/**
 * @author SHshuo
 * @data 2022/4/4--8:56
 */
public class Partition {
    public static void main(String[] args) {
//        荷兰国旗问题、根据某个数进行分三段

        int[] res = new int[]{0, 0, -1, -4, -2, 3, 6, 4, 7};

        int left = 0, i = left, right = res.length - 1;
        while(i <= right){
            if(res[i] > 0){
                swap(i++, left++, res);
            }else if(res[i] == 0){
                swap(i, right--, res);
            }else{
                i++;
            }
        }
        System.out.println(Arrays.toString(res));

    }
}

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0, i = left, right = nums.length - 1;
        while(i <= right){
            if(nums[i] % 2 == 0){
                swap(i, right--, nums);
            }else{
                swap(i++, left++, nums);
            }
        }

        return nums;
    }

    public void swap(int left, int right, int[] nums){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

解决TopK问题：

• 剑指offer40，最小的k个数
• 思路：partition的思路，在过程中return；而不是所有数据都排序完毕

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length <= k){
            return arr;
        }
        int[] res = new int[k];
        partition(arr, 0, arr.length - 1, k);

        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    public void partition(int[] arr, int left, int right, int k){
        int index = getIndex(arr, left, right);
        if(index == k){
            return;
        }else if(index < k){
            partition(arr, index + 1, right, k);
        } else{
            partition(arr, left, index - 1, k);
        }
    }

    public int getIndex(int[] arr, int left, int right){
        int pivot = left;
        int index = pivot + 1;
        for(int i = index; i <= right; i++){
            if(arr[i] < arr[pivot]){
                swap(arr, i, index);
                index++;
            }
        }

        swap(arr, pivot, index - 1);
        return index - 1;
    }

    public void swap(int[] arr, int left, int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

class Solution {
    public String minNumber(int[] nums) {
        int len = nums.length, index = 0;
        String[] res = new String[len];
        for(int i : nums){
            res[index++] = String.valueOf(i);
        }
        quickSort(res, 0, len - 1);

        StringBuffer buffer = new StringBuffer();
        for(String i : res){
            buffer.append(i);
        }
        return buffer.toString();
    }

    public void quickSort(String[] res, int left, int right){
        if(right >= left){
            int index = getIndex(res, left, right);
            quickSort(res, left, index - 1);
            quickSort(res, index + 1, right);
        }
    }

    public int getIndex(String[] res, int left, int right){
        int pivot = left;
        int index = pivot + 1;
        for(int i = index; i <= right; i++){
            if((res[i] + res[pivot]).compareTo(res[pivot] + res[i]) < 0){
                swap(res, i, index);
                index++;
            }
        }

        swap(res, index - 1, pivot);
        return index - 1;
    }

    public void swap(String[] res, int left, int right){
        String temp = res[left];
        res[left] = res[right];
        res[right] = temp;
    }
}

快排的最坏时间复杂度的情况？

• 数据本来就已经升序，按照pivot的方法，每次分区之后分区点都还在右边界;
• 这就产生了分区极度不均匀的情况，最后需要分n次区，每次分区平均要扫描n / 2个元素。所以时间复杂度就退化成了O（n ^ 2）
• 也就是递归的过程原本是树的形式，退化到了链表
• 参考：https://www.cnblogs.com/FengZeng666/p/13944309.html

如何实现快排的优化？

• 当待排序序列长度分割到一定大小后，使用插入排序；对于很小和部分有序的数据，快排不如插排（有序的时候插入时间复杂度会变为O(n)）好。所以可以使用插排替换快排；
• 在一次分割结束后，可以把与基准pivot相等的元素聚在一起，继续下次分割时，不用再对与pivot相等元素分割（处理）；
• 随机选取数组中的元素作为基准，使算法成为等概率事件，也就是快排3.0的优化。

• 将找基准的过程不在原数组进行修改，而是另外申请一段空间B，在原来的数据空间A中，选取第一个元素pivot作为基准；
• 首先遍历空间A，将所有小于pivot基准的元素依次放到空间B中，然后将pivot放入B中；
• 再次遍历空间B，将所有大于等于pivot基准的元素依次放入空间B中；
• 最后重新将空间B的数据全部拷贝到空间A中。