线性查找算法(BFPTR算法)的原始实现，以及改进形式， C语言实现

蔚落 2023-03-01 05:32 24阅读 0赞

先说明一下，这里所说的是“线性查找”，而不是“顺序查找”。线性查找算法又叫BFPRT算法，即Blum、Floyd、Pratt、Rivest、Tarjan等5个作者的名字的缩写，Blum、Floyd、Rivest、Tarjan这四个作者都是图灵奖得主，可见这个算法的份量。

在具体介绍线性查找算法之前，我们先来看看它的用途：解决Top-K问题。  
Top-K问题：如果数组arr中的数据不是有序的，怎么样才能找第k大的数？下面是三种解决方案：  
1、用选择排序的思想，对数组进行部分排序，重复k次之后找出最大的k个数据，则arr\[k\]就是第k大的数。这样做的时间复杂度为O(N \* K)。  
2、直接对整个数组进行排序，arr\[k\]就是第k大的数。这样做的时间复杂度为O(N \* logN)。这种方式对其余n - k个数据进行排序，但这些数据是没有必要排序的。对这些数据的排序浪费了很多时间。  
3、借助于堆排序，建立一个有k个数组成的小顶堆。然后遍历剩余元素，跳过比堆顶元素小的数，如果被遍历的元素比堆顶元素大，就用这个数取代堆顶元素，并重新维护这个堆。这样做的时间复杂度为O(N \* logK)。这种方式只对k个元素进行排序，所以时间复杂度就比较小了。这种方式中，k个元素的堆仍然是处于总体有序的状态。  
上面这三种方法都进行了排序，或者部分排序。所以导致算法的时间复杂度都比较大。有没有办法让top-K问题的时间复杂度降低到O(N) 呢？这时，BFPRT等五位大神就出场了。

在讨论BFPRT算法之前，我们先回忆一下原始的快速排序算法：快速排序算法最神奇的地方是在一轮扫描之后可以让基准数找到它的正确位置 (standardIndex)，而且这个基准数据可以不是最大值或者最小值。这样，待排序的数组就被分成了三块。接着分别在左边和右边两段数组中继续递归查找基准数的正确位置即可。  
如果我们把快速排序法用在top-K问题里该怎么做：取一个基准数，然后扫描整个数组，找到这个基准数的正确位置 (standardIndex)，如果standardIndex正好是整个数组中的第k个位置，那么这个基准数就是我们希望找的第k大的值。如果standardIndex ＜ k，那就继续在standardIndex右边找；如果standardIndex ＞ k，那就继续在standardIndex左边找。先不考虑这种查找方式的效率怎么样，我们至少能找到第k大的数了。实现代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    int arr[] = {
         3, 6, 1, 8, 2, 5, 9, 4, 7 }; //无序的数组 
    int size = 0; //数组的大小，需要重新计算 
    
    void swap(int a, int b)
    {
        
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    //快速排序的划分过程
    int Partion(int low, int high) 
    {
        
    	if (low > high) //递归的出口 
    	{
        
    		return -1;	
    	}
    	
    	int standard = arr[low]; //最左边的元素作为基准 
    	int i = low; //确定范围 
    	int j = high;
    	
    	// 将大于基准数的元素交换到基准数的左边，小于基准数的元素交换到基准数的右边
    	while (i < j) 
    	{
        
    		while (i < j && arr[j] <= standard) 
    		{
        
    			j--;
    		}
    		while (i < j && arr[i] >= standard) 
    		{
        
    			i++;
    		}
    		if(i < j) //东东和虫虫没有相遇 
    		{
        
    			swap(i, j);
    		}
    	}
    	
    	//东东和虫虫相遇后 
    	arr[low] = arr[i];
    	arr[i] = standard;
    	
    	return i; //返回基准数的下标
    }
    
    void show() //显示数组 
    {
        
    	for (int i = 0; i < size; ++i)
        {
        
            printf("%d ", arr[i]);
        }
        printf("\r\n");
    }
    
    int BFPTR(int low, int high, int k)
    {
        
    	show();
    	printf("查找第%d大的数据: 查找范围:%d--%d，基准数是%d\r\n", k, arr[low], arr[high], arr[low]);
    	int standardIndex = Partion(low, high); //划分 
    	
    	if(standardIndex < 0)
    	{
        
    		printf("k > 数组中元素个数，出错\r\n");
    		return -1;
    	}
    
    	if (standardIndex == k) 
    	{
        
    		printf("基准数的下标是%d, 与k相等，所以要查找的数是：%d\r\n", standardIndex, arr[k]);
    		show();
    		return standardIndex;
    	}
    	else if (standardIndex > k) 
    	{
        
    		printf("基准数的下标%d > %d，在基准数的左边递归查找\r\n\r\n", standardIndex, k);
    		return BFPTR(low, standardIndex - 1, k); //在standardIndex左侧继续递归查找
    	}
    	else
    	{
        
    		printf("基准数的下标%d < %d，在基准数的右边递归查找\r\n\r\n", standardIndex, k);
    		return BFPTR(standardIndex + 1, high, k); //在standardIndex右侧继续递归查找	
    	}
    	printf("\r\n\r\n");
    }
    
    int main()
    {
        
        size = sizeof(arr) / sizeof(int); //动态计算数组大小 
        int k = 1; //查找第k大的元素 
        BFPTR(0, size - 1, k); //调用BFPTR算法 
        return 0;
    }

运行结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
下面我们分析一下这个方法的时间复杂度。如果每次都能把数组划分为差不多大小的两段，那么n个数据在划分log2N次之后就只剩下1个数据，总的时间复杂度为O(N)。推导如下：  
一共要操作的次数sum = 20 + 21 + 22 +23 +… +2logN = 2logN + 1 - 1 = 2N - 1。  
时间复杂度为O(sum) = O(2N - 1) = O(N)。

但是，如果待查找的数组本身是有序的，则每次取得的基准数都是最大值或者最小值，这时每次划分都只能减少一个元素，这样查找效率就会变得很低，时间复杂度为O(N^2)。如果每次随机选择一个元素作为基准，这样也能提高效率，但是这种方式并不可靠，不能确保每次都找到比较靠中间的元素。那么有没有比较可靠的方式找到中间的元素呢? (也就是说，我们希望时间复杂度永远为O(N)。)  
方法①：很简单，把所有元素都排序一下，然后一定可以找到中间元素 (这不是废话嘛！)。这个方法的时间复杂度比较高，不可行！  
方法②：把数组分为5个元素为一组进行排序，直到所有元素都被分组。其中最后一个分组可能不是5个元素。排好序之后，取每一组的中间元素，组成一个新的数组。然后再次把数组分为5个元素为一组进行排序…这样，最后可以得到一个元素。这个元素在原始数组中基本上就是比较靠中间的元素了。在所有比较排序算法中，对于 < 50个元素的数组，使用插入排序的速度最快。插入排序查找中间值的中间值的时间复杂度为O(N)，合理的划分的时间复杂度也是O(N)，所以整个算法的时间复杂度也是O(N)。  
在插入排序的时间复杂度为的证明：输入规模为常数5，以swap作基本操作，设其最坏情况下时间复杂度为 T1 ，则：T1(n = 5) = 1 + 2 + 3 + 4 = 10 = O(1)。  
查找中间值的中间值的时间复杂度为O(N)的证明：http://www.voidcn.com/article/p-xnguptda-vt.html

方法②就是BFPRT算法中最核心的一部分内容。下面是BFPRT算法完整的描述：  
1.将序列中所有元素按5个元素一组进行划分，最后一组可能少于5个元素，对每一组元素进行插入排序选出中间的元素即为中位数；  
2.对所有中位数重复步骤1，即对中位数进行分组，求得它们的中位数；重复此步骤，直到只有一个中位数；  
3.遍历序列，得到该中位数的下标；  
4.以该中位数作为pivot，对序列进行Partion划分过程，返回划分后的中位数的下标；  
5.根据下标得出当前中位数是第X大元素，判断X是否等于K，若是则表明该中位数即为第K大元素，返回下标；否则，判断X是否小于K，若是，则从中位数左边的元素中递归找出第K大元素；否则，从中位数右边的元素中找出第K-X大元素 (因为经过Partion后，中位数左边的元素都大于等于该中位数)。

#include <stdio.h>
    #include <stdlib.h>
    
    int arr[] = {
         3, 6, 1, 8, 2, 5, 9, 4, 7 }; //无序的数组 
    int size = 0; //数组的大小，需要重新计算 
    
    void swap(int a, int b)
    {
        
    	//同上
    }
    
    //插入排序。在这里，从小到大排序或者从大到小排序都可以。 
    void insertSort(int low, int high)  
    {
        
    	//第0个数是有序的，所以从第1个数开始排序
    	for(int i = low + 1; i < high; i++)
    	{
        
    		int temp = arr[i]; //记录第i个数据
    		int j = i - 1; //从i - 1个数据开始往前查找
    		
    		//j的下标不能 < 0，且arr[j] > temp。
            //从小到大排序
    		while(j >= 0 && arr[j] > temp)
    		{
        
    			arr[j + 1] = arr[j]; //用前一个数字覆盖后一个数字
    			j--;
    		}		
    		arr[j + 1] = temp; //在正确的位置插入数据
    	}
    }
    
    int findMidMid(int low, int high) //找中间值的中间值
    {
        
    	if (high - low + 1 < 5)  //如果不足5个
        {
        
            insertSort(low, high); //插入排序         
            return (low + high) / 2; //返回low和high的中间值 
    
    		//移动位的方式是在CPU中进行，而不是内存中进行，效率较高。但是可读性较低。
            //return (low + high) >> 1; //部分网页上写成这样，意思是一样的。    
    }
    
    	//如果 ≥ 5个数据 
        int j = low - 1;
        for (int i = low; i <= high; i += 5)  //5个一组插入排序取中位数，并统一放在左侧
        {
        
            insertSort(i, i + 4);
            j++;
            swap(j, i + 2); //把中间值放在整个数组的最左侧，依次往右放置 
        }
        return findMidMid(low, j);  //直至仅出现一个的中位数
    }
    
    //快速排序进行划分的过程
    int Partion(int low, int high) 
    {
        
    	if (low > high) //递归的出口 
    	{
        
    		return -1;	
    	}
    	
    	int standardIndex = findMidMid(low, high); //找到最合适的基准数的下标
    	swap(standardIndex, low); //把最合适的基准数放到最左边
    
    	int standard = arr[low]; //最左边的元素作为基准 
    	int i = low; //确定范围 
    	int j = high;
    	
    	// 将大于基准数的元素交换到基准数的左边，小于基准数的元素交换到基准数的右边
    	while (i < j) 
    	{
        
    		while (i < j && arr[j] <= standard) 
    		{
        
    			j--;
    		}
    		while (i < j && arr[i] >= standard) 
    		{
        
    			i++;
    		}
    		if(i < j) //东东和虫虫没有相遇 
    		{
        
    			swap(i, j);
    		}
    	}
    	
    	//东东和虫虫相遇后 
    	arr[low] = arr[i];
    	arr[i] = standard;
    	return i; //返回基准数的正确的位置
    }
    
    void show() //显示数组 
    {
        
    	//同上
    }
    
    int BFPTR(int low, int high, int k)
    {
        
    	show();
    	printf("查找第%d大的数据: 查找范围:%d--%d，基准数是%d\r\n", k, arr[low], arr[high], arr[low]);
    	int standardIndex = Partion(low, high); //划分 
    	
    	if(standardIndex < 0)
    	{
        
    		printf("k > 数组中元素个数，出错\r\n");
    		return -1;
    	}
    	if (standardIndex == k) 
    	{
        
    		printf("基准数的下标是%d, 与k相等，所以要查找的数是：%d\r\n", standardIndex, arr[k]);
    		show();
    		return standardIndex;
    	}
    	else if (standardIndex > k) 
    	{
        
    		printf("基准数的下标%d > %d，在基准数的左边递归查找\r\n\r\n", standardIndex, k);
    		return BFPTR(low, standardIndex - 1, k); //缩小查找范围，继续递归查找
    	}
    	else
    	{
        
    		printf("基准数的下标%d < %d，在基准数的右边递归查找\r\n\r\n", standardIndex, k);
    		return BFPTR(standardIndex + 1, high, k); //缩小查找范围，继续递归查找	
    	}
    	printf("\r\n\r\n");
    }
    
    int main()
    {
        
        //同上
    }

运行结果如下：!

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]

我们可以看到，这里只进行了两次划分就找到了第1大的值。效率确实比原先的方法要高很多。这个算法比较难理解的是时间复杂度的计算，尤其是对5个元素的数组进行插入排序时，时间复杂度从O(N^2)变成O(1)的过程。如果这样也行，岂不是任何排序算法的时间复杂度都为O(1)了？

找中间值的中间值的过程也有一点点复杂，需要仔细理解这个算法的推导过程，体会算法精彩的地方：如果使用原始的快速排序的划分算法，平均时间复杂度为O(N)，但是最差的情况下变成O(N^2)。其实可以用优化快速排序的方法优化这个方法，但是不可靠 (不能保证所有情况下都不退化成O(N^2)，事实上，有对抗快速排序的数组/算法存在，用这个算法就可以让快速排序退化成冒泡排序)。线性查找解决了最差情况下，时间复杂度仍然为O(N)的关键问题。

ps: 在计算时间复杂度等地方，有的数字应该是上标，有的是下标，但都没法弄，我又懒得截图。大家将就着看吧。代码是没问题的，copy到Dev C++中就可以运行。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/ffbddddac5a143d882777745533911c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/5498475fd3a34695a9591eab3c44e335.png