分治法求第k小元素

63 阅读 0 评论 42 点赞

我是靠谱客的博主完美唇彩，最近开发中收集的这篇文章主要介绍分治法求第k小元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法：http://www.cnblogs.com/chaofan/archive/2009/12/14/1623320.html

求一列数中的第k小元素，利用分治的策略进行递归求解。

首先随便指定一个数，这里我指定的是第一个数为第k小元素记为randK，将数组中其他的数与findK进行比较，比他小的放在左边，大的放在右边，如果randK左边的元素个数为k-1个，说明findK就是你所要找的元素，如果左边的元素个数>k-1，说明你要找的元素在左边的数中，继续使用相同的方法在左边的数中进行查找，如果左边的元素的个数<k-1,说明你要找的元素在右边的数中，则继续使用相同的办法在右边的数中进行查找。。。

代码：

#include <iostream>
using namespace std;

const int M = 999;
typedef struct Data 
{
	int data;
	bool flag;
}Mit[M];

int findP(int a [], int oP, int R)
{
	int randK = a[oP];
	int iL = oP + 1;
	int iR = R;
	while (true)
	{
		while (a[iL] < randK)
		{
			iL++;
		}
		while (a[iR] >= randK)
		{
			iR--;
		}
		if (iL >= iR)
		{
			break;
		}
		swap(a[iL], a[iR]);
	}
	swap(a[oP], a[iR]);
	return iR;
}

int findK(int a [], int oP, int n, int k)
{
	int find_k;
	int copy_k;
	find_k = findP(a, oP, n);
	copy_k = find_k - oP;
	if (k == copy_k)
	{
		return a[find_k];
	}
	if (k > copy_k)
	{
		return findK(a, find_k + 1, n, k - copy_k - 1);
	}
	if (k > copy_k)
	{
		return findK(a, oP, find_k - 1, k);
	}
	else
	{
		return 0;
	}
}

int main()
{
	int n;
	int k1, k2;
	Mit d;
	cout << "请输入无序列表的大小:" << endl;
	cin >> n;

	cout << "请输入无序列表中的所有元素" << endl;
	//输入无序列表中的所有元素
	for (int i = 0; i < n; i++)
	{
		d[i].flag = 1;
		cin >> d[i].data;
	}

	cout << "请输入k1, k2:" << endl;
	cin >> k1 >> k2;
	if (k1 < k2)
	{
		int temp = k1;
		k1 = k2;
		k2 = temp;
	}

	for (int i = 0; i < n; i++)
	{
		if (d[i].flag)
		{
			cout << d[i].data << endl;
		}
	}

	system("pause");
}