算法从小白到大神之荷兰国旗问题&快排&堆排

题目一：

给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
问题二（荷兰国旗问题）
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

/**
 * 问题:（荷兰国旗问题）
 * 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 */
public class NetherLandsFlag {
    public static int[] partition(int [] arr,int L,int R,int num){
        int less=L-1;
        int more=R+1;
        int cur=L;
        while (cur<more){
            if (arr[cur]<num){
                swap(arr,++less,cur++);
            }else if(arr[cur]>num){
                swap(arr,--more,cur);
            }else {
                cur++;
            }
        }
        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }
    public static int [] generateArray(){
        int [] arr=new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=(int)(Math.random()*3);
        }
        return arr;

    }

    public static void main(String[] args) {
        int [] arr=generateArray();
        int[] res=partition(arr,0,arr.length-1,2);
        System.out.println(Arrays.toString(res));
    }
}

题目二：

随机快速排序的细节和复杂度分析
可以用荷兰国旗问题来改进快速排序
时间复杂度O(N*logN)，额外空间复杂度O(logN)

/**
 * 快排
 */
public class QuickSort {
    public static void quickSort(int [] arr){
        if (arr==null || arr.length<2){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }

    private static void quickSort(int[] arr, int L, int R) {
        if (L<R){
            int [] p=partition(arr,L,R);
            quickSort(arr,L,p[0]-1);
            quickSort(arr,p[1]+1,R);
        }
    }

    private static int[] partition(int[] arr, int L, int R) {
        int less=L-1;
        int more=R;
        int cur=L;
        while (cur<more){
            if (arr[cur] < arr[R]) {
                swap(arr,++less,cur++);
            }else if(arr[cur]> arr[R]){
                swap(arr,--more,cur);
            }else {
                cur++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int [] arr={12,10,4,10,10,8,9,10};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

题目三
堆排序的细节和复杂度分析
时间复杂度O(N*logN)，额外空间复杂度O(1)
堆结构非常重要

1，堆结构的heapInsert与heapify

2，堆结构的增大和减少

3，如果只是建立堆的过程，时间复杂度为O(N)

4，优先级队列结构，就是堆结构

/**
 *  堆排
 */
public class HeapSort {
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int []arr={1,34,4,5,76,8,9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

有关排序问题的补充：

1，归并排序的额外空间复杂度可以变成O(1)，但是非常难，不 需要掌握，可以搜“归并排序 内部缓存法”

2，快速排序可以做到稳定性问题，但是非常难，不需要掌握， 可以搜“01 stable sort”

3，有一道题目，是奇数放在数组左边，偶数放在数组右边，还 要求原始的相对次序不变，碰到这个问题，可以怼面试官。面试官非良人。

参考：牛客算法进阶