剑指offer之partition算法 / 开普饭

1 问题

partition 算法:

从无序数组中选出枢轴点 pivot，然后通过一趟扫描，以 pivot 为分界线将数组中其他元素分为两部分，使得左边部分的数小于等于枢轴，右边部分的数大于等于枢轴（左部分或者右部分都可能为空），最后返回枢轴在新的数组中的位置。

如果原始数组为[5,9,2,1,4,7,5,8,3,6]，那么整个处理的过程如下图

Partition 可不只用在快速排序中，还可以用于 Selection algorithm（在无序数组中寻找第K大的值）中.

2 代码实现

我们按照算法需求简单实现如下

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(vector<int>& vector, int start, int end)
{
    if (vector.size() < 1)
    {
        std::cout << "vector is null or vector size is not normal" << std::endl;
        return -1;
    }
    //一般我们写代码不要这样写死，pivot = vector[0],如果遇到这种写死数字的时候我们确认下是否是可以用变量更加合适
    int pivot = vector[start];
    int index = 0;
    for (int i = start + 1; i < end; ++i)
    {
        if (vector[i] <= pivot)
        {
            ++index;
            swap(vector[index], vector[i]);
        }
    }
    swap(vector[0], vector[index]);
    return index;
}

3 优化

上面实现的效率很低，我们需要优化，如果我们考虑用2个指针的思想，保持头尾两个指针向中间扫描，每次在头部找到大于pivot的值，同时在尾部找到小于pivot的值，然后将它们做一个交换

1）第一种优化代码实现

#include <iostream>
#include <vector>

using namespace std;

/*
 *partition算法 记得如果这里是C++我们传递的是vector类型，我们记得要加引用，
 *不然改变不了数据，这里和java传递ArrayList不一样，ArrayList作为参数可以改变集合里面的值，
 *所以C++如果函数传递非基本数据类型，一半都是带引用的
 */
int partitionOne(vector<int>& vector, int start, int end)
{
    if (start > end)
    {
        std::cout << "vector is empty or start > end" << std::endl;
        return -1;
    }
    int pivot = vector[start];
    while (start < end)
    {
        //我们先从尾巴开始
        while (start < end && pivot <= vector[end])
        {
            --end;
        }
        //这里用的数组赋值，而不是直接用swap交换函数，那么下面的2步也是用数组赋值，而不是用swap交换函数
        vector[start] = vector[end];
        while (start < end && pivot >= vector[start])
        {
            ++start;
        }
        vector[end] = vector[start];
    }
    vector[start] = pivot;
    return start;
}

void printVector(vector<int> v)
{
    for (int i = 0; i < v.size(); ++i)
    {
        std::cout << v[i] << "\t";
    }
    std::cout << std::endl;
}

int main()
{
    vector<int> v1;
    //[5,9,2,1,4,7,5,8,3,6]
    v1.push_back(5);
    v1.push_back(9);
    v1.push_back(2);
    v1.push_back(1);
    v1.push_back(4);
    v1.push_back(7);
    v1.push_back(5);
    v1.push_back(8);
    v1.push_back(3);
    v1.push_back(6);

    std::cout << "old data print " << std::endl;
    printVector(v1);

    partitionOne(v1, 0, v1.size() - 1);

    std::cout << "after partitionOne" << std::endl;
    printVector(v1);
    return 0;
}

运行结果如下

old data print
5921475836
after partitionOne
3421575896

然后图解每一步如下

2）第二种优化代码实现

我们使用交换函数，而不是数组赋值，和上面差不多,我们用swap函数的时候，我们单独定义了2个变量i和j保存了start和end,这样在后面的最后一个swap函数的时候进行swap(vector[i], vector[start]);还有这个函数是返回i,而不是start,不然就有问题。

#include <iostream>
#include <vector>

using namespace std;

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void printVector(vector<int> v)
{
    for (int i = 0; i < v.size(); ++i)
    {
        std::cout << v[i] << "\t";
    }
    std::cout << std::endl;
}

/*
 *partition算法 记得如果这里是C++我们传递的是vector类型，我们记得要加引用，
 *不然改变不了数据，这里和java传递ArrayList不一样，ArrayList作为参数可以改变集合里面的值，
 *所以C++如果函数传递非基本数据类型，一半都是带引用的
 */
int partitionTwo(vector<int>& vector, int start, int end)
{
    if (start > end)
    {
        return -1;
    }
    int i = start;
    int j = end;
    int pivot = vector[start];
    while (i < j)
    {
        //我们先从尾巴开始
        while (i < j && pivot <= vector[j])
        {
            --j;
        }
        //这里用的数组赋值，而不是直接用swap交换函数，那么下面的2步也是用数组赋值，而不是用swap交换函数
        while (i < j && pivot >= vector[i])
        {
            ++i;
        }
        swap(vector[i], vector[j]);
    }
    swap(vector[i], vector[start]);
    //printVector(vector);
    return i;
}

int main()
{
    vector<int> v1;
    //[5,9,2,1,4,7,5,8,3,6]
    v1.push_back(5);
    v1.push_back(9);
    v1.push_back(2);
    v1.push_back(1);
    v1.push_back(4);
    v1.push_back(7);
    v1.push_back(5);
    v1.push_back(8);
    v1.push_back(3);
    v1.push_back(6);

    std::cout << "old data print " << std::endl;
    printVector(v1);

    partitionTwo(v1, 0, v1.size() - 1);

    std::cout << "after partitionOne" << std::endl;
    printVector(v1);
    return 0;
}

运行结果如下

old data print
5921475836
after partitionOne
4321575896

4 总结

我们使用partition算法的时候，从我们上面代码第一次调用来看，我们选择的第一个数字5作为中间轴，然后执行一次后，我们的 partition函数返回的start或者i值都是4，然后我们最后一步把5也插入了vector[4]那里，就是说明我们左边有4个值比当前数字5作为中间轴都小，也能说明这左边的4个值和中间轴数5都是数组里面最小的5个值，如果我们需要求出一个数组里面最小的5个值，我们只需要partition算法返回值是4就行，然后在左边的数组的前5个数字就是这个数组里面最小的5个数，所以这里的数组里面最小的多少K个数确保partition返回的index或者start的关系是：index = K - 1; 或者start = K -1关系，也就是说partition函数返回index或者start值的时候，数组里面从坐标0到index或者start的值就是数组里面最小的元素，也就是index+1个元素。

我们使用partition算法是双指针思想

剑指offer之partition算法