算法设计与分析（线性时间选择算法

线性时间选择算法（QuickSelect）实现

线性时间选择算法 是快速排序算法的一个变种，用于在未完全排序的数组中找到第k小的元素。线性时间选择算法的平均时间复杂度为O(n)，但最坏情况下的时间复杂度仍然是O(n^2)。通过随机选择基准点（pivot），可以在一定程度上避免最坏情况的发生。

以下是线性时间选择算法的一个C++实现示例：

#include <iostream>   
#include <stdlib.h>  
#include <time.h>  using namespace std;    // 分区函数，同时返回pivot的最终位置  
int Partition(int a[], int low, int high){  // 初始化随机数生成器  srand((unsigned)time(0));  // 随机选择一个元素作为基准点  int key = rand() % (high - low + 1) + low;  // 交换随机选定的元素和第一个元素  int t = a[key];  a[key] = a[low];  a[low] = t;  int pivot = a[low];        // 将第一个元素作为 pivot  while (low < high){  // 从后向前扫描，找到第一个小于pivot的元素  while (low < high && a[high] >= pivot) --high;  a[low] = a[high];      // 交换  // 从前向后扫描，找到第一个大于pivot的元素  while (low < high && a[low] <= pivot) ++low;  a[high] = a[low];     // 交换  }   a[low] = pivot;           // 将 pivot 放到最终的位置  return low;  
}  // 线性时间选择算法函数，找到第k小的元素  
int Select(int a[], int low, int high, int k){  if (low < high){  // 分治  int pivotpos = Partition(a, low, high);  int j = pivotpos - low + 1; // 左边剩余元素个数  if (k <= j) return Select(a, low, pivotpos, k); // 如果第k小的元素在左边，则递归左边  else return Select(a, pivotpos + 1, high, k - j); // 否则递归右边  }  else return a[low]; // 当low == high时，返回该元素  
}  int main() {  int a[10] = {5, 3, 7, 8, 4, 2, 10, 9, 1, 6};  // 输出找到的第5小的元素（注意，索引是从0开始的）  cout << "The 5th smallest element is: " << Select(a, 0, 9, 5) << endl;   return 0;    
}

注意事项

随机数生成：每次调用Partition函数时都重新设置了随机数种子，这在实际应用中是不推荐的。更好的做法是在程序开始时（如main函数最开始处）设置一次随机数种子。

时间复杂度：虽然线性时间选择算法的平均时间复杂度为O(n)，但在最坏情况下（如输入数组已经是有序的，且总是选择最小或最大元素作为pivot）会退化到O(n^2)。通过随机选择pivot可以显著降低这种情况发生的概率。

实际应用：线性时间选择算法非常适用于在未排序的数组中查找第k小（或第k大）的元素，特别是在数据量较大时，比排序整个数组后再查找要高效得多。

有可能出现的特殊情况：

因为随机数本身是关于时间的伪随机数，所以可能几次都没发送变化，因此循环好几回后才结束。

在这里插入图片描述

if (k <= j) return Select(a, low, pivotpos, k); 非常重要，k<=j 和 pivotpos 是关键，因为必须得查找到最后 low == high 才能停止。如果此时 5 的位置已经定下来了，但是 k<=j 和 pivotpos 会将 5 继续放入下一次递归，直到最后一次 low == high 递归为止。

那为什么不能 if (k < j) return Select(a, low, pivotpos-1, k); 呢？其实是可以的，首先肯定要在上面加的代码是 if (pivotpos + 1 == K) return a[pivotpos]; 这里的 K 是全局的固定值，因为 k 会一直变动。

关于过程的呈现可以使用以下代码：

#include <iostream> 
#include <stdlib.h>
#include <time.h>using namespace std;  int a[10] = {5, 3, 7, 8, 4, 2, 10, 9, 1, 6};int Partition(int a[], int low, int high){srand((unsigned)time(0));int key = rand() % (high - low + 1) + low;cout << "key: " << key << endl;// 把随机到的元素和 low 交换 int t = a[key];a[key] = a[low];a[low] = t;int pivot = a[low];        // 将第一个元素作为 pivotwhile (low < high){while (low < high && a[high] >= pivot) --high;a[low] = a[high];      // 将小于 pivot 的元素移到低端 // 这里不能为了下一步位移，因为会导致a[high] = a[low]被错误填充 while (low < high && a[low] <= pivot) ++low;a[high] = a[low];     // 将大于 pivot 的元素移到高端} a[low] = pivot;           // 将 pivot 放到最终的位置return low;
}int Select(int a[], int low, int high, int k){if (low < high){// 分治 int pivotpos = Partition(a, low, high);int j = pivotpos - low + 1;			// 左边剩余元素个数 for (int i = 0; i <= 9; i++){  cout << a[i] << ' ';  }cout << endl;if (k <= j) return Select(a, low, pivotpos, k);	// 左半段排序 else return Select(a, pivotpos + 1, high, k - j); 	// 右半段排序}else return a[low];
}int main() {// 输出找到的第 k 小的元素 cout << Select(a, 0, 9, 5) << endl; return 0;  
}