C++：分治算法之选择问题的选择第k小元素问题

一时失言乱红尘 2024-03-22 11:26 24阅读 0赞

**目录**

3.2.6 选择问题

分析过程：

解法一：

算法代码：

【单组数据】

【多组数据】

运行结果：

解法二

代码：

运行结果：

解法三：

--------------------

## **3.2.6** **选择问题** ##

¢ **对于给定的** ***n*** **个元素的数组** **a\[0** **：** ***n*** **—** **1\]** **，要求从中找出第** ***k*** **小的元素。**

¢ **输入**

**输入有多组测试例。**

**对每一个测试例有****2****行，第一行是整数*****n*****和*****k*****（****1****≤*****k*****＜*****n*****≤****1000****），第二行是*****n*****个整数。**

¢ **输出**

**第*****k*****小的元素****。**

### 分析过程： ###

> ¢ 一种简单的解决方法就是对全部数据进行排序，于是得到问题的解。
> 
> l 但即使用较好的排序方法，算法的复杂性也为 *n* log *n* 。
> 
> ¢ 快速排序算法是分治策略的典型应用，不过不是对问题进行等份分解（二分法），而是通过分界数据（支点）将问题分解成独立的子问题。

> ¢ 首先选 第一个数 作为分界数据，将比它 小 的数据存储在它的 左边 ，比它 大 的数据存储在它的 右边 ，它存储在左、右两个子集之间。这样左、右子集就是原问题分解后的独立子问题。
> 
> l 再用同样的方法，继续解决这些子问题，直到每个子集只有一个数据，就完成了全部数据的排序工作。

> ¢ 利用 快速排序算法的思想，来解决选择问题。
> 
> l 记 一趟快速排序后，分解出 左子集 中元素个数为 *nleft* ,则选择问题可能是以下几种情况之一：
> 
> ① *nleft* ＝ k ﹣ 1，则分界数据就是选择问题的答案。
> 
> ② *nleft* ＞ k ﹣ 1 ，则选择问题的答案继续在左子集中找 ，  
> 问题规模变小了。
> 
> ③ *nleft* ＜ k ﹣ 1 ，则选择问题的答案继续在右子集中找 ，  
> 问题 变为选择 第 k- *nleft* \-1  小的数，问题的 规模变 小了。

> **此算法在最坏情况时间复杂度为**  **O(n** **2** **)**  **，此时** ***nleft*** **总是为** **0** **，左子集为空，即第** ***k*** **小元素总是位于** ***right*** **子集中。**
> 
> **平均时间复杂度为**  **O(** ***n***  **)** **。**

### 解法一： ###

![3fb6f62863bb42ccb8dd99faf4f5fa5e.png][]

### 算法代码： ###

#### 【单组数据】 ####

#include<iostream>
 #include<algorithm>
 using namespace std;
 const int NUM = 1001;
 
 int a[NUM];
 
 int select(int left,int right,int k){
 	//找到了第k小色元素
 	if (left >= right)
 		return a[left];
 	int i = left;//从左到右的指针
 	int j = right;//从右到左的指针
 	int pivot = a[left];//把最左边的元素作为分界数据
 
 	while (true)
 	{
 		//寻找左边大于pivot的数
 		do {
 			i++;
 		} while (a[i]<pivot);
 		//寻找右边小于pivot的数
 		do {
 			j--;
 		} while (a[j] > pivot);
 
 		if (i >= j)
 			break;//没有发现交换对象
 		swap(a[i], a[j]);
 	}
 	if (j - left + 1 == k)
 		return pivot;
 	a[left] = a[j];
 	a[j] = pivot;
 	if (j - left + 1 < k)
 		return select(j + 1, right, k - (j - left + 1));
 	else
 		return select(left, j - 1, k);
 }
 
 int main() {
 	int n, k;
 	cin >> n >> k;
 	for (int i = 0; i < n; i++) {
 		cin >> a[i];
 	}
 	cout<<select(0, n - 1, k);
 	return 0;
 }

#### 【多组数据】 ####

#include<iostream>
 #include<algorithm>
 using namespace std;
 const int NUM = 1001;
 
 int a[NUM];
 
 int select(int left, int right, int k) {
 //找到了第k小色元素
 if (left >= right)
 return a[left];
 int i = left;//从左到右的指针
 int j = right;//从右到左的指针
 int pivot = a[left];//把最左边的元素作为分界数据
 
 while (true)
 {
 //寻找左边大于pivot的数
 do {
 i=i+1;
 } while (a[i] < pivot);
 //寻找右边小于pivot的数
 do {
 j=j-1;
 } while (a[j] > pivot);
 
 if (i >= j)
 break;//没有发现交换对象
 swap(a[i], a[j]);
 }
 if (j - left + 1 == k)
 return pivot;
 
 //存储pivot
 a[left] = a[j];
 a[j] = pivot;
 
 if (j - left + 1 < k)
 return select(j + 1, right, k - (j - left + 1));
 else
 return select(left, j - 1, k);
 }
 
 int main() {
 int n, k;
 while (cin >> n >> k && n != 0 && k != 0) {
 for (int i = 0; i < n; i++) {
 cin >> a[i];
 }
 cout << select(0, n - 1, k) << endl;
 }
 return 0;
 }

> 这段代码实现了选择问题中的查找第 k 小元素的算法，该算法通过快速选取法（QuickSelect）实现，基本思路为利用快速排序的部分思路进行枢轴（pivot）的划分，缩小问题规模，最终得到第 k 小的元素。
> 
> 具体来说， select 函数的流程如下：
> 
> 1. 确定枢轴，默认选取序列中的第一个元素 a\[left\] 作为枢轴。
> 2. 初始化 i = left 和 j = right 两个指针，从两端向中间扫描，直至 i >= j 停止扫描。
> 3. 在扫描过程中，不断移动指针 i 和 j，使 a\[i\] < pivot 且 a\[j\] > pivot，然后交换 a\[i\] 和 a\[j\] 的值，直到 i >= j 停止。
> 4. 将枢轴和 a\[j\] 位置的元素互换，将 j - left + 1 的长度作为枢轴左边元素个数计算。
> 5. 如果 k 等于枢轴左边元素个数，则返回枢轴的值。
> 6. 如果 k 小于枢轴左边元素个数，则递归地在左半边序列里选择第 k 小元素。
> 7. 如果 k 大于枢轴左边元素个数，则递归地在右半边序列里选择第 k - (j - left + 1) 小元素。
> 
> 例如，对于序列 \{3, 5, 1, 6, 4, 2\}，查找第 3 小的元素，在 select(0, 5, 3) 中，首先选择 a\[0\] = 3 作为枢轴 pivot，然后从两端开始移动指针，扫描过程如下：
> 
> [3] 5 1 6 4 2 // i = 1, j = 5
> 3 [2] 1 6 4 5 // i = 2, j = 4
> 3 [2 1] 6 4 5 // i = 3, j = 4
> 3 [2 1] 4 6 5 // i = 3, j = 3
> 3 [2 1] 4 5 6 // i = 3, j = 2
> 3 2 [1 4] 5 6 // i = 4, j = 1
> 3 2 [1 4] 5 6 // i = 4, j = 1, 结束扫描
> 
> 从上表可以看出，最终将枢轴和 a\[j\] 位置的元素互换，得到序列 \{1, 2, 3, 6, 4, 5\}，此时第 3 小的元素 为 3，返回结果。
> 
> --------------------
> 
> a[left] = a[j];
> 	a[j] = pivot;
> 
> 在这段代码中， `a[left] = a[j]` 的作用是将枢轴的值（即最左边的元素）与当前分界点 `j` 所在位置的元素交换。而 `a[j] = pivot` 则是将原来的枢轴值（即最左边的元素）赋给当前分界点 `j` 所在位置，保证了左右两个子序列仍然是以枢轴值为分界的。
> 
> 这样做的原因是，选择算法在进行一轮快速排序后会得到分界点 `j` 的位置，也就是说，在分界点左边的所有元素都小于枢轴值，而在右边的所有元素都大于它。但是此时枢轴已经不在最左边，而是位于分界点处，因此需要将枢轴的位置与分界点所在位置进行交换，以便在递归处理子区间时能够正确地处理左右子序列。
> 
> 总之，`a[left] = a[j]` 和 `a[j] = pivot` 这两行代码可以帮助我们维护所需的元素分界点，确保选择算法能够正确地返回第 k 小的元素。

> 这段代码是一个经典的算法——快速选择，用于在一个无序数组中找到第 k 小的元素。它的改进之处可能包括以下几个方面：
> 
> 1.  随机选择枢轴 - 快速选择算法实际上是一种快速排序的变体，它通过将数组分为两个部分来寻找第 k 小的元素。在选择枢轴时，可以考虑随机选择一个位置而不是一直使用最左边的元素。这样能够减少最坏情况的出现概率，提高算法的效率。
> 2.  三数中值分割 - 在选择枢轴时，可以考虑多取几个数并找到这些数的中位数作为枢轴值。这样能够更好地均衡左右子序列的大小，减少递归次数。
> 3.  循环选择 - 如果数组很大，递归选择可能会耗费大量的时间和空间。因此，可以考虑使用循环选择算法来代替递归算法，从而提高算法的效率。
> 4.  利用线性时间选择算法 - 在某些情况下，我们需要在无序数组中查找第 k 小的元素，并且这个元素的规模非常大，超出了基于比较排序的算法的时间复杂度下界。这时可以使用线性时间选择算法来解决这个问题，它的时间复杂度为 O(n)。
> 
> 需要指出的是，以上提到的改进并不是一定都要实现，具体要看具体情况，找到适合自己问题的最优解即可。

### 运行结果： ###

![d5251b70ac5c414881c57fe37b0d99db.png][]

--------------------

### 解法二 ###

> 为了解决输入数据不随机排列以及比较元素大小时出现的问题，可以对快速选择算法进行以下改进：
> 
> 1. 在每次递归之前，随机选取一个元素作为枢轴点，确保元素的选择是随机的。
> 2. 比较元素大小时使用 <= 和 >=，以处理数组中有重复元素的情况。
> 3. 使用插入排序等排序算法来处理小数据集，避免 QuickSelect 算法退化成 O(n^2)。
> 
> 下面是改进后的代码实现：

*  #### 代码： ####

#include <iostream>
 #include <algorithm>
 
 using namespace std;
 const int NUM = 1001;
 int a[NUM];
 // 插入排序，用于处理小数据集
 void insertionSort(int a[], int start, int end) {
 for (int i = start + 1; i <= end; i++) {
 int key = a[i];
 int j = i - 1;
 while (j >= start && a[j] > key) {
 a[j + 1] = a[j];
 j--;
 }
 a[j + 1] = key;
 }
 }
 
 int quickSelect(int a[], int left, int right, int k) {
 if (right - left + 1 <= 5) {
 insertionSort(a, left, right);
 return a[left + k - 1];
 }
 // 随机选择枢轴点
 int pivotIndex = rand() % (right - left + 1) + left;
 int pivot = a[pivotIndex];
 swap(a[pivotIndex], a[right]);
 int i = left - 1;
 for (int j = left; j < right; j++) {
 if (a[j] <= pivot) {
 i++;
 swap(a[i], a[j]);
 }
 }
 swap(a[i + 1], a[right]);
 int index = i + 1 - left + 1;
 if (index == k) {
 return a[i + 1];
 }
 else if (index > k) {
 return quickSelect(a, left, i, k);
 }
 else {
 return quickSelect(a, i + 2, right, k - index);
 }
 }
 
 int main() {
 int n, k;
 while (cin >> n >> k && n != 0 && k != 0) {
 for (int i = 0; i < n; i++) {
 cin >> a[i];
 }
 cout << quickSelect(a, 0, n - 1, k) << endl;
 }
 return 0;
 }

> 这段代码实现了快速选择算法，用于查找数组中第 k 小的元素。具体过程如下：
> 
> 1. 读入数据，包括数组大小 n 和要查找的第 k 小的元素。
> 2. 读入 n 个整数，表示要查找的数组。
> 3. 调用 quickSelect 函数查找数组中第 k 小的元素，并打印结果。
> 4. 重复步骤 1~3，直到读入的 n 和 k 均为 0 为止。
> 
> 在 quickSelect 函数中，首先判断当前处理的数据集是否已经很小（比如小于等于 5），如果是，则使用插入排序来处理。这是因为插入排序对于小数据集的效率更高。
> 
> 如果数据集很大，则随机选取一个枢轴点，将比枢轴点小的元素放在数组左边，比枢轴点大的元素放在数组右边。此时，枢轴点就是整个数组中的第 index 小元素（index 是枢轴点的位置）。通过比较 index 和 k 的大小关系，可以判断第 k 小元素在数组的哪一侧，并递归处理该侧的数据集，直到找到第 k 小的元素。
> 
> 值得注意的是，为了避免算法退化成 O(n^2)，每次递归前都需要随机选择枢轴点，保证算法的随机性。另外，在比较元素大小时，使用了 <= 和 >=，以处理数组中有重复元素的情况。

*  #### 运行结果： ####

![5dba5f1f24bb4ab586b4c3953e9bccfc.png][]

--------------------

### 解法三： ###

C++：分治算法之选择问题的选择第k小元素问题

> 用 C++ 设计分治算法解决选择问题中的选择第 k 小元素问题。
> 
> 首先，对于一个无序数组来说，如果想要找到其中第 k 小的元素，可以使用快速选择算法（QuickSelect）进行处理。快速选择算法的基本思路是选取数组中的一个主元，将数组划分为两个部分，并根据主元在数组中的位置关系，决定继续处理数组的哪一部分。通过每次划分将待查找的第 k 小元素所在的区间不断缩小，最终得到结果。
> 
> 然而，在实际应用中，数据量很大时，快速选择算法的效率可能会受到影响。这时可以使用分治算法来解决问题。分治算法是一种将问题分成若干个子问题处理的思想，通过将原问题分解为多个规模较小的子问题并逐个解决，最终将子问题的解组合起来得到原问题的解。
> 
> 具体来说，对于选择第 k 小元素的问题，可以利用分治算法的思想将数组按照主元划分为两个部分，并根据主元在数组中的位置关系，决定继续处理数组的哪一部分。每次处理只需要考虑一个子问题，这样就不需要对整个数组进行排序，从而提高了算法的效率。可以使用递归的方式实现分治算法解决选择问题中的选择第 k 小元素问题。
> 
> 下面是 C++ 代码示例：

int quickSelect(vector<int>& nums, int left, int right, int k) {
 if (left == right) {// 只有一个元素
 return nums[left];
 }
 
 // 选取一个主元
 int pivotIndex = rand() % (right - left + 1) + left;
 int pivot = nums[pivotIndex];
 
 // 将数组按照主元划分为两部分
 swap(nums[pivotIndex], nums[right]);
 int i = left - 1;// i 表示左数组的右边界位置
 for (int j = left; j <= right; j++) {
 if (nums[j] < pivot) {
 i++;
 swap(nums[i], nums[j]);
 }
 }
 swap(nums[i+1], nums[right]);
 i++;
 
 // 根据主元在数组中的位置关系决定继续处理左/右子问题
 if (k == i - left + 1) {
 return nums[i];
 } else if (k < i - left + 1) {
 return quickSelect(nums, left, i-1, k);
 } else {
 return quickSelect(nums, i+1, right, k - (i - left + 1));
 }
 }
 
 int kthSmallest(vector<int>& nums, int k) {
 return quickSelect(nums, 0, nums.size()-1, k);
 }

> 以上代码中的 `quickSelect` 函数为快速选择算法的实现，`kthSmallest` 函数则是使用分治算法解决选择问题中的选择第 k 小元素问题的实现。函数的参数含义如下：
> 
>  *  `nums`：待查找第 k 小元素的数组；
>  *  `left`：当前处理区间的左边界；
>  *  `right`：当前处理区间的右边界；
>  *  `k`：目标元素的排名。

[3fb6f62863bb42ccb8dd99faf4f5fa5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/2d588510229043039fdd915ee6b2dc0a.png
[d5251b70ac5c414881c57fe37b0d99db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/0600ce18519c4777a3945da6b91512e5.png
[5dba5f1f24bb4ab586b4c3953e9bccfc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/7fe62d7acd6e4898a51eb5ea3893abd2.png