一、关于分治策略

分治策略： 简单来说就是将问题的规模变小，问题本身不变

解题步骤：

  • 分解： 将原问题划分成子问题，规模变小
  • 递归： 递归求解子问题，若子问题规模足够小，此时停止递归，直接求解
  • 合并： 将小规模的解合并成原规模的解

注意： 分治策略是一种处理问题的思想，递归是一种算法。

二、使用分治策略+递归解题

（1）快速排序

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
113
114
115
116
117
118
#include<iostream>
#include<stack>
#include<limits.h>

using namespace std;
//快排
#if 1
class QuickSort
{
public:
	//从左向右划分（适用于单链表）
	void LeftToRight(int* arr, int left, int right)
	{
		int j = left - 1;
		int i = left;
		int tmp = arr[left];
		while (i <= right)
		{
			if (arr[i] <= tmp)
			{
				++j;
				swap(arr[i], arr[j]);
			}
			++i;
		}
		swap(arr[left], arr[j]);
		if (left < j - 1)
		{
			LeftToRight(arr, left, j - 1);
		}
		if (j + 1 < right)
		{
			LeftToRight(arr, j + 1, right);
		}	
	}
private:
	//两边向中间划分
	int OnePartition(int* arr, int left, int right)
	{
		int tmp = arr[left];
		int i = left;
		int j = right;
		while (i < j)
		{
			while (i < j && arr[j] > tmp)
			{
				--j;
			}
			arr[i] = arr[j];
			while (i < j && arr[i] <= tmp)
			{
				++i;
			}
			arr[j] = arr[i];
		}
		arr[i] = tmp;
		return i;
	}

public:
	//递归快排
	void quicksort(int* arr, int left, int right)
	{
		if (arr == nullptr || left < 0 || right < 0 || right < left)
			return;
		if (left < right)
		{
			//一次划分
			int mid = OnePartition(arr, left, right);
			quicksort(arr, left, mid - 1);
			quicksort(arr, mid + 1, right);
		}
	}
	//非递归
	void NonRecursive(int* arr, int left, int right)
	{
		if (arr == nullptr || left < 0 || right < 0 || right < left)
			return;
	
		//使用栈
		stack<std::pair<int, int>> st;
		st.push(std::pair<int, int>(left, right));

		while (!st.empty())
		{
			std::pair<int, int> top = st.top();
			st.pop();
			int mid = OnePartition(arr, top.first, top.second);
			if (top.first < mid - 1)
			{
				//左边
				st.push(std::pair<int, int>(top.first, mid - 1));
			}
			if (mid + 1 < top.second)
			{
				//右边
				st.push(std::pair<int, int>(mid + 1, top.second));
			}
		}
	}
};

int main()
{
	int arr[] = {12, 23, 56, 45, 78, 42, 12, 45, 42, 12};
	int len = sizeof(arr) / sizeof(arr[0]);

	QuickSort q;
	//q.NonRecursive(arr, 0, len - 1);
	q.LeftToRight(arr, 0 , len - 1);
	for (const int& x : arr)
	{
		cout << x << " ";
	}
	return 0;
}

#endif

（2）寻找无序不重复的数组第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

//寻找不重复的第K小
#if 1
//两边向中间划分
int OnePartition(int* arr, int left, int right)
{
	int tmp = arr[left];
	int i = left;
	int j = right;
	while (i < j)
	{
		while (i < j && arr[j] > tmp)
		{
			--j;
		}
		arr[i] = arr[j];
		while (i < j && arr[i] <= tmp)
		{
			++i;
		}
		arr[j] = arr[i];
	}
	arr[i] = tmp;
	return i;
}
//findK
int FindK(int* arr, int left, int right, int k)
{
	if (left == right && k == 1) return arr[left];
	int mid = OnePartition(arr, left, right);
	int kmin = mid - left + 1;	//arr[mid]是kmin小
	//第k小在mid左边(arr, left, mid, k)
	if (k <= kmin)
	{
		return FindK(arr, left, mid, k);
	}
	//k小在mid右边
	else
	{
		return FindK(arr, mid + 1, right, k - kmin);
	}
}
//寻找不重复的第K小
int FindK_min(int* arr, int len, int k)
{
	if (nullptr == arr || len <= 0 || k > len)
		return -1;
	return FindK(arr, 0, len - 1, k);
}

int main()
{
	int arr[] = {56, 12, 23, 45, 89, 86, 46, 57, 26, 33};
	int len = sizeof(arr) / sizeof(arr[0]);
	for (int k = 1; k < 10; ++k)
	{
		cout << FindK_min(arr, len, k)<< endl;
	}
	return 0;
}

#endif

（3）归并排序

归并排序的思想：类似于二叉树的后序遍历（根左右）。（递归过程中分组，回归过程中排序合并数据）

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
//归并排序（递归）
#if 1
//有序合并
void Merge(int* src, int* des, int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		des[k++] = src[i] <= src[j] ? src[i++] : src[j++];
	}
	while (i <= mid)
	{
		des[k++] = src[i++];
	}
	while (j <= right)
	{
		des[k++] = src[j++];
	}
}
//拷贝
void Copy(int* src, int* des, int left, int right)
{
	if (nullptr == des || nullptr == src) return;
	while (left <= right)
	{
		src[left] = des[left];
		++left;
	}
}
//归并
void MergePass(int* arr, int* des, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		MergePass(arr, des, left, mid);
		MergePass(arr, des, mid + 1, right);
		//有序合并到des
		Merge(arr, des, left, mid, right);
		//有序des复制到arr
		Copy(arr, des, left, right);
	}
}
//排序
void MergerSort(int* arr, int len)
{
	if (nullptr == arr || len < 2) return;
	int* tmp = new int[len];
	MergePass(arr,tmp , 0, len - 1);
	delete[] tmp;
}
int main()
{
	int arr[] = { 12, 23, 56, 45, 78, 42, 12, 45, 42, 12 };
	int len = sizeof(arr) / sizeof(arr[0]);
	MergerSort(arr, len);
	for (const int& x : arr)
	{
		cout << x << " ";
	}
	return 0;
}
#endif