跳至主要內容

快速排序以及荷兰国旗问题

牧歌2025/4/16...大约 6 分钟algorithm荷兰国旗问题快排

快速排序以及荷兰国旗问题

荷兰国旗问题

荷兰国旗问题分为了两种：

  1. 给定一个数 num ，将数组中小于等于这个数的放左边，大于这个数据放右边。
  2. 给定要给数 num ，将数组中小于这个数据放左边，等于这个数的放中间，大于这个数的放右边。好似荷兰国旗样分成 3 部分，称之为荷兰国旗问题。

第二种是第一种的升级版，可以注意到只要求大小没有要求顺序，因此只考虑 2 个数的比较即可，不用全局考虑。

第一种

第一种种问题实现思路：
引入一个变量 left 标记 小于 num 数组 右边界，从 0 开始。
引入一个变量i，i从左到右，循环遍历数组

操作

  1. 当 i 处的数值 <= num 则与 left 上的位置交换， 小于 num 数组右边界 left++ 和 i++
  2. 当 i 处的数值 > num 则 i++
package learn.note.algorithm.sort.three.fastextension;

import java.util.Arrays;

/**
 * 荷兰国旗问题，第一版本：
 * 给定一个数组，将数组分为两个区域，小于等于区域等于，大于区域
 * @author Wang WenLei
 * @date 2025/8/14 9:40
 * @since 1.0
 */
public class NetherlandsNationalFlag1 {
    public static void main(String[] args) {
        int[] list = new int[] {1,8,5,9,7,2,5,6,3,4};
        dispose(list, 5);
        Arrays.stream(list).forEach(System.out::print);
    }

    private static void dispose(int[] list, int num) {
        int left = 0;
        int i = 0;
        while (i < list.length) {
            if (list[i] <= num) {
                // 换位置
                swap(list, left++, i++);
            } else {
                i++;
            }
        }
    }

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

执行结果：这个执行结果让我疑惑了一下，34 并没有在 5 的左边是不是错了？并没有小于这个数的确实都在左边，只分界线在从零起的第 5 个数后。

1525349678

第二种

package learn.note.algorithm.sort.three.fastextension;

import java.util.Arrays;

/**
 * 荷兰国旗问题，给定一个数组、给定一个数，将数据分为三个部分，小于这个数在数组左边、等于这个数在中间、大于这个数在右边
 * @author Wang WenLei
 * @date 2025/8/14 17:47
 * @since 1.0
 */
public class NetherlandsNationalFlag2 {
    public static void main(String[] args) {
        int[] list = new int[] {1,8,5,9,7,2,5,6,3,4};
        dispose(list, 5);
        Arrays.stream(list).forEach(System.out::print);
    }

    private static void dispose(int[] list, int num) {
        int left = -1;
        int right = list.length;
        int i = 0;
        while (i < right) {
            if (list[i] < num) {
                swap(list, i++, ++left);
            } else if (list[i] == num) {
                i++;
            } else {
                swap(list, i, --right);
            }
        }
    }

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

执行结果：完美

1432556798

快速排序

给我的感觉是每次找到的一个数在这个数组中的应该位置，当每个数都找到自己的位置就排序完成了，很奇妙

基于荷兰国旗第一种方法编写快排，一次搞定一个数


import java.util.Arrays;

/**
 * @author Wang WenLei
 * @date 2025/8/13 17:28
 * @since 1.0
 */
public class FastSort {
    public static void main(String[] args) {
        int[] list = new int[] {5,2,1,6,7,1,6,87,12,5,2,6,89};
        fastSort(list);
        Arrays.stream(list).forEach(System.out::println);
        // 对数器
        CompareMachineUtil.compare(FastSort::fastSort, null);
    }

    private static void fastSort(int[] list) {
        disposeSort(list, 0, list.length - 1);
    }

    private static void disposeSort(int[] list, int low, int high) {
        if (low >= high) {
            return;
        }
        int left = low -1;
        int i = low;
        // 从数组中随机取一个位置与最后要给数交换，来做到随机
        swap(list, ((int)(Math.random() * (high - low + 1)) + low), high);
        // 取最后一个值，low 到 high - 1 做荷兰国旗分两个区域，得到一个位置
        int num = list[high];
        while (i < high) {
            int cur = list[i];
            if (cur <= num) {
                swap(list, ++left, i++);
            } else {
                i++;
            }
         }
        // 取出的 num 与 left 后面的的第一个交换
        swap(list, high, left+1);

        // 一次搞定数
        disposeSort(list, low, left);
        disposeSort(list, left + 2, high);
    }

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

基于荷兰国旗第二种方法编写快排，一次搞定一批相等的数

import java.util.Arrays;

public class FastSort {
    public static void main(String[] args) {
        int[] list = new int[] {5,2,1,6,7,1,6,87,12,5,2,6,89};
        fastSort(list);
        Arrays.stream(list).forEach(System.out::println);
        // 对数器
        CompareMachineUtil.compare(FastSort::fastSort, null);
    }

    private static void fastSort(int[] list) {
        disposeSort(list, 0, list.length - 1);
    }

    private static void disposeSort(int[] list, int low, int high) {
        if (low >= high) {
            return;
        }
        // 取一个值，low 到 high - 1 做荷兰国旗，得到区间
        int left = low -1;
        int right = high;
        int i = low;
        int num = list[high];
        while (i < right) {
            int cur = list[i];
            if (cur < num) {
                swap(list, ++left, i++);
            } else if (cur == num) {
                i++;
            } else {
                swap(list, --right, i);
            }
         }
        // 取出的 num 与 right 的第一个交换
        swap(list, high, right);
        
        // 一次搞定一批相等的数
        disposeSort(list, low, left);
        disposeSort(list, right, high);
    }

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

得到结果

1
1
2
2
5
5
6
6
6
7
12
87
89
恭喜对数正确

对数器详情

快排加随机取值

上面算法快排最差情况是 O(n2)O(n^2) ，每次递归分组都在边上，每次进入下次递归几乎要重新遍历。
如果每次递归都差不多在中间分成两组，效率就会变高。随机选一个数，与最后一个位置交换，然后进行排序。好情况和差情况是随机的，根据概率累计、长期期望后得到时间复杂度O(nlogn)O(nlog^n)

Java基础#随机数的使用 

import java.util.Arrays;

public class FastSort {
    public static void main(String[] args) {
        int[] list = new int[] {5,2,1,6,7,1,6,87,12,5,2,6,89};
        fastSort(list);
        Arrays.stream(list).forEach(System.out::println);
        // 对数器
        CompareMachineUtil.compare(FastSort::fastSort, null);
    }

    private static void fastSort(int[] list) {
        disposeSort(list, 0, list.length - 1);
    }

    private static void disposeSort(int[] list, int low, int high) {
        if (low >= high) {
            return;
        }
        int left = low -1;
        int right = high;
        int i = low;
        // 从数组中随机取一个位置与最后要给数交换，来做到随机
        swap(list, ((int)(Math.random() * (high - low + 1)) + low), high);
        // 取最后一个值，low 到 high - 1 做荷兰国旗，得到区间
        int num = list[high];
        while (i < right) {
            int cur = list[i];
            if (cur < num) {
                swap(list, ++left, i++);
            } else if (cur == num) {
                i++;
            } else {
                swap(list, --right, i);
            }
         }
        // 取出的 num 与 right 的第一个交换
        swap(list, high, right);

        // 一次搞定一批相等的数
        disposeSort(list, low, left);
        disposeSort(list, right, high);
    }

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

其他写法

几年前，在博客上曾经画过，快排的分步骤图例，起名 “史上最详细图解快速排序” 惭愧，当时轻狂了，哈哈哈。

原理写在我的博客：# 史上最详细图解快速排序

import java.util.Arrays;

public class FastSort {
    public static void main(String[] args) {
        int[] list = new int[] {5,2,1,6,7,1,6,87,12,5,2,6,89};
        fastSort(list);
        Arrays.stream(list).forEach(System.out::println);
        // 对数器
        CompareMachineUtil.compare(FastSort::fastSort, null);
    }

    private static void fastSort(int[] list) {
        fastSort(list, 0, list.length - 1);
    }

    public static void fastSort(int [] data,int low,int high){
        if(low >= high){
            return;
        }
        // 从数组中随机取一个位置与最后要给数交换，来做到随机
        swap(data, ((int)(Math.random() * (high - low + 1)) + low), low);
        int pivot = data[low];
        int i = low;
        int j = high;
        while(i < j){
            // 因为 要 想左移动j，直到data[j] < pivot
            while(i < j && pivot < data[j]){
                j -- ;
            }
            if(i < j){
                data [i] = data[j];
                i++;
            }
            while(i < j && pivot > data[i]){
                i ++ ;
            }
            // 下面的if在第一次编写时丢了，导致少了一部分逻辑
            if(i < j){
                data [j] = data[i];
                j--;
            }
        }
        data[i] = pivot;
        fastSort(data,low,--i);
        // 这里第一次编写时错误的使用了 ++i，现在改成了++j。错误原因i在上面已经被减过了
        fastSort(data,++j,high);
    }
}

完~

最近更新
贡献者: wenleiwang