使用快排一次划分求第k小、使用优先级队列、使用堆

落日映苍穹つ 2022-11-11 14:59 102阅读 0赞

快排

#include <iostream>
    using namespace std;
    
    /**************************************
    * 
    * Partition() 快排的一次划分函数
    * 
    */
    
    
    // 把小的插入头部位置，可用于链表
    int Partition(int* ar, int left, int right) {
        
    	int i = left - 1, j = left;
    	int tmp = ar[j];
    	while (j <= right) {
        
    		if (ar[j] <= tmp) {
        
    			std::swap(ar[i + 1], ar[j]);
    			i += 1;
    		}
    		j += 1;
    	}
    	std::swap(ar[left], ar[i]);
    	return i;
    }
    
    // 双指针单方向推进
    int Partition1(int* ar, int left, int right)
    {
        
    	int i = left, j = left + 1;
    	int tmp = ar[i];
    	while (i < right && j < right)
    	{
        
    		while (j <= right && ar[j] <= tmp) j++;	// 大值
    		if (j > right) break;
    		i = j + 1;
    		while (i <= right && ar[i] > tmp) i++;	// j后小值
    		if (i > right) break;
    		std::swap(ar[i], ar[j]);
    		//j++;
    	}
    	std::swap(ar[j - 1], ar[left]);
    	return j - 1;
    }
    
    // 双指针，两边夹逼推进
    int Partition2(int* ar, int left, int right)
    {
        
    	int i = left, j = right;
    	int tmp = ar[i];
    	while (i < j)
    	{
        
    		while (i < j && ar[j] > tmp) j--;
    		if (i >= j) break;
    		while (i < j && ar[i] <= tmp) i++;
    		if (i >= j) break;
    		std::swap(ar[i], ar[j]);
    	}
    	std::swap(ar[i], ar[left]);
    	return i;
    }
    
    
    // 快排中间层，递归调用一次划分
    void QuickPass(int* ar, int left, int right)
    {
        
    	if (left < right)
    	{
        
    		int pos = Partition(ar, left, right);
    		QuickPass(ar, 0, pos - 1);
    		QuickPass(ar, pos + 1, right);
    	}
    }
    // 快排接口
    void QuickSort(int* ar, int n)
    {
        
    	if (nullptr == ar || n < 1) return;
    	QuickPass(ar, 0, n - 1);
    }
    
    int main()
    {
        
    	int arr[] = {
         4,5,2,3,4,4,3,1,7,8,4,9,10,6 };
    	QuickSort(arr, sizeof(arr) / sizeof(arr[0]));
    	for (int a : arr)
    		std::cout << a << ' ';
    	std::cout << std::endl;
    	return 0;
    }

> 有关快排优化：参考：[万字长文带你走进快速排序的前世今生【拓跋阿秀】][Link 1]
> 
> 1.  非递归
> 2.  优化基准选取位置，如三位取中法等
> 3.  设定一个阈值，在阈值范围内使用插入排序（插入排序在元素比较少时效率最高）
> 4.  三向切分。

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

使用快排的的一次划分，我们可以实现寻找无序数列中的第K小。

#include <iostream>
    using namespace std;
    int OnePartition(int* ar, int left, int right)
    {
        
    	int midVal = ar[left];		// 基准
    	while (left < right)
    	{
        
    		while (left < right)
    		{
        
    			if (ar[right] >= midVal) right--;
    			else {
        
    				swap(ar[right], ar[left++]); break;
    			}
    		}
    		while (left < right)
    		{
        
    			if (ar[left] <= midVal) left++;
    			else {
        
    				swap(ar[left], ar[right--]); break;
    			}
    		}
    	}
    	return left;
    }
    int Select_K(int* ar, int left, int right, int pos)
    {
        
    	int i = OnePartition(ar, left, right);
    	if (i < pos - 1) i = Select_K(ar, i + 1, right, pos);	// 右边
    	else if (i > pos - 1) i = Select_K(ar, left, i - 1, pos);	//左边
    	else return ar[i];
    }
    
    
    int main()
    {
        
    	int arr[] = {
         67,12,89,23,90,100 ,34,78,56,45 };
    
    	int n = sizeof(arr) / sizeof(arr[0]);
    	//cout << Cpair_ar(arr, n);
    	for (int i = 1; i < 11; i++)
    		cout << i << ":  " << Select_K(arr, 0, n - 1, i) << endl;
    
    	return 0;
    }
    
    /*
    	输出：
    			1:  12
    			2:  23
    			3:  34
    			4:  45
    			5:  56
    			6:  67
    			7:  78
    			8:  89
    			9:  90
    			10:  100
    */

除此之外，我们可以使用优先级队列，或直接使用数据结构堆。

优先级队列，大数优先级高（底层大根堆实现）。使用小数优先级高的方式也可以实现下列算法。

#include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    
    // 第k大
    int KthLargest(int arr[], int n, int k)
    {
        
    	if (nullptr == arr || n <= 0 || k > n) return -1;
    
    	//priority_queue<int> pq;	// 默认产生大根堆,数据大的优先
    	priority_queue<int, vector<int>, less<int>> pq;
    
    	for (int i = 0; i < n; i++)
    	{
        
    		pq.push(arr[i]);	// 把数据加入优先级队列中
    	}
    	// 把第1大，第2大，第3....，到第k次时为第k大
    	while (k > 1)
    	{
        
    		pq.pop();
    		k--;
    	}
    
    	return pq.top();
    }
    // 第k小
    int KthSmall(int arr[], int n, int k)
    {
        
    	if (nullptr == arr || n <= 0 || k > n) return -1;
    
    	priority_queue<int> pq;
    
    	for (int i = 0; i < n; i++)
    	{
        
    		pq.push(arr[i]);	// 把数据加入优先级队列中
    	}
    	k = n - k + 1;	// 求第k小，把n-k+1的大数据出队，剩下的就是第k小
    	while (k > 1)
    	{
        
    		pq.pop();
    		k--;
    	}
    
    	return pq.top();
    }
    
    int main()
    {
        
    	int arr[] = {
         67,12,89,23,90,100 ,34,78,56,45 };
    
    	int n = sizeof(arr) / sizeof(arr[0]);
    	for (int i = 1; i <= n; i++)
    		cout << i << ":\t small " << KthSmall(arr, n, i)
    		<< "\t big" << KthLargest(arr, n, i) << endl;
    
    	return 0;
    }
    /*
    	输出：
    		1:       small 12        big100
    		2:       small 23        big90
    		3:       small 34        big89
    		4:       small 45        big78
    		5:       small 56        big67
    		6:       small 67        big56
    		7:       small 78        big45
    		8:       small 89        big34
    		9:       small 90        big23
    		10:      small 100       big12
    
    */

直接使用数据结构堆。

#include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    
    // 第k大
    int KthLargest(int arr[], int n, int k)
    {
        
    	if (nullptr == arr || n <= 0 || k > n) return -1;
    
    	// std::make_heap(arr, arr + n);		// 在一个迭代器范围内构造一个堆（默认最大堆）
    	std::make_heap(arr, arr + n, less<int>());		// 创建大根堆
    
    	while (k > 1)
    	{
        
    		pop_heap(arr, arr + n);			// 弹出堆顶元素，并把它放到末尾位置
    		n--;
    		make_heap(arr, arr + n, less<int>());	// 将剩余元素调整为堆
    		k--;
    	}
    	return arr[0];
    }
    // 第k小
    int KthSmall(int arr[], int n, int k)
    {
        
    	if (nullptr == arr || n <= 0 || k > n) return -1;
    	//n = n - 1;	// 将长度变成下标
    	std::make_heap(arr, arr + n, greater<int>());		// 创建小根堆
    
    	while (k > 1)
    	{
        
    		pop_heap(arr, arr + n);			// 弹出堆顶元素，并把它放到末尾位置
    		n--;
    		make_heap(arr, arr + n, greater<int>());	// 将剩余元素调整为堆
    		k--;
    	}
    	return arr[0];
    }
    
    int main()
    {
        
    	int arr[] = {
         67,12,89,23,90,100 ,34,78,56,45 };
    	int brr[] = {
         67,12,89,23,90,100 ,34,78,56,45 };
    
    	int n = sizeof(arr) / sizeof(arr[0]);
    	for (int i = 1; i <= n; i++)
    		cout << i << ":\t small " << KthSmall(arr, n, i)
    		<< "\t big" << KthLargest(arr, n, i) << endl;
    
    	return 0;
    }
    
    
    /*
    	输出：
    		1:       small 12        big100
    		2:       small 23        big90
    		3:       small 34        big89
    		4:       small 45        big78
    		5:       small 56        big67
    		6:       small 67        big56
    		7:       small 78        big45
    		8:       small 89        big34
    		9:       small 90        big23
    		10:      small 100       big12
    */

[Link 1]: https://mp.weixin.qq.com/s/KcONJpqlWpVYnzY5bomzWg