荷兰国旗问题与快速排序

荷兰国旗问题

即以最后一个元素进行划分，将一组数据分成三个区域，分别是小于区、等于区、大于区
时间复杂度为：O(N)

• less 用来记录小于最后一个元素的右下标，初始值为L-1，代表目前在划分区域内没有。
• more 用来记录大于最后一个元素的左下标，初始值为R，认为最后一个在大于区内。（最后再将最后一个元素与最大区的做元素与其交换）
  • if arr[L] > arr[R] ，交换arr[++less] 和 arr[L++] 的值
  • if arr[L] < arr[R] ，交换 arr[--more] 和 arr[L] 的值
  • if arr[L] < arr[R] ，不交换，L++，直接遍历下一个值
  • 当 L >= more 时，退出循环。

Java代码实现

    public static void partition(int[] arr,int L,int R) {
        int less = L-1;
        int more = R;
        while(L < more) {
            if(arr[L] < arr[R]) {
                swap(arr, ++less, L++);
            }else if(arr[L] > arr[R]) {
                swap(arr,--more,L);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
    }
    
    public static void swap(int[] arr,int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

快速排序

快速排序即是荷兰国旗的一个延申，进行递归调用

• 即是将划分的小于区与大于区分别再进行划分
• 分别记录下来最小区的最右元素与最大区的最左元素
• 将记录下的元素分别作为两个荷兰国旗的 R 和 L
• 每个子划分直到只剩一个元素时停止划分（L < R）

Java代码实现

    public static void quickSort(int[] arr, int L, int R) {
        if(L < R) {
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0]-1);
            quickSort(arr, p[1] + 1, R);
        }
    }
    
    public static int[] partition(int[] arr,int L,int R) {
        int less = L-1;
        int more = R;
        while(L < more) {
            if(arr[L] < arr[R]) {
                swap(arr, ++less, L++);
            }else if(arr[L] > arr[R]) {
                swap(arr,--more,L);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1, more};
    }
    
    public static void swap(int[] arr,int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }