排序练习

发表于 | 分类于 |

前言：

昨天学习了九大基本排序，然后就想着不能学了不用，所以今天就莽了几个经典的排序面试题，顺带记录下来……

小范围排序练习题:

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

给定一个$int$数组$A$，同时给定A的大小$n$和题意中的$k$，请返回排序后的数组。

题解：

时间复杂度为$O(N)$的排序算法：计数排序，基数排序，因为不知道数组中具体某个数的范围，所以不适用所有情况；

时间复杂度为$O(N^2)$的排序算法：冒泡排序，选择排序，时间复杂度跟原始数组的序列无关，所以时间复杂度是严格的$O(N^2)$的；插入排序，每个元素移动距离不超过$k$，也就意味着插入排序的步长不会超过$k$，所以对于插入排序，时间复杂度不会超过$O(N * K)$；

时间复杂度为$O(N * log N)$的排序算法：快速排序，归并排序，时间复杂度跟原数组的序列无关

上述的方法都不是最优解，最优解是改进后的堆排序：

因为每个元素的移动距离不会超过$k$，也就是排序后每个元素的最小值不会超过$k$，所以整个数组的最小值一定是在$[0 , k - 1]$这个区间里面产生的，那么就有下面的操作：

  • 建立一个根据$a[0]……a[k - 1]$小根堆，堆顶就是整个数组的最小值
  • 取出堆顶，放在数组的第一个元素中，再将$a[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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public int[] sortElement(int[] A, int n, int k) {
	if(A == null && A.length == 0 && n < k)
		return A;
	int[] heap = getKHeap(A, k);
	for(int i = k; i < n; ++i){
		A[i - k] = heap[0];
		heap[0] = A[i];
		heapify(heap, 0, k);
	}
	for(int i = n - k; i < n; ++i){
		A[i] = heap[0];
		swap(heap, 0, k - 1);
		heapify(heap, 0, --k);
	}
	return A;
}

private int[] getKHeap(int[] a, int k) {
	int[] heap = new int[k];
	for(int i = 0; i < k; ++i){
		heapInsert(heap, a[i], i);
	}
	return heap;
}

private void heapInsert(int[] heap, int value, int index) {
	heap[index] = value;
	while(index != 0){
		int parent = (index - 1) / 2;
		if(heap[parent] > heap[index]){
			swap(heap, parent, index);
			index = parent;
		}else {
			break;
		}
	}
}

private void heapify(int[] heap, int index, int heapSize) {
	int l = index * 2 + 1;
	int r = index * 2 + 2;
	int minn = index;
	while(l < heapSize){
		if(heap[l] < heap[index]){
			minn = l;
		}
		if(r < heapSize && heap[r] < heap[minn]){
			minn = r;
		}
		if(minn != index){
			swap(heap, minn, index);
		}else {
			break;
		}
		index = minn;
		l = index * 2 + 1;
		r = index * 2 + 2;
	}
}

private void swap(int[] heap, int minn, int index) {
	int tmp = heap[minn];
	heap[minn] = heap[index];
	heap[index] = tmp;
}

三色排序练习题:

有一个只由$0，1，2$三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。给定一个只含$0，1，2$的整数数组$A$及它的大小，请返回排序后的数组。保证数组大小小于等于$500$。

题解：

经典的荷兰国旗问题，整个划分过程跟快排的划分过程实际上是很像的

划分过程：

  • 数组的最左边划定一个$0$区，最右边划定一个$1$区
  • 给定一个游标，从左到右遍历
  • 比较当前的数是否等于$0$，以及是否等于$2$；如果等于$0$，就将其放到&0&区，如果等于$2$，就将其放到$2$区
  • 重复上述操作，直到当前的位置和$2$区的位置重合的时候结束

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void swap(int[] heap, int minn, int index) {
	int tmp = heap[minn];
	heap[minn] = heap[index];
	heap[index] = tmp;
}

public int[] sortThreeColor(int[] A, int n) {
	int l = -1;
	int r = A.length;
	int index = 0;
	while(index < r){
		if(A[index] == 0){
			swap(A, ++l, index++);
		}else if(A[index] == 2){
			swap(A, index, --r);
		}else{
			++index;
		}
	}
	return A;
}

最短子数组练习题:

对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。

给定一个$int$数组$A$和数组的大小$n$，请返回一个二元组，代表所求序列的长度。(原序列位置从$0$开始标号,若原序列有序，返回$0$)。保证A中元素均为正整数。

题解：

这道题它的最优解可以做到时间复杂度$O(N)$，额外空间复杂度为$O(1)$

做法是：

首先从左到右遍历整个数组，单独用一个变量记录一下遍历过部分的最大值，此时我们只关注一种情况：就是遍历过部分的最大值大于当前数的这种情况，这种情况发生的时候我们知道真实的排序之后这个最大值它起码会在当前数的位置或者是更右的位置。从左到右遍历过程中，我们记录发生这种情况的最右的位置。

接下来是从右到左遍历整个数组，同样单独用一个变量记录遍历过部分的最小值，同样我们只关注遍历过部分的最小值小于当前数的这种情况，这种情况发生我们知道真实的排序之后这个最小值它会在当前数的位置或者更左边的位置。从右到左遍历过程中，记录发生这种情况的最左的位置。

最左的位置到最右的位置范围就是我们需要排序的最短子数组。

代码：

1
2


相邻两数最大差值练习题:

有一个整形数组$A$，请设计一个复杂度为$O(n)$的算法，算出排序后相邻两数的最大差值。

给定一个$int$数组$A$和$A$的大小$n$，请返回最大的差值。保证数组元素多于$1$个。

题解：

这道题目的最优解可以做到时间复杂度为$O(N)$，额外空间复杂度为$O(N)$

它的思想来自于桶排序思想，但不是真实的进行的桶排序

过程：

  • 找到数组的最大值，最小值，分为$n$（数组的元素个数）个等量的区间
  • 每个区间分别对应一个桶，每个数根据数值分别放入一个桶，然后$n + 1$号桶中放入最大值
  • 桶的数量有$n + 1$个，数组元素有$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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public int maxGap(int[] nums,int N) {
	if (nums == null || nums.length < 2) {
		return 0;
	}
	int len = nums.length;
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < len; i++) {
		min = Math.min(min, nums[i]);
		max = Math.max(max, nums[i]);
	}
	if (min == max) {
		return 0;
	}
	boolean[] hasNum = new boolean[len + 1];
	int[] maxs = new int[len + 1];
	int[] mins = new int[len + 1];
	int bid = 0;
	for (int i = 0; i < len; i++) {
		bid = bucket(nums[i], len, min, max); // 算出桶号
		mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
		maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
		hasNum[bid] = true;
	}
	int res = 0;
	int lastMax = 0;
	int i = 0;
	while (i <= len) {
		if (hasNum[i++]) { // 找到第一个不空的桶
			lastMax = maxs[i - 1];
			break;
		}
	}
	for (; i <= len; i++) {
		if (hasNum[i]) {
			res = Math.max(res, mins[i] - lastMax);
			lastMax = maxs[i];
		}
	}
	return res;
}

// 使用long类型是为了防止相乘时溢出
public int bucket(long num, long len, long min, long max) {
	return (int) ((num - min) * len / (max - min));
}