荷兰国旗问题、快排以及BFPRT算法

荷兰国旗问题、快排以及BFPRT算法

荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)。

这个问题的解决思路是这样的，首先划定一个小于区域，其右边界为less，划定一个大于区域，其左边界为more。

从数组的第一个元素开始进行遍历，如果当前小于num，那么将这个数与小于区域外的第一个元素进行交换，并对当前位置的下一个元素进行判断；如果当前值大于num，那么将当前值与大于区域外的第一个元素进行交换，并且对交换来的元素进行判断；如果当前值等于num，那么对当前值的下一个元素进行判断。

void Netherlandsflag(vector<int> arr, int num)

{

	vector<int> res;

	int more = arr.size() ; //大于区域左边界

	int less = -1; //小于区域右边界

	int current = 0;

	while (current < more)

	{

		if (arr[current] < num)

		{

			swap(arr[current++], arr[++less]); //将当前值与小于区域下一个值进行交换，小于区域扩大

		}

		else if (arr[current]>num)

		{

			swap(arr[current], arr[--more]); //将当前值与大于区域下一个值进行交换，大于区域扩大，并对

		}                                    //交换来的数继续进行判断

		else //当前值等于num时，对下一个值进行判断

		{

			current++;

		}

	}

}

快排

快排的思路类似于荷兰国旗问题，挑选一个比较值，将小于比较值的放左边，大于比较值的放右边，等于比较值的放中间。

并对大于区域和小于区域进行同样的 *** 作。

void Quicksort(vector<int> &arr, int start, int end)

{

	if (start < end)

    {

		vector<int> edge = partition(arr, start, end);

		Quicksort(arr, start, edge[0]);

		Quicksort(arr, edge[1], end);

    }

}

vector<int> partition(vector<int> &arr, int start, int end) //类似于荷兰国旗问题

{

	int index = start;

	int less = start - 1;

	int more = end + 1;

	int num = arr[rand() % (end - start + 1) + start]; //随机选取数组中元素作为比较值

	while (index < more)

	{

		if (arr[index] < num)

		{

			swap(arr[index++], arr[++less]);

		}

		else if (arr[index]>num)

		{

			swap(arr[index], arr[--more]);

		}

		else

		{

			index++;

		}

	}

	vector<int> res{less, more}; //存储边界

    return res;

}

经典快排将每次的比较值都选择为arr[end]，这种方法的弊端在于它的时间复杂度是与数据状况有关。

举个例子，如果我们需要处理的数组为{1，2，3，4，5，6}，选择arr[end]作为比较值时，每次partition仅能将问题的规模减少一个，这样使得时间复杂度变为了O(N^2)。

而随机快排可以使得问题的期望达到O(N*logN)，其做法仅需要在经典快排的基础上，将数组中随机的一个数与arr[end]进行交换。

BFPRT算法

BFPRT算法是对上述的快排进行优化的，可以利用BFPRT算法求一个数组中第k大的值或第k小的值。

BFPRT对于随机快排的优化在于，随机选取一个元素变为选取中位数，它的步骤可以分为以下几步：

1. 将数组分为5个一组的多个数组，不足五个的形成一组。
   

   
   

2. 组内进行排序。
   

   
   

3. 每个组中位数取出构成新的数组。
   

   
   

4. 递归调用BFPRT直到得到一个数组只剩下一个数，返回这个数作为比较值。
   

   
   

int selectnum(vector<int> arr, int start, int end)

{

    if (start == end)

    {

        return arr[start];

    }

	int offset = (end - start + 1) % 5 == 0 ? 0 : 1; //不足5个数的形成一组

	int length = (end - start + 1) / 5 + offset;

	vector<int> median(length);

	for (int i = 0; i < median.size(); i++)

	{

		int startI = start + i * 5;

		int endI = startI + 4 < end ? (startI + 4) : end;//最后一组的endI为end

		median[i] = getmedian(arr, startI, endI); //可以选择插入排序选择排序等，数据规模不大于5

	}

	return select(median, 0, median.size() - 1); //递归调用

}

接下来解决求数组中第k小的值的问题：

1. 小于中位数的放左边，等于中位数的放中间，大于中位数的放右边
2. 如果k小于小于区域的右边界，那么在小于区域递归partition过程。
   

   
   

   如果k大于大于区域的左边界，那么在大于区域递归partition过程。
   

   
   

   如果刚好k处于等于区域中，返回中位数的值。
   

   
   

int MinKthbyBFPRT(vector<int> &arr, int start, int end, int k)

{

	if (start == end)

		return arr[start];

	int num = selectnum(arr, start, end);

	vector<int> edge = partition(arr, start, end, num);

	if (k > edge[0] && k < edge[1])

	{

		return num;

	}

	else if (k <= edge[0])

	{

		return BFPRT(arr, start, edge[0], k);

	}

	else

	{

		return BFPRT(arr, edge[1], end, k);

	}

}