uni_shiki

算法与数据结构_2_递归、master公式、归并排序、荷兰国旗问题、快排

  • 2023-03-18
  • 作者 uni_shiki
  • ~3.73K 字

 

递归

  • 算中点距离：

    • mid = (L + R) / 2 : L + R可能越界
    • mid = L + (R - L) / 2 : 更好
    • 等同于 L + (R - L) >> 1 : 右移一位比/2要快

  • 递归求一个数组的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int getMax(int[] arr)
{
	return process(arr, 0, arr.length - 1);
}

public static int process(int[] arr, int L, int R)
{
	if (L == R) // arr[L..R]范围上只有一个数，直接返回
	{
		return arr[L];
	}
	int mid = L +((R - L) >> 1);
	int leftMax = process(arr, L, mid);
	int rightMax = process(arr, mid + 1, R);
	return Math.max(leftMax, rightMax);
}

master公式

  • T(N) = a * T(N / b) + O(N^d)
    • T(N) : 母问题规模
    • T(N / b) : 子问题的规模
    • a : 子问题的调用次数
    • O(N^d) : 除去调用之外，剩下的过程的时间复杂度
  • 只要是满足子问题等规模的递归，都可以用master公式求解时间复杂度
  • logb^a < d O(N^d)
    logb^a > d O(N^logb^a)
    logb^a == d O(N^d * 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
public static void process(int[] arr, int L, int R)
{
	if (L == R)
	{
		return;
	}
	int mid = L + ((R - L) >> 1);
	process(arr, L, mid);
	process(arr, mid + 1, R);
	merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int M, int R)
{
	int[] help = new int[R - L + 1];
	int i = 0;
	int p1 = L;
	int p2 = M + 1;
	while (p1 <= M && p2 <= R)
	{
		help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= M)
	{
		help[i++] = arr[p1++];
	}
	while (p2 <= R)
	{
		help[i++] = arr[p2++];
	}
	for (i = 0; i < help.length; i++)
	{
		arr[L + i] = help[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
32
33
34
35
36
37
38
39
40
41
42
43
	public static int mergeSort(int[] arr, int L, int R)
	{
		if (R == L)
		{
			return 0;
		}
		int 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 M, int R)
	{
		int[] help = new int[R - L +1];
		int i = 0;
		int p1 = L;
		int p2 = M + 1;
		int sum = 0;
		while (p1 <= M && p2 <= R)
		{
			sum += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
//			if (arr[p1] < arr[p2])
//			{
//				sum += (R - p2 + 1) * arr[p1];
//				help[i++] = arr[p1++];
//			}
//			else
//			{
//				help[i++] = arr[p2++];
//			}
		}
		while (p1 <= M)
		{
			help[i++] = arr[p1++];
		}
		while (p2 <= R)
		{
			help[i++] = arr[p2++];
		}
		
		return sum;
	}

荷兰国旗问题

  • 给定一个整形数组和一个数，要求按这个数将数组分为3个区域，> == <。
    1. [i] < num, [i] 和< 区域下一个交换, <区域右扩, i++
    2. [i] == num, i++
    3. [i] > num, [i] 和> 区域前一个交换, >区域左扩, i不变

快速排序

  • 快排1.0
    • 拿最后一个数num做划分
    • 前面的数 <= num的放左边, > num的放右边
    • 大于区域的第一个数和num做交换
    • 让左侧和右侧重复这个行为
  • 快排2.0
    • 利用荷兰国旗问题，一次搞定一批相等的数，比1.0快
    • 用最后一个数num做划分
    • 前面的数分成 <num ==num >num三个区域
    • 把num和>num区域第一个数交换
    • 让左侧和右侧重复这个行为
  • 快排3.0
    • 随机选一个数，放在最后，拿它做划分值num
    • 时间复杂度变成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
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); // >区
	}
}
// partition返回int[2] 等于划分值的 左边界和右边界 两个值
public static int[] patition(int[] arr, int L, int R)
{
	int less = L - 1; // <区右界
	int more = R; // >区左界
	while (L < more) // L表示当前数的位置 arr[R] -> 划分值
	{
		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};
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2024-03-26