失眠网 > c语言线性时间选择分治法【分治法】线性时间选择（转）

c语言线性时间选择分治法【分治法】线性时间选择（转）

时间：2023-12-05 21:27:03

转自：/liufeng_king/article/details/8480430

线性时间选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，(这里给定的线性集是无序的)。

1、随机划分线性选择

线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理。

程序清单如下：

1 //2d9-1 随机划分线性时间选择

2 #include "stdafx.h"

3 #include

4 #include

5 using namespacestd;6

7 int a[] = {5,7,3,4,8,6,9,1,2};8

9 template

10 void Swap(Type &x,Type &y);11

12 inline int Random(int x, inty);13

14 template

15 int Partition(Type a[],int p,intr);16

17 template

18 int RandomizedPartition(Type a[],int p,intr);19

20 template

21 Type RandomizedSelect(Type a[],int p,int r,intk);22

23 intmain()24 {25 for(int i=0; i<9; i++)26 {27 cout<

33 template

34 void Swap(Type &x,Type &y)35 {36 Type temp =x;37 x =y;38 y =temp;39 }40

41 inline int Random(int x, inty)42 {43 srand((unsigned)time(0));44 int ran_num = rand() % (y - x) +x;45 returnran_num;46 }47

48 template

49 int Partition(Type a[],int p,intr)50 {51 int i = p,j = r + 1;52 Type x =a[p];53

54 while(true)55 {56 while(a[++i]x);58 if(i>=j)59 {60 break;61 }62 Swap(a[i],a[j]);63 }64 a[p] =a[j];65 a[j] =x;66 returnj;67 }68

69 template

70 int RandomizedPartition(Type a[],int p,intr)71 {72 int i =Random(p,r);73 Swap(a[i],a[p]);74 returnPartition(a,p,r);75 }76

77 template

78 Type RandomizedSelect(Type a[],int p,int r,intk)79 {80 if(p ==r)81 {82 returna[p];83 }84 int i =RandomizedPartition(a,p,r);85 int j = i - p + 1;86 if(k <=j)87 {88 returnRandomizedSelect(a,p,i,k);89 }90 else

91 {92 //由于已知道子数组a[p:i]中的元素均小于要找的第k小元素93 //因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。

94 return RandomizedSelect(a,i+1,r,k-j);95 }96 }

View Code

程序解释：利用随机函数产生划分基准，将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r]，使a[p:i]中的每个元素都不大于a[i+1:r]中的每个元素。接着"j=i-p+1"计算a[p:i]中元素个数j.如果k<=j，则a[p:r]中第k小元素在子数组a[p:i]中，如果k>j，则第k小元素在子数组a[i+1:r]中。注意：由于已知道子数组a[p:i]中的元素均小于要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。

在最坏的情况下，例如：总是找到最小元素时，总是在最大元素处划分，这是时间复杂度为O(n^2)。但平均时间复杂度与n呈线性关系，为O(n)(数学证明过程略过,可参考王云鹏论文《

2、利用中位数线性时间选择

中位数：是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。

算法思路：如果能在线性时间内找到一个划分基准使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0

实现步骤：

(1)将所有的数n个以每5个划分为一组共

组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。将每组中的元素排好序再分别取每组的中位数，得到

个中位数。

(2)取这

个中位数的中位数，如果

是偶数，就找它的2个中位数中较大的一个作为划分基准。

(3)将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。在这种情况下找出的基准x至少比