蓝桥 第三周 分治 排序

3.1 分治法介绍及关键点解析_哔哩哔哩_bilibili

分治：分解 解决 合并

快速排序

        单向扫描分区法

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {1,6,3,6,2,8,6,1,0,7};
		quickSort1(arr,0,arr.length-1);
		for(int i:arr) {
			System.out.println(i);
		}
	}
	public static void quickSort1(int[] arr,int idx1,int idx2) {
		if(idx1<idx2) {
			int q = partition(arr,idx1,idx2);
			quickSort1(arr,idx1,q-1);
			quickSort1(arr,q+1,idx2);
		}	
	}
	public static int partition(int[] arr,int idx1,int idx2) {
		int pivot = arr[idx1];
		int l = idx1+1;
		int r = idx2;
		int temp;
		while(l<=r) {
			if(arr[l]<pivot)l++;
			else{
				temp = arr[l];
				arr[l]=arr[r];
				arr[r]=temp;
				r--;
			}			
		}
		temp = arr[idx1];
		arr[idx1] = arr[r];
		arr[r] = temp;
		return r;
	}

        双向扫描分区法

public static int partition2(int[] arr,int idx1,int idx2) {
		int pivot = arr[idx1];
		int l = idx1+1;
		int r = idx2;
		int temp;
		while(l<=r) {
			while(l<=r&&arr[l]<=pivot)l++;
			while(l<=r&&arr[r]>pivot)r--;
			if(l<r) {
				temp = arr[l];
				arr[l] = arr[r];
				arr[r] = temp;
			}			
		}
		temp = arr[idx1];
		arr[idx1] = arr[r];
		arr[r] = temp;
		return r;
	}

快速排序的优化

        三点中值法 （在p r mid之间，选一个中间值作为pivot）

        绝对中值法

        待排序列表较短时，用插入排序

归并排序 Merge Sort

public class Solution3_1 {
    private static int[] helper;
    public static void main(String[] args) {
        int[] arr = {10,2,7,3,19,11,1,6,8,4,13};
        sort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    public static void sort(int[] arr){
        helper = new int[arr.length];
        mergeSort(arr,0,arr.length-1);
    }
    private static void mergeSort(int[] arr,int low, int high){
        if(low<high){
            int mid = low + ((high - low)>>1);
            mergeSort(arr,low,mid);
            mergeSort(arr,mid+1,high);
            merge(arr,low,mid,high);
        }
    }
    public static void merge(int[] arr, int low,int mid,int high){
        System.arraycopy(arr,low,helper,low,high-low+1);
        int left = low,right = mid +1;
        int cur = low;
        while(left<=mid&&right<=high){
            if(helper[left]<=helper[right]){
                arr[cur++]=helper[left++];
            }else{
                arr[cur++]=helper[right++];
            }
        }
        while(left<=mid){
            arr[cur++]=helper[left++];
        }
    }
}

题1：调整数组顺序使奇数位于偶数前面（O(n)）

public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7,8,9,10};
        int[] helper = new int[arr.length];
        System.arraycopy(arr,0,helper,0,arr.length-1);
        int p=0;
        for(int i=0;i<arr.length;i++){
            if(helper[i]%2==1){
                arr[p++]=helper[i];
            }
        }
        for(int i=0;i<arr.length;i++){
            if(helper[i]%2==0){
                arr[p++]=helper[i];
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }

  题2：第k个元素（第k大的元素）

public class Solution3_3 {
    public static void main(String[] args) {
        int[] arr = {1,5,2,4,3,6,9,8,7};
        int k = 7;
        System.out.println(getK(arr,k,0,arr.length-1));

    }
    public static int getK(int[] arr,int k,int idx1,int idx2){
        int q = partition(arr,idx1,idx2);
        int qK = q-idx1+1;//pivot是第几个元素
        if(qK==k) {
            return arr[q];
        }else if(qK>k){
            return getK(arr,k,idx1,q-1);
        }else{
            return getK(arr,k-qK,q+1,idx2);
        }
    }
    public static int partition(int[] arr,int idx1,int idx2){
        int pivot = arr[idx1];
        int l = idx1+1;
        int r = idx2;
        int temp;
        while(l<=r) {
            while(l<=r&&arr[l]<=pivot)l++;
            while(l<=r&&arr[r]>pivot)r--;
            if(l<r) {
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        temp = arr[idx1];
        arr[idx1] = arr[r];
        arr[r] = temp;
        return r;
    }
}

题3：超过一半的数字

        排序后位置在下标n/2的元素

public static void main(String[] args) {
        int[] arr = {6,7,7,7,8,8,8,8,8,8};
        Arrays.sort(arr);
        System.out.println(arr[arr.length/2]);
    }

题3扩展：寻找发帖水王

public static int getCandidate(int[] arr){
        int candidate = arr[0];
        int nTimes = 1;
        for(int i=0;i<arr.length;i++){
            if(nTimes==0){
                candidate = arr[i];
                nTimes = 1;
                continue;
            }
            if(arr[i]==candidate){
                nTimes++;
            }else{
                nTimes--;
            }
        }
        return candidate;
    }

  题4：最小可用id

public class Solution3_5 {
    public static void main(String[] args) {
        int[] arr = {10,2,3,4,6,7,8,1};
        System.out.println(getMinId(arr,0,arr.length-1));
    }
    public static int getMinId(int[] arr,int low,int high){
        if(low>=high)return Math.max(low,high)+1;
        int q = partition(arr,low,high);
        if(arr[q]==q+1){
            return getMinId(arr,q+1,high);
        }else{
            return getMinId(arr,low,q);
        }
    }
    public static int partition(int[] arr,int low,int high){
        int pivot = arr[low];
        int l = low+1;
        int r = high;
        int temp;
        while(l<=r){
            if(arr[l]<pivot){
                l++;
            }else{
                temp = arr[l];
                arr[l] = arr[r];
                arr[r--] = temp;
            }
        }
        temp = arr[low];
        arr[low] = arr[r];
        arr[r] = temp;
        return r;
    }
}

题5：合并有序数组

题6：逆序对个数

树和二叉树

        树的遍历 先序遍历 中序遍历 后序遍历

        数组的先序遍历

    public static void preOrder(int[] arr,int i){
        if(i>=arr.length){
            return;
        }
        System.out.println(arr[i]);
        preOrder(arr,i*2+1);
        preOrder(arr,i*2+2);
    }

堆 

        完全二叉树 近似完全二叉树

        大顶堆 小顶堆

堆排序

        堆化 反向调整使得每个子树都是大顶堆或者小顶堆

        按序输出元素 把堆顶和最末元素对调 然后调整堆顶元素

计数排序

        用辅助数组对数组中出现的数字计数 元素转下标 下标转元素