基于partition的递归

 partition算法可以应用在快速排序算法中,也可以应用到 Selection algorithm(在无序数组中寻找第K大的值)

Partition 实现

快速排序中用到的 partition 算法思想很简单,首先从无序数组中选出枢轴点 pivot,然后通过一趟扫描,以 pivot 为分界线将数组中其他元素分为两部分,使得左边部分的数小于等于枢轴,右边部分的数大于等于枢轴(左部分或者右部分都可能为空),最后返回枢轴在新的数组中的位置。

Partition 的一个直观简单实现如下(这里取数组的第一个元素为pivot):

// Do partition in arr[begin, end), with the first element as the pivot.
int partition(vector<int>&arr, int begin, int end){
    int pivot = arr[begin];
    // Last position where puts the no_larger element.
    int pos = begin;
    for(int i=begin+1; i!=end; i++){
        if(arr[i] <= pivot){
            pos++;
            if(i!=pos){
                swap(arr[pos], arr[i]);
            }
        }
    }
    swap(arr[begin], arr[pos]);
    return pos;
}

这种实现思路比较直观,但是其实并不高效。从直观上来分析一下,每个小于pivot的值基本上(除非到现在为止还没有遇见大于pivot的值)都需要一次交换,大于pivot的值(例如上图中的数字9)有可能需要被交换多次才能到达最终的位置。

如果我们考虑用 Two Pointers 的思想,保持头尾两个指针向中间扫描,每次在头部找到大于pivot的值,同时在尾部找到小于pivot的值,然后将它们做一个交换,就可以一次把这两个数字放到最终的位置。一种比较明智的写法如下:

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

Partition 应用

我们都知道经典的快速排序就是首先用 partition 将数组分为两部分,然后分别对左右两部分递归进行快速排序,过程如下:

void quick_sort(vector<int> &arr, int begin, int end){
    if(begin >= end - 1){
        return;
    }
    int pos = partition(arr, begin, end);
    quick_sort(arr, begin, pos);
    quick_sort(arr, pos+1, end);
}

虽然快排用到了经典的分而治之的思想,但是快排实现的前提还是在于 partition 函数。正是有了 partition 的存在,才使得可以将整个大问题进行划分,进而分别进行处理。

除了用来进行快速排序,partition 还可以用 O(N) 的平均时间复杂度从无序数组中寻找第K大的值。和快排一样,这里也用到了分而治之的思想。首先用 partition 将数组分为两部分,得到分界点下标 pos,然后分三种情况:

  • pos == k-1,则找到第 K 大的值,arr[pos];
  • pos > k-1,则第 K 大的值在左边部分的数组。
  • pos < k-1,则第 K 大的值在右边部分的数组。

下面给出基于迭代的实现(这里寻找第 k 小的数字):

int find_kth_number(vector<int> &arr, int k){
    int begin = 0, end = arr.size();
    assert(k>0 && k<=end);
    int target_num = 0;
    while (begin < end){
        int pos = partition(arr, begin, end);
        if(pos == k-1){
            target_num = arr[pos];
            break;
        }
        else if(pos > k-1){
            end = pos;
        }
        else{
            begin = pos + 1;
        }
    }
    return target_num;
}

该算法的时间复杂度是多少呢?考虑最坏情况下,每次 partition 将数组分为长度为 N-1 和 1 的两部分,然后在长的一边继续寻找第 K 大,此时时间复杂度为 O(N^2 )。不过如果在开始之前将数组进行随机打乱,那么可以尽量避免最坏情况的出现。而在最好情况下,每次将数组均分为长度相同的两半,运行时间 T(N) = N + T(N/2),时间复杂度是 O(N)。

在最好情况下,假设平均分成两半,那么kth元素要不在前一半,要不在后一半,只需要在其中一半寻找即可。所以期望复杂度是:O(n) + O(n/2) + O(n/4) + ... + O(1) = O(2n) = O(n)  (n+n/2+n/4+...+1可以用等比数列求和公式 = 2n)

 

参考:

https://selfboot.cn/2016/09/01/lost_partition/

 

 

 

 

 

 

原文地址:https://www.cnblogs.com/zkfopen/p/11175291.html