uni_shiki

算法与数据结构_3_快排、堆、比较器

  • 2023-03-19
  • 作者 uni_shiki
  • ~6.36K 字

 

快排

  • 额外空间复杂度：好情况O(logN),差情况O(N)

完全二叉树

  • 左孩子 : 2 * i + 1
    右孩子 : 2 * i + 2
    父节点 : (i - 1) / 2

  • 有N个节点时，高度是logN级别

  • heapInsert时，只关心父节点的路径上走多少高度，所以用户新加一个数字时，调整的代价是O(logN)级别

  • 用户想删掉一个数，并让剩下的数重新调整堆的代价也是O(logN)级别

堆

  1. 堆结构就是用数组实现的完全二叉树结构

  2. 完全二叉树分为大根堆、小根堆

  • 大根堆 : 每个子树最大值都是头节点
  • 小根堆 : 每个子树最小值都是头节点
  1. 堆结构的heapInsert和heapify操作
  • 维持大根堆 : 将每次放进数组的值跟它的父节点的值做比较并调整，这个过程称为heapInsert
  • heapInsert :
1
2
3
4
5
6
7
8
public static void heapInsert(int[] arr, int index)
{
	while (arr[index] > arr[(index - 1) / 2]) // 到0位置时，while依然不成立
	{
		swap(arr, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}
  • 假设用户需要返回最大的数，这个数就是arr[0]
  • 假设用户需要删除最大的数，做法是 :
    交换第一个和最后一个数，同时heapsize–，不断比较两个孩子中最大的一个与父节点的大小，并调整，这个过程称为heapify
  • heapify :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void heapify(int[] arr, int index, index heapSize)
{
	int left = index * 2 + 1; // 左孩子下标

	while (left < heapSize) // 下方还有孩子时
	{
		// 俩孩子谁的值大，把下标记下
		int largest = left + 1 < heapSize && 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;
	}
}
  1. 堆结构的增大和减小
  • heapSort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void heapSort(int[] arr)
{
	if (arr == null || arr.length < 2)
	{
		return;
	}
	for (int i = 0; i < arr.length; i++) // O(N)
	{
		heapInsert(arr, i); // O(logN)
	}
	int heapSize = arr.length;
	swap(arr, 0, --heapSize);
	while (heapSize > 0) // O(N)
	{
		heapify(arr, 0, heapSize); // O(logN)
		swap(arr, 0, --heapSize); // O(1)
	}
}
  • 用户加数O(NlogN),heapify时O(NlogN),整体O(NlogN),额外空间复杂度O(1)
  • mergeSort额外空间复杂度O(N),快排O(logN)
  • 如果用户一股脑给出所有数组，要求弄成大根堆，可以从后往前做heapify，从倒数第二层开始，都只用往下进行一次heapify
  • 这时时间复杂度 :
    (如果数组中有N个数，想象成满二叉树，这时最底层节点N/2个)
    T(N) = N/2 + N/4 * 2 + N/8 * 3 + N/16 * 4 + …
    2T(N) = N/2 * 2 + N/2 * 2 + N/4 * 3 + …
    T(N) = N + N/2 + N/4 + N/8 + … = O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void heapSort(int[] arr)
{
	if (arr == null || arr.length < 2)
	{
		return;
	}
	//for (int i = 0; i < arr.length; i++) // O(N)
	//{
	//	heapInsert(arr, i); // O(logN)
	//}

	for (int i = arr.length - 1; i >= 0; i--)
	{
		heapify(arr, i, arr.length);
	}

	int heapSize = arr.length;
	swap(arr, 0, --heapSize);
	while (heapSize > 0) // O(N)
	{
		heapify(arr, 0, heapSize); // O(logN)
		swap(arr, 0, --heapSize); // O(1)
	}
}

  1. 优先级队列结构，就是堆结构

  2. 堆排序扩展题目

  • 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序
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
import java.util.PriorityQueue;

public void sortedArrDistanceLessK(int[] arr, int k)
{
	// 默认小根堆
	PriorityQueue<Integer> heap = new PriorityQueue<>();
	int index = 0;
	for (; index <= Math.min(arr.length, k); index++)
	{
		heap.add(arr[index]);
	}
	int i = 0;
	for (; index <= arr.length; index++)
	{
		heap.add(arr[index]);
		arr[i] = heap.poll();
	}
	while (!heap.isEmpty())
	{
		arr[i++] = heap.poll();
	}
}

public static void main(String[] args)
{
	PriorityQueue<Integer> heap = new PriorityQueue<>();

	heap.add(8);
	heap.add(4);
	heap.add(4);
	heap.add(9);
	heap.add(10);
	heap.add(3);
	heap.add(2);
	heap.add(8);

	while (!heap.isEmpty())
	{
		System.out.printf(heap.poll());
	}
}

比较器

  • 实现Comparator接口，重载int compare()方法，可写成内部类
  • 对于sort排序
    如果返回负数，认为第一个参数应该放在前面
    如果返回正数，认为第二个参数应该放在前面
    如果返回0，认为谁在前面都行
  • 对于new PriorityQueue<>(new AComp())的创建
    如果返回负数，认为第一个参数应该放在上面
    如果返回正数，认为第二个参数应该放在上面
    如果返回0，认为谁在上面都行
1
2
3
4
5
6
7
8
9
10
11
12
public class HeapTest
{
	public static class Acomp implements Comparator<Integer>
	{
		@override
		public int compare(Integer arg0, Integer arg1)
		{
			return arg1 - arg0;
		}
	}
	...
}

不基于比较的排序

  • 不基于比较的排序 必须分析数据状况来定制
  • 计数排序
    • 员工的年龄，建一个数组age[200],遍历一般，将下标对应成年龄来计数，如 1岁 arg[1]++。O(N)
  • 基数排序
    • [17 13 25 100 72]排序，先看最大的数字是几位
      按十进制数看
      [017 013 025 100 072]
      准备容器(可以是数组/队列/栈)，叫做桶
      这里假设桶是队列，准备10个桶
      先根据各位数字来 017放到7号桶 013放到3号桶 …
      把桶中的所有数字依次倒出来
      [100 072 013 025 017]
      再按十位数决定进哪个桶 100进0号桶 072进7号桶 …
      把桶中的所有数字依次倒出来
      [100 013 017 025 072]
      最后按百位数字决定进哪个桶 100进1号桶 013 017 025 072进0号桶
      把桶中的所有数字依次倒出来
      [013 017 025 072 100]
  • 基数排序代码
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
public static void radixSort(int[] arr)
{
	if (arr == null || arr.length < 2)
	{
		return;
	}
	radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

public static int maxbits(int[] arr)
{
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < arr.length; i++)
	{
		max = Math.max(max, arr[i]);
	}
	int res = 0;
	while (max != 0)
	{
		res++;
		max /= 10;
	}
	return res;
}

public static void radixSort(int[] arr, int L, int R, int digit) // digit表示这一批数中最大的有几个十进制位
{
	final int ridix = 10;
	int i = 0, j = 0;
	// 有多少个数准备多少个辅助空间
	int[] bucket = new int[R - L + 1];
	for (int d = 1; d <= digit; d++) // 最大数有多少位就进出几次
	{
		// 10个空间 词频表
		// count[0] 当前位(d位)是0的数字有多少个
		// count[1] 当前位(d位)是(0和1)的数字有多少个
		// count[2] 当前位(d位)是(0、1和2)的数字有多少个
		// count[i] 当前位(d位)是(0~i)的数字有多少个
		int[] count = new int[radix]; // count[0..9]
		for (i = L; i <= R; i++)
		{
			j = getDigit(arr[i], d); // 取出d位上的数字
			count[j]++;
		}
		// 将count加工成前缀和
		for (i = 1; i < redix; i++)
		{
			count[i] = count[i] + count[i - 1];
		}
		// 从右往左将原数组放进辅助数组，词频前缀和-1的下标位置，词频前缀和--
		// 如100 061 074 083 053
		// count [0] [1] [2] [3] [4]
		// 词频   1   1   0   2   1 
		// 词频和 1   2   2   4   5
		// 从右往左看 053的个位数3,词频和4表示个位数<=3(0、1、2、3)的词频和,出栈时一定是最大的数3(词频和4-1),放在help[3],词频和--
		// count [0] [1] [2] [3] [4]
		// 词频和 1   2   2   3   5
		// 083 词频和3 个位数<=3(0、1、2、3),放在help[2],词频和--
		// count [0] [1] [2] [3] [4]
		// 词频和 1   2   2   2   5
		// 074 词频和5 个位数<=4(0、1、2、3、4),放在help[4](5-1),词频和--
		// help [0] [1] [2] [3] [4]
		//              083 053 074
		// count[3]为<=3的词频和， 这个词频和-1
		for (i = R; i >= L; i--)
		{
			j = getDigit(arr[i], d);
			bucket[count[j] - 1] = arr[i];
			count[j]--;
		}
		for (i = L, j = 0; i <= R; i++, j++)
		{
			arr[i] = bucket[j];
		}
	}
}

public static int getDigit(int x, int d)
{
	return ((x / ((int) Math.pow(10, d - 1))) % 10); 
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2024-03-26