劍指offer之partition算法

1 問題

 partition 算法:

從無(wú)序數(shù)組中選出樞軸點(diǎn) pivot，然后通過一趟掃描，以 pivot 為分界線將數(shù)組中其他元素分為兩部分，使得左邊部分的數(shù)小于等于樞軸，右邊部分的數(shù)大于等于樞軸（左部分或者右部分都可能為空），最后返回樞軸在新的數(shù)組中的位置。

如果原始數(shù)組為[5,9,2,1,4,7,5,8,3,6]，那么整個(gè)處理的過程如下圖

Partition 可不只用在快速排序中，還可以用于 Selection algorithm（在無(wú)序數(shù)組中尋找第K大的值）中.

 
2 代碼實(shí)現(xiàn)

我們按照算法需求簡(jiǎn)單實(shí)現(xiàn)如下

    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],如果遇到這種寫死數(shù)字的時(shí)候我們確認(rèn)下是否是可以用變量更加合適
        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 優(yōu)化

上面實(shí)現(xiàn)的效率很低，我們需要優(yōu)化，如果我們考慮用2個(gè)指針的思想，保持頭尾兩個(gè)指針向中間掃描，每次在頭部找到大于pivot的值，同時(shí)在尾部找到小于pivot的值，然后將它們做一個(gè)交換
1）第一種優(yōu)化代碼實(shí)現(xiàn)

    #include <iostream>
    #include <vector>
     
    using namespace std;
     
    /*
     *partition算法 記得如果這里是C++我們傳遞的是vector類型，我們記得要加引用，
     *不然改變不了數(shù)據(jù)，這里和java傳遞ArrayList不一樣，ArrayList作為參數(shù)可以改變集合里面的值，
     *所以C++如果函數(shù)傳遞非基本數(shù)據(jù)類型，一半都是帶引用的
     */
    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;
            }
            //這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
            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;
    }

運(yùn)行結(jié)果如下

    old data print
    5    9    2    1    4    7    5    8    3    6    
    after partitionOne
    3    4    2    1    5    7    5    8    9    6    
     
     

然后圖解每一步如下

 
2）第二種優(yōu)化代碼實(shí)現(xiàn)

我們使用交換函數(shù)，而不是數(shù)組賦值，和上面差不多,我們用swap函數(shù)的時(shí)候，我們單獨(dú)定義了2個(gè)變量i和j保存了start和end,這樣在后面的最后一個(gè)swap函數(shù)的時(shí)候進(jìn)行swap(vector[i], vector[start]);還有這個(gè)函數(shù)是返回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類型，我們記得要加引用，
     *不然改變不了數(shù)據(jù)，這里和java傳遞ArrayList不一樣，ArrayList作為參數(shù)可以改變集合里面的值，
     *所以C++如果函數(shù)傳遞非基本數(shù)據(jù)類型，一半都是帶引用的
     */
    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;
            }
            //這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
            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;
    }

運(yùn)行結(jié)果如下

    old data print
    5    9    2    1    4    7    5    8    3    6    
    after partitionOne
    4    3    2    1    5    7    5    8    9    6    

 

 
4 總結(jié)

我們使用partition算法的時(shí)候，從我們上面代碼第一次調(diào)用來(lái)看，我們選擇的第一個(gè)數(shù)字5作為中間軸，然后執(zhí)行一次后，我們的 partition函數(shù)返回的start或者i值都是4，然后我們最后一步把5也插入了vector[4]那里，就是說明我們左邊有4個(gè)值比當(dāng)前數(shù)字5作為中間軸都小，也能說明這左邊的4個(gè)值和中間軸數(shù)5都是數(shù)組里面最小的5個(gè)值，如果我們需要求出一個(gè)數(shù)組里面最小的5個(gè)值，我們只需要partition算法返回值是4就行，然后在左邊的數(shù)組的前5個(gè)數(shù)字就是這個(gè)數(shù)組里面最小的5個(gè)數(shù)，所以這里的數(shù)組里面最小的多少K個(gè)數(shù)確保partition返回的index或者start的關(guān)系是：index = K - 1; 或者start = K -1關(guān)系，也就是說partition函數(shù)返回index或者start值的時(shí)候，數(shù)組里面從坐標(biāo)0到index或者start的值就是數(shù)組里面最小的元素，也就是index+1個(gè)元素。
 

我們使用partition算法是雙指針?biāo)枷?br>

作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)