算法

本文最后更新于：2024年1月27日 晚上

[TOC]

蓝桥杯

异或

题2 找出落单的数

一个数组里除了某一个数字外，其他数字都出现了两次，请找出这个数字。

很简单，使用异或思路。

对数组里所有的值进行异或，根据异或相同为0、不同为1的性质可知，所有出现了两次的值异或后值都变为0，而落单的数与0异或等于他自身。

题3 二进制中1的个数

实现一个函数，输入一个整数，输出该数二进制表示中1的个数

例如：9的二进制为1001，有2个1

基本思路：

将1左移i位然后再和num做&操作，此时，这个1左移后会出现100…的形式，与num &后，如果num转为二进制对应位为1，那么就会与 n<<i 相等，否则不相等

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    System.out.println(Integer.toString(num,2));    // 转成2进制输出
    int n = 1,count=0;
    for(int i=0;i<32;i++) {
        if((num&(n<<i)) == n<<i) {
            count++;
        }
    }
    System.out.println(count);
}

题4 判断某个整数是否为2的整数次方

一条语句判断某个整数是否为2的整数次方

很简单，转为二进制，然后采用异或的思路

如果一个数为2的整数次方，那么转为2进制肯定只有一个1，其余都是0。

那么我们只需要将数N-1(二进制原来的1后面出现多个1，那一位变为0)与N做异或操作，那么就会为0

16的二进制为 1000，

减一变为 0111

所以异或就会为0

1
2
3
4
5
6
7
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
if(((N-1)&N) == 0) {
    System.out.println("是2的整数次方");
}else {
    System.out.println("不是");
}

题5 将整数的奇偶位互换

将整数的二进制上的奇偶位互换

如：9的二进制1001 互换为 0110

很简单，使用变量ou获得二进制偶数位上的数，0xaaaaaaaa表示32位二进制偶数位上为1，那么与num与操作后获得偶数位的数

同理，ji变量获得二进制奇数位

然后我们将奇数位左移1位，偶数位右移1位，再或操作，就得到正确结果了，很妙

1
2
3
4
5
6
7
public static void main(String[] args) {
    int num = 9;
    int ou = num&0xaaaaaaaa;
    int ji = num&0x55555555;
    int n = (ou>>1) | (ji<<1);
    System.out.println(n);	// 输出6
}

题6 0~1之间浮点实数的二进制表示

给定一个0到1之间的实数 (如：0.625)，类型为double，打印它的二进制表示(0.101)

如果该数字无法精确用32位以内的二进制精确表示，则打印ERROR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double num = 0.3;
StringBuilder sb = new StringBuilder("0.");
while(num > 0) {
    num *= 2;
    if (num >= 1) {
        sb.append("1");
        num -= 1;
    }else {
        sb.append("0");
    }
    if(sb.length()>34) {
        System.out.println("ERROR");
        return;
    }
}
System.out.println(sb);

递归

汉诺塔

给定三根柱子，记为 A、B、C ，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。

移动时应注意：① 一次只能移动一个盘子 ②大的盘子不能压在小盘子上

问：将 A 柱上的盘子经由 B 柱移动到 C 柱最少需要多少次？

image-20240117204239287

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class 汉诺塔 {
    public static void main(String[] args) {
        hnt(3,"A","B","C");
    }

    public static void hnt(int n,String from,String to,String help) {
        if(n==1) { // 只有一个盘子直接移动即可
            System.out.println("move "+n +" from "+from+" to "+to);
            return;
        }
        hnt(n-1,from,help,to); // 先将n-1个盘子移动到help
        System.out.println("move "+n +" from "+from+" to "+to); // 移动第n个盘子到to
        hnt(n-1,help,to,from); // 将n-1个盘子移动到to
    }
}

快速幂

P1226 快速幂

image-20240123120757111

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;

public class P1226快速幂 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(),b = sc.nextLong(),p = sc.nextLong();
        System.out.printf("%d^%d mod %d=%d",a,b,p,fastPow(a,b,p));
    }

    public static long fastPow(long a,long b,long p) {
        long ans = 1,base;
        a = a % p;
        base = a;
        while(b > 0) {
            if ((b&1) == 1) {
                ans *= base;
                ans %= p;
            }
            base *= base;
            base %= p;
            b >>= 1;
        }
        return ans;
    }
}

月份API

P5716 月份天数

题目描述

输入年份和月份，输出这一年的这一月有多少天。需要考虑闰年。

输入格式

输入两个正整数，分别表示年份 y 和月数 m，以空格隔开。

输出格式

输出一行一个正整数，表示这个月有多少天。

Calendar

1
2
3
4
5
6
7
public static void calendar(int y , int m) {
    Calendar calendar = Calendar.getInstance();
    calendar.set(Calendar.YEAR,y);
    calendar.set(Calendar.MONTH,m-1);
    calendar.set(Calendar.DAY_OF_MONTH,1);
    System.out.println(calendar.getActualMaximum(Calendar.DAY_OF_MONTH));
}

LocalDate

1
2
3
public static void localDate(int y , int m) {
    System.out.println(LocalDate.of(y,m,1).lengthOfMonth());
}

辗转相除法求最大公因数

1
2
3
public static long gcd(long a,long b) {
    return b!=0 ? gcd(b,a%b): a;
}

马士兵-左程云

1.认识复杂度和简单排序算法

认识时间复杂度

image-20240126133404224

排序

选择排序

时间复杂度 O(N^2) 不稳定排序

在0~N-1范围内找一个最小的值，放到0位置；

在1~N-1范围内找一个最小的值，放到1位置；

…

一直重复到结束

（每次过一遍范围都找到最小的，然后放到范围内的首位置）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 public static void selectSort(int[] arr) {
     if (arr == null || arr.length < 2) {
         return;
     }
     int minIndex;
     for (int i = 0; i < arr.length - 1; i++) {
         minIndex = i;
         for (int j = i+1; j < arr.length ; j++) {
             minIndex = arr[j]<arr[minIndex] ? j:minIndex;
         }
         swap(arr,minIndex,i);
     }
 }

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

冒泡排序

时间复杂度 O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = arr.length-1; i > 0 ; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j]>arr[j+1]) {
                swap(arr,j,j+1);
            }
        }
    }
}
public static void swap(int[] arr,int i,int j) {
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

异或

异或性质

1）0^N == N N^N == 0

2）异或运算满足交换律和结合率

两数交换

利用异或的性质：相同为0，不同为1

交换两个数

(如果使用在数组中，注意不要让数组下标相等，否则可能变成0，就覆盖了)

1
2
3
a = a^b;
b = a^b;
a = a^b;

原理

假设 a=甲 b=乙

  1. a = 甲^乙 b = 乙
  2. a = 甲^乙 b = 甲^乙^乙=甲
  3. a = 甲^乙^甲 = 乙 b = 甲

此时已经完成交换了

找出一组偶次出现数中的一个数

image-20240126143130768

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数

根据异或的性质，

相同为0、不同为1，交换律，结合律

0^N=N

a^b=b^a

只要用一个0与该组数中全部异或即可，这样所有偶次出现的数全部变为0了，只留下这个奇次出现的数

1
2
3
4
5
6
7
public static int problem1(int[] arr) {
    int eor=0;
    for (int n: arr) {
        eor ^= n;
    }
    return eor;
}

找出一组偶次出现的数中的两个互不相等的奇次数

一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数

首先会想到使用异或，假设这两个数为a、b

当eor=0，对一组数异或后会得到a^b的值，但是这并不能获得单独的值

因为这两个数不相等，所以二进制对应某一bit位必然不相等(假设第8bit位不相等)

那么这一组数arr可根据对应二进制位为 0、1 分为两组

A组：该二进制位为1

B组：该二进制位为0

如果我们对A组进行异或，那么偶次出现的数全会变为0，不影响，此时只剩奇数次出现的a或b了

假如剩余eor1=a

那么b=eor^eor1=a^b^a=b

但是如何求出该bit有点问题，我们需要用到补码的思想

~eor+1 这样再和eor作&与操作，就拿到最右边的1了

image-20240126151507076

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void problem2(int[] arr) {
    int eor = 0;
    for (int n: arr) {
        eor ^= n;
    }
    int eor1=0;
    int rightOne = eor&(~eor+1); // 提取bit最右侧的1
    for (int n: arr) {
        if ((n&rightOne)!=0) { 
            eor1 ^= n;
        }
    }
    System.out.println(eor1+" "+(eor^eor1));
}

(n&rightOne)!=0这一句就是让这组数中都与rightOne与操作，判断对应bit是否为1, !=0就是bit为1.等价(n&rightOne)==rightOne 、(n&rightOne)==0

二分法

在一个有序数组中，找某个数是否存在

时间复杂度 O(logN)

在一个有序数组中，找某个数是否存在，并返回下标

需要一个有序数组：int[] arr = new int[]{1,1,2,3,3,3,3,4};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int search(int[] arr,int target) {
    int left,right,mid;
    left = 0;
    right = arr.length-1;
    while(left<=right) {
        mid = (left+right) >> 1;
        if (arr[mid]==target) {
            return mid;
        } else if (arr[mid]>target) {
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    return -1;
}

在一个有序数组中，找>=某个数最左侧的位置

image-20240126155703335

假如我们需要找到这个有序数组中最左侧的3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int search2(int[] arr,int target) {
    int left,right,mid,pos;
    left = 0;
    right = arr.length - 1;
    pos = arr.length;
    while(left<=right) {
        mid = (left+right) >> 1;
        if (arr[mid]>=target) {
            if (mid<pos) {
                pos = mid;
            }
            right = mid - 1;
        }else {
            left = mid + 1;
        }

    }
    if (pos==arr.length) {
        return -1;
    }
    return pos;
}

局部最小值问题

假设一个无序数组arr，如何求其中一个局部最小值？

arr[0]<arr[1] 局部最小值就是arr[0]

arr[length-1]<arr[length-2] 局部最小值就是arr[length-1]

arr[i]<arr[i-1] && arr[i]<arr[i+1] 局部最小值就是arr[i]

之前我们只会在有序数组中用二分法查找值，但是这题无序数组也可以使用二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int getAreaMin(int[] arr) {
    if (arr == null) {
        return -1;
    }
    if (arr.length == 1) {
        return arr[0];
    }
    //第一个元素如果比第二个要小，因为左边没有数，所以第一个元素就是一个局部最小数。
    if (arr[0]<arr[1]) {
        return arr[0];
    }
    //数组最后一个元素如果比倒数第二个元素值要小，说明最后一个元素也是一个局部最小数。
    if (arr[arr.length-1]<arr[arr.length-2]) {
        return arr[arr.length-1];
    }
    int left,right,mid;
    left = 1;
    right = arr.length - 2;

    while(left<=right) {
        mid = (left+right) >> 1;
        if (arr[mid]>arr[mid-1]) {
            right = mid - 1;
        }else if (arr[mid]>arr[mid+1]) {
            left = mid + 1;
        }else {
            return arr[mid];	// 小于左右两边
        }
    }
    return -1;
}

对数器的概念和使用

1，有一个你想要测的方法a

2，实现一个复杂度不好但是容易实现的方法b

3，实现一个随机样本产生器

4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。

5，如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b

6，当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

对数器其实就是用来测试方法是否正确的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.util.Arrays;

public class Code01_SelectionSort {

    // 选择排序方法
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // 如果数组为空或长度小于2，无需排序
        }
        // 外层循环遍历数组
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i; // 假设当前位置为最小值的索引
            // 内层循环找到最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex; // 更新最小值的索引
            }
            swap(arr, i, minIndex); // 将最小值与当前位置交换
        }
    }

    // 数组元素交换方法
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 用于测试的比较器方法
    public static void comparator(int[] arr) {
        Arrays.sort(arr); // 使用Java内置的排序方法对数组进行排序
    }

    // 生成随机数组的方法
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // 生成在 [-maxValue, maxValue] 范围内的随机整数
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // 复制数组的方法
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // 判断两个数组是否相等的方法
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 主函数，用于测试
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        // 随机生成数组进行测试
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            selectionSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "排序正确!" : "排序错误!");

        // 随机生成数组并打印排序前后的结果
        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        selectionSort(arr);
        printArray(arr);
    }
}

2.认识O(NlogN)的排序

master公式的使用

Master公式用来较为简便地评估递归算法的时间复杂度

（自由子问题分成相同的大小才能使用master公式求时间复杂度）
$$
T(N)=a\cdot T(\frac{N}{b}) + O(N^d)
$$

  1. log(b,a) > d -> 时间复杂度为O(N^log(b,a))

  2. log(b,a) = d -> 时间复杂度为O(N^d * logN)

  3. log(b,a) < d -> 时间复杂度为O(N^d)

a：生成的子问题数（比如二叉树的递归遍历就是 a = 2)
b：表示每次递归是母问题的1/b的数据规模
N：母问题的数据规模
d：额外操作的次数

注：使用Master公式分析递归问题时间复杂度时，各子问题的数据规模应该是一致的，否则不能使用Master公式。

如何使用递归找数组中的最大值？

1
2
3
4
5
6
7
8
9
10
public static int getArrMax(int[] arr, int L, int R) {
    if (L == R) {
        return arr[L];
    }
    int mid;
    mid = L + ((R - L) >> 1); // 右移1位效率高,防止整数溢出
    int leftMax = getArrMax(arr, L, mid);
    int rightMax = getArrMax(arr, mid + 1, R);
    return Math.max(leftMax, rightMax);
}

d(额外操作的次数)，除去两个递归，其他的操作时间复杂度为O(1)

这里使用master公式：T(N)=2*T(N/2)+O(N^0)

a=2,b=2,d=0.

所以log(b,a)=1>d=0. 时间复杂度O(N)

归并排序

归并排序就是一个递归，先左边排好序，然后右边排好序，最后左右设置双指针，让其整体有序

让其整体有序的过程里用了外排序方法

时间复杂度: O(N*logN) 空间复杂度: O(N)

归并排序思想很简单：

首先将一个数组分为两部分，递归，让左边半部分排好序，让右边半部分排好序，这时左右两部分分别排好序了。此时只需要使用merge函数使用双指针，让这两部分按序填入新创建的空间中，最后赋值给原数组即可

image-20240127200221069

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr,0,arr.length-1);
}
public static void mergeSort(int[] arr,int l,int r) {
    if (l == r) {
        return;
    }
    int mid;
    mid = l + ((r-l)>>1);
    mergeSort(arr,l,mid);
    mergeSort(arr,mid+1,r);
    merge(arr,l,mid,r);
}

public static void merge(int[] arr,int l,int mid,int r) {
    int[] help = new int[r-l+1];
    int i=0;
    int p1=l,p2=mid+1;
    while(p1<=mid&&p2<=r) { // 当两个数组指针都没有到末尾
        help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    }
    while(p1<=mid) {  // p2数组已经赋值完了，只要将p1后的部分全部填入即可
        help[i++] = arr[p1++];
    }
    while(p2<=r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length ; i++) {
        arr[l+i] = help[i];
    }

}

时间复杂度使用master公式计算: T(N)=2*T(N/2)+O(N)

此时log(b,a)=1=d，所以时间复杂度: O(N*logN)

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。

求一个数组 的小和。

例子: [1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、2; 所以小和为1+1+3+1+1+3+4+2=16

小和问题可以解释为：每一个数右边有几个比它大的数，如果有n个，小和就加上n*这个数的值

例如3的右边有4、5两个数更大，所以小和加上：3*2

所以总小和：4*1+3*2+4*1+2*1=16 结果一致

小和问题可以使用归并排序来解决，因为归并排序每一次其中的一部分都有序，归并的数组长度从一个元素开始逐个增加，一开始左边数组和右边数组进行大小比较，如果右边的元素大，那么小和就可加上 左边元素值*右边大于该元素的长度，排完序后原来右边的元素到左边了，不会重复叠加

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    return mergeSort(arr, 0, arr.length - 1);
}

public static int mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return 0;
    }
    int mid;
    mid = l + ((r - l) >> 1);
    return mergeSort(arr, l, mid) +
        mergeSort(arr, mid + 1, r) +
        merge(arr, l, mid, r);
}

public static int merge(int[] arr, int l, int mid, int r) {
    int sum = 0;
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l, p2 = mid + 1;
    while (p1 <= mid && p2 <= r) {
        // 关键代码
        sum += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
    return sum;
}

merge函数中有一行关键代码

1
sum += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;

如果arr[p1] < arr[p2] 就说明左边数组当前下标p1的元素小于右边数组p2及其后面的元素，那么我们最小和加上：arr[p1]*(r - p2 + 1) 乘以p2下标到右数组尾部长度共有多少个元素

image-20240127210741457

逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序 对

荷兰国旗问题

问题一

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

image-20240127213916962

假设我们取一个数组：[3,5,6,7,4,3,5,8]，我们需要把小于等于5的放在数组左边，大于5的放在数组右边

我们可以想象一个<=区,初始下标i=0

分为两种情况:

  1. arr[i]<=num此时arr[i]与<=区的下一个数交换，<=区右扩，i++
  2. arr[i]>num i++即可

这样一遍过后，当i到达数组边界时，此时数组元素已经按要求排列好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void problem1(int[] arr,int num) {
    int i=0,index=0; // index代表<=区的下一个下标
    while(i<arr.length) {
        if (arr[i]<=num) {
            swap(arr,index,i);
            index++;
            i++;
        }else {
            i++;
        }
    }
}
public static void swap(int[] arr,int i,int j) {
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

荷兰国旗问题

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

这个只是比上面的复杂一点，我们设置3个区<区 =区 >区

image-20240127220025575

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void swap(int[] arr,int i,int j) {
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static int[] partition(int[] arr,int l,int r,int num) {
    int less = l;
    int more = r;
    while(l<=more) {  // 注意加等号
        if (arr[l]<num) {
            swap(arr,l++,less++);
        } else if (arr[l]>num) {
            swap(arr,l,more--); // 这里l不需要--，因为换过来的数没有判断
        }else {
            l++;
        }
    }
    return new int[] { less + 1, more - 1 }; // 返回一个<区和>区的下标
}

快速排序

随机快速排序（改进的快速排序）

1）在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分： 左侧<划分值、中间==划分值、右侧>划分值

2）对左侧范围和右侧范围，递归执行

3）时间复杂度为O(N*logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        // 随机取一个数放到数组末尾，保证时间复杂度为: O(N*logN)
        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;
}

partition()函数每次将数组分为: <区 =区 > 区

该函数之前首先会将随机想要排序的num放在指定数组最后一位(即：r位置)

然后while循环，将小于num的值放到该数组的前面，大于的放后面，等于的在中间，最后一个是num

所以while循环结束后还要swap一下：

1
swap(arr, more, r);

这样就按照荷兰国旗的形式排列好了

算法
#算法
算法
https://leekosss.github.io/2024/01/17/算法/
作者
leekos
发布于
2024年1月17日
更新于
2024年1月27日
许可协议