Partition算法剖析

时间:2021-01-10 11:09:58

partition算法从字面上就非常好理解,就是分割算法嘛!简单讲就是可以把数组按照一定的分成几个部分,其中最常见的就是快速排序中使用的partition算法,这是一个二分partition算法,将整个数组分解为小于某个数和大于某个数的两个部分,然后递归进行排序算法。

上述只是二分partition算法,我们还会使用三分partition算法,三分partition也有这非常重要的应用。往往我们更多的关注点是快速排序算法等各种算法,以及时间复杂度等这些东西,今天我们专门讨论一下partition分割算法的一些应用。

二分 Partition算法

二分partition算法是我们最常使用的,尤其在快速排序中使用最为常见。常见的partition算法有如下两种实现思路:

思路I

算法思路

  • 使用第一个数组元素作为枢轴点,即为pivot;
  • 使用一个指针去扫描整个数组,凡是小于pivot的全部放到数组左端;
  • 最后讲pivot放到数组中间的位置,pivot左边全部都是小于他的数字,右边反之,最后返回pivot的位置信息;

代码

int partition(vector<int> &nums, int begin, int end)
{
int pivot = nums[begin];
int pos = begin;
for(int i = begin+1; i < end; ++i)
{
if(nums[i] <= pivot)
swap(nums[++pos],nums[i]);
}
swap(nums[pos], nums[begin]);
return pos;
}

思路II

算法思路

  • 就如快速排序中最常使用的那样,使用两个指针分别从头部和尾部进行扫描,头部遇到大于pivot的数和尾部遇到小于pivot的数进行交换;
  • 使用了两个指针,效率更高一点;

代码

int partition(vector<int> &nums, int begin, int end)
{
int pivot = nums[begin];
while(begin < end)
{
while(begin < end && nums[--end] >= pivot);
nums[begin] = nums[end];
while(begin < end && nums[++begin] <= pivot);
nums[end] = nums[begin];
}
nums[begin] = pivot;
return begin;
}

二分partition算法应用

快速排序算法

经典的快速排序算法,直接上代码:

代码

void quickSort(vector<int> &nums, int begin, int end)
{
if(end - begin <= 1)
return;
int mid = partition(nums, begin, end); quickSort(nums, begin, mid);
quickSort(nums, mid, end);
}

数组第K大数值查询

这也是LeetCode中的一道例题,非常适合使用partition算法进行解决,问题链接215. Kth Largest Element in an Array

解题思路

  • 首先可以通过排序进行求解,简单暴力;
  • 不断使用partition算法进行迭代查找;

代码

class Solution
{
public:
int findKthLargest(vector<int> &nums, int k)
{
int len = nums.size();
int res = 0;
int left = 0;
int right = len;
while(left < right)
{
int pos = partition(nums, left, right);
if(pos == len-k)
{
res = nums[pos];
break;
}
else if(pos < len-k)
left = pos+1;
else
right = pos;
}
return res;
}
int partition(vector<int> &nums, int begin, int end)
{
int pivot = nums[begin];
while(begin < end)
{
while(begin < end && nums[--end] >= pivot);
nums[begin] = nums[end];
while(begin < end && nums[++begin] <= pivot);
nums[end] = nums[begin];
}
nums[begin] = pivot;
return begin;
}
};

三分paitition算法

三分partition算法,顾名思义,也就是将数组按照规则分为三个部分,比如非常经典的国旗问题Dutch national flag problem,就是要给定的红、白、蓝三色随机颜色小球按照红、白、蓝的顺序进行排序,利用partition算法,使用一个指针进行扫描,红色的小球就用swap()放到左边,白色的保持位置不变,蓝色的同样使用swap()放到右边,最后就得到要求的序列了。

Dutch National Flag Problem

LeetCode中有恰好有这么一个题:75. Sort Colors

解题思路

  • 就使用三分partition算法进行求解就可以了!

代码

class Solution
{
public:
void sortColors(vector<int> &nums)
{
int len = nums.size();
int left = 0;
int right = len - 1;
for(int i = 0; i < len; ++i)
{
if(i > right)
break;
if(nums[i] == 1)
continue;
else if(nums[i] == 0)
{
swap(nums[i], nums[left]);
left++;
}
else
{
swap(nums[i], nums[right]);
right--;
i--;
}
}
}
};

进阶应用

LeetCode 324. Wiggle Sort II

LeetCode中的第324题中也同样可以使用三分partition算法,该题的discuss中,StefanPochmann大神提出一种O(n)+O(1)复杂度的高效算法,原链接为:

324. Wiggle Sort II

Discuss

解题思路

  • 使用partition算法获取数组的中位数,这个思路同找第k大的数,这里作者用了c++中的nth_element()函数;
  • 使用宏定义的方式#define A(i) nums[(1+2*(i)) % (n|1)]A()的前半部分对应nums中下标为奇数的元素,后半部分为偶数,即奇数 + 偶数
  • 使用三分partition算法对A()进行排序,使其前半部分大于后半部分,即在nums中奇数部分 > 偶数部分
  • 最终达到的效果为 0 < 1 > 2 < 3 > 4 < 5 ...
  • 注意这里需要的是奇数>偶数,所以进行partition的时候大于pivot枢轴值的要放到前面;

#define A(i) nums[(1+2*(i)) % (n|1)]的作用如下所示:

假设有0, 1, 2, 3, 4, 5, 6, 7, 8, 9共10个数据,则使用A()进行映射之后的结果为:

A(0) -> nums[1].

A(1) -> nums[3].

A(2) -> nums[5].

A(3) -> nums[7].

A(4) -> nums[9].

A(5) -> nums[0].

A(6) -> nums[2].

A(7) -> nums[4].

A(8) -> nums[6].

A(9) -> nums[8].

代码

class Solution
{
public:
void wiggleSort(vector<int>& nums)
{
int n = nums.size(); // Find a median.
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr; // Index-rewiring.
#define A(i) nums[(1+2*(i)) % (n|1)] // 3-way-partition-to-wiggly in O(n) time with O(1) space.
int i = 0, j = 0, k = n - 1;
while (j <= k)
{
if (A(j) > mid)
swap(A(i++), A(j++));
else if (A(j) < mid)
swap(A(j), A(k--));
else
j++;
}
}
};

Partition算法剖析Githubhttps://github.com/haoyuanliu

Partition算法剖析个人博客http://haoyuanliu.github.io/

个人站点,欢迎访问,欢迎评论!