农村一区二区AV,中文字幕9/片,久久久久色

快速排序，堆排序和 $top\ k$ 問題一直都是非常經(jīng)典的算法知識點。并且他們在原理和算法思想上有相通的部分。這篇文章會簡要復(fù)習(xí)和總結(jié)這三個算法知識，并且給出我自己的 $c++$ 實現(xiàn)。

快速排序

快速排序顯然是最經(jīng)典的排序算法，期望時間復(fù)雜度為 $O(nlogn)$ ，實際上最壞情況下可能退化乘 $O(n^2)$ ，但是可以通過一些方法來避免或是減少最壞情況出現(xiàn)的概率。實際上快速排序相當(dāng)快。

partition函數(shù)

快速排序最為關(guān)鍵的是 $partition$ 函數(shù)，這個函數(shù)選出一個樞紐 $pivot$ 通過一次 $O(n)$ 掃描，將原序列分成左右兩部分，左邊部分的所有數(shù)都 $\leq pivot$ ，右邊部分的所有數(shù)都 $>pivot$ 。
$partition$ 函數(shù)的實現(xiàn)通過雙指針，左指針 $ptrl$ 指向的是下一個存放 $\leq pivot$ 的數(shù)的位置，右指針向右掃描，每當(dāng)找到一個 $\leq pivot$ 的數(shù) $x$ ，則執(zhí)行 $swap(x,*ptrl)$ ，即將這個數(shù)交換到左指針位置，然后 $ptrl++$ ，指向下一個存放的位置。

partition

template <typename T>
int partition(vector<T> &vec, int first, int last) //* 對于[begin,end]范圍內(nèi)的元素做partition操作
{
    int pos = rng() % (last - first + 1); //* 隨機選擇pivot，使得不能構(gòu)造出能達到最壞情況的數(shù)組
    swap(vec[first + pos], vec[last]);
    int i = first;             //* 第一個指針，指向下一個存放<=pivot元素的位置
    for (int j = i; j < last; j++) //* 第二個指針，遍歷所有元素
    {
        if (vec[j] < vec[last]) //* 當(dāng)前元素<=pivot，應(yīng)存到i所在的位置，同時維護左指針
        {
            swap(vec[j], vec[i]);
            i++;
        }
    }
    swap(vec[last], vec[i]); //* pivot放回i指向的地方，完成一次partition
    return i;        //* 返回partition結(jié)束后分割的位置
}

上面的代碼使用泛型對序列元素類型進行了抽象，可以進一步將第 $9$ 行中的比較抽象成一個使用者傳入的一個比較器。

快速排序?qū)崿F(xiàn)

了解了 $partition$ 函數(shù)的原理和實現(xiàn)，快速排序也就很簡單了。
快速排序每次對序列進行一次 $partition$ ，這時候左側(cè)元素一定都小于右側(cè)元素，但是左右兩側(cè)的內(nèi)部不一定有序，那么繼續(xù)對左右兩側(cè)規(guī)模更小的序列進行快速排序。
如果每次隨機選擇 $pivot$ ，那么遞歸層數(shù)一定不會太多，期望復(fù)雜度 $O(nlogn)$ 。
wikipedia中有詳細(xì)解釋
隨機選擇 $pivot$ 很大程度上避免了最壞情況的出現(xiàn)，但是仍然有極小可能出現(xiàn)，如果想完全避免最壞情況，可以考慮每次選擇 $pivot$ 的時候先 $O(n)$ 求出中位數(shù)來當(dāng) $pivot$ 。但是我懷疑這樣常數(shù)會變大。

代碼：

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(time(0));

template <typename T>
int partition(vector<T> &vec, int first, int last) //* 對于[begin,end]范圍內(nèi)的元素做partition操作
{
    int pos = rng() % (last - first + 1); //* 隨機選擇pivot，使得不能構(gòu)造出能達到最壞情況的數(shù)組
    swap(vec[first + pos], vec[last]);
    int i = first;             //* 第一個指針，指向下一個存放<=pivot元素的位置
    for (int j = i; j < last; j++) //* 第二個指針，遍歷所有元素
    {
        if (vec[j] < vec[last]) //* 當(dāng)前元素<=pivot，應(yīng)存到i所在的位置，同時維護左指針
        {
            swap(vec[j], vec[i]);
            i++;
        }
    }
    swap(vec[last], vec[i]); //* pivot放回i指向的地方，完成一次partition
    return i;        //* 返回partition結(jié)束后分割的位置
}

template <typename T>
void qsort(vector<T> &vec, int first, int last)
{
    if (first >= last)
        return;
    int pos = partition(vec, first, last);
    if (first < pos - 1) //* 遞歸對兩側(cè)繼續(xù)快排
        qsort(vec, first, pos - 1);
    if (pos + 1 < last)
        qsort(vec, pos + 1, last);
}

void test() //* 測試
{
    vector<int> vec1 = {3, 6, 1, 0, 9, 2, 8, 4, 7, 5};
    vector<string> vec2 = {"dyume", "hello_world", "arknights", "heapsort"};
    qsort(vec1, 0, vec1.size() - 1);
    qsort(vec2, 0, vec2.size() - 1);
    cout << "vec1 after sort:\n";
    for (const auto &x : vec1)
        cout << x << ' ';
    cout << '\n';
    cout << "vec2 after sort:\n";
    for (const auto &x : vec2)
        cout << x << ' ';
    cout << '\n';
}

int main()
{
    test();
}

堆排序

堆排序也是一種性能極佳的排序方法，復(fù)雜度 $O(nlogn)$ ，沒有最壞情況。事實上， $std::sort$ 使用的是一種將快速排序，堆排序和選擇排序相結(jié)合的算法，在快速排序遞歸深度過深可能出現(xiàn)最壞情況時會改用堆排序。

堆

既然是堆排序了，那么一定借助了堆這種數(shù)據(jù)結(jié)構(gòu)。
首先堆是一顆完全二叉樹，這使得堆能夠使用數(shù)組來表示，而不需要像其他樹形結(jié)構(gòu)一樣，通過指針來標(biāo)識父親節(jié)點和兒子節(jié)點。使用數(shù)組表示的樹形結(jié)構(gòu)顯然更加方便簡潔。
假設(shè)堆共有 $n$ 個節(jié)點，堆的根存放在 $0$ 號節(jié)點，每個節(jié)點 $i$ 的左右兒子分別是 $2*i+1$ 和 $2*i+2$ 號節(jié)點。每個節(jié)點 $i$ 的父親則是 $\lfloor \frac{i}{2}-1 \rfloor$ 號節(jié)點。通過這些數(shù)量關(guān)系就可以通過編號來在樹上隨意跳轉(zhuǎn)。

堆的數(shù)組表示

其次，堆滿足性質(zhì)：以大頂堆為例，每個節(jié)點的孩子的值都 $\leq$ 節(jié)點的值。這樣保證了堆的頂端一定是最大的。

堆的調(diào)整

堆的向下調(diào)整是堆較為關(guān)鍵的行為。當(dāng)堆的頂部發(fā)生了改變，可能首部元素被取走，或者是發(fā)生了改變，那么可以從頂部向下調(diào)整來使堆恢復(fù)。
利用堆的性質(zhì)，如果當(dāng)前節(jié)點的值小于其孩子時，可以選出孩子中其中較大的一個與該節(jié)點進行交換，然后繼續(xù)處理被交換的那個孩子。

向下調(diào)整

從網(wǎng)上扒了一張向下調(diào)整的圖解，這圖里的是小頂堆。

代碼：

template <typename T>
void adjust(vector<T> &vec, int pos, int len) //* pos位置的元素向下調(diào)整，大頂堆
{
    for (int child = pos * 2 + 1; child < len; pos = child, child = child * 2 + 1) //* 維護當(dāng)前位置以及左孩子的位置
    {
        if (child + 1 < len && vec[child + 1] > vec[child]) //* 如果右孩子合法且更加大，則替換為右孩子
            child++;
        if (vec[pos] >= vec[child]) //* 如果當(dāng)前已經(jīng)比兩個孩子都大了則退出
            break;
        swap(vec[pos], vec[child]); //* 否則交換值，繼續(xù)對孩子調(diào)整
    }
}

堆排序的實現(xiàn)

堆排序分為兩個步驟。

建堆：將無序的序列視為一個堆，從最后一個不是葉子的節(jié)點開始向下調(diào)整。每次調(diào)整相當(dāng)于將以該節(jié)點為根的子樹調(diào)整完畢。從最后一個不是葉子的節(jié)點開始到最開始的節(jié)點，每個都做一遍向下調(diào)整，調(diào)整完后就形成了一個堆。
排序：每次從堆的頂端取走一個元素，從后往前依次放置。由于堆的性質(zhì)，每次取走的必定是剩下的序列中最大的元素，這樣當(dāng)堆被取完，排序自然就完成了。

#include <bits/stdc++.h>
using namespace std;

template <typename T>
void adjust(vector<T> &vec, int pos, int len) //* pos位置的元素向下調(diào)整，大頂堆
{
    for (int child = pos * 2 + 1; child < len; pos = child, child = child * 2 + 1) //* 維護當(dāng)前位置以及左孩子的位置
    {
        if (child + 1 < len && vec[child + 1] > vec[child]) //* 如果右孩子合法且更加大，則替換為右孩子
            child++;
        if (vec[pos] >= vec[child]) //* 如果當(dāng)前已經(jīng)比兩個孩子都大了則退出
            break;
        swap(vec[pos], vec[child]); //* 否則交換值，繼續(xù)對孩子調(diào)整
    }
}
template <typename T>
void heapsort(vector<T> &vec) //* 原地排序，改變輸入數(shù)組，時間復(fù)雜度O(nlogn)，空間O(1)
{
    int sz = vec.size();
    for (int i = sz / 2 - 1; i >= 0; i--) //* 建堆過程，從最后一個不是葉子的元素開始向下調(diào)整
        adjust(vec, i, sz);
    for (int i = sz - 1; i >= 0; i--) //* 排序過程，每次從堆中取出最大的一個元素，然后調(diào)整
    {
        swap(vec[i], vec[0]);
        adjust(vec, 0, i);
    }
}

void test() //* 測試
{
    vector<int> vec1 = {3, 6, 1, 0, 9, 2, 8, 4, 7, 5};
    vector<string> vec2 = {"dyume", "hello_world", "arknights", "heapsort"};
    heapsort(vec1);
    heapsort(vec2);
    cout << "vec1 after sort:\n";
    for (const auto &x : vec1)
        cout << x << ' ';
    cout << '\n';
    cout << "vec2 after sort:\n";
    for (const auto &x : vec2)
        cout << x << ' ';
    cout << '\n';
}

int main()
{
    test();
}

top k 問題

$top\ k$ 問題也是非常常見的問題，比如在一堆玩家中需要選出分?jǐn)?shù)最高的幾個玩家顯示在排行榜上，當(dāng)玩家數(shù)量級非常多時，算法的復(fù)雜度直接影響了運行的速度。而將這個問題與堆排序和快速排序放在一起的原因是：他們其中蘊含的一些算法思想是類似的。

先給出幾種復(fù)雜度較高的算法：

排序

先對所有元素進行一次排序，然后選出前 $k$ 個元素，時間復(fù)雜度 $O(nlogn)$ 。
我們其實只需要前 $k$ 個最大的元素，至于所有元素是否有序，甚至這前 $k$ 個元素是否有序和我們需要的關(guān)系不大。

排序

暴力

找 $k$ 次最大的元素。時間復(fù)雜度 $O(nk)$ 。這顯然不太行， $k$ 很小只有個位數(shù)的時候大概行吧。。。

暴力

然后引出兩個較為優(yōu)秀的解決方案：堆和 $partition$

堆

因為元素是否有序和 $top\ k$ 無關(guān)，我們可以想到堆這種數(shù)據(jù)結(jié)構(gòu)，堆只滿足當(dāng)前節(jié)點的值 $\geq$ 孩子的值。所以我們可以維護一個小頂堆，那么堆頂一定是堆中最小的元素，然后逐個遍歷所有元素，如果有 $>$ 堆頂?shù)脑兀敲催M行替換，然后進行一次向下調(diào)整，那么堆中保存的就是到目前為止最大的 $k$ 個元素。
時間復(fù)雜度 $O(nlogk)$ ，因為每次向下調(diào)整最多進行 $logk$ 次交換。

建堆

維護

結(jié)果

堆的一個好處在于它是一種動態(tài)的數(shù)據(jù)結(jié)構(gòu)，假設(shè)當(dāng)前數(shù)據(jù)又新進了一個元素，那么不需要重新做一次 $top\ k$ ，只需要維護當(dāng)前堆即可。

partition

最后一種方法利用了快速排序中 $partition$ 的思想，期望復(fù)雜度為 $O(n)$ 。
單次 $partition$ 能夠?qū)⑿蛄蟹殖蓛刹糠?，這兩部分整體是有序的，但是兩部分內(nèi)部并不有序，但是這樣也足夠了。假設(shè)當(dāng)前這次 $partition$ 選出的值是 $pivot$ ，那么 $partition$ 后我們能夠知道有多少個元素 $\geq pivot$ ，假設(shè)是 $pos$ 個。

如果 $pos <=k$ ，那么說明 $partition$ 右部的元素數(shù)量還不夠，還得在左邊繼續(xù)選出 $k-pos$ 個，那么對左側(cè)繼續(xù) $partition$ 。
否則說明 $partition$ 右側(cè)的元素太多了，在 $pos$ 個元素中只需要 $k$ 個就夠了，那么對右側(cè)繼續(xù) $partition$ 。

partition

如果每次 $pivot$ 都是隨機選擇的，那么遞歸層數(shù)不會太多，這個遞歸的層數(shù)，可以考慮成二分查找到 $k$ 所用的次數(shù)，而每次遞歸所執(zhí)行的區(qū)間長度是不斷減少的，所以期望復(fù)雜度是 $O(n)$ 。
可以對比一下快速排序的復(fù)雜度計算，同樣是遞歸大概 $logn$ 次,但是每次都要 $O(n)$ 搞一層，那么總體復(fù)雜度就是 $O(nlogn)$ 了，而這里的算法每層不是 $O(n)$ ，而是跟著遞歸層數(shù)減少的。這就是分治法和減治法在時間復(fù)雜度上的區(qū)別。

代碼：

#include <bits/stdc++.h>
using namespace std;

/*
template <typename T>
void adjust(vector<T> &vec, int pos, int len)
{
    for (int l = pos * 2 + 1; l < len; pos = l, l = l * 2 + 1)
    {
        if (l + 1 < len && vec[l + 1] < vec[pos])
            l++;
        if (vec[pos] <= vec[l])
            break;
        swap(vec[pos], vec[l]);
    }
}

template <typename T>
vector<T> topk(vector<T> &vec, int k)
{
    assert(k <= vec.size());
    vector<int> ans(vec.begin(), vec.begin() + k);
    for (int i = k / 2 - 1; i >= 0; i--)
        adjust(ans, i, k);

    for (int i = k; i < vec.size(); i++)
    {
        if (vec[i] > ans[0])
        {
            ans[0] = vec[i];
            adjust(ans, 0, k);
        }
    }
    return ans;
}
*/

mt19937 rng(time(nullptr));

template <typename T>
int partition(vector<T> &vec, int begin, int end, int flag = -1)
{
    int pos = begin + rng() % (end - begin + 1);
    if (flag != -1)
        pos = flag;
    swap(vec[pos], vec[end]);
    int i = begin;
    for (int j = begin; j < end; j++)
    {
        if (vec[j] >= vec[end])
        {
            swap(vec[j], vec[i]);
            ++i;
        }
    }
    swap(vec[i], vec[end]);
    return i;
}

template <typename T>
int getk(vector<T> &vec, int k, int begin, int end)
{
    if (begin == end)
        return begin;
    int pos = partition(vec, begin, end);
    int cnt = pos - begin + 1;
    if (cnt == k)
        return pos;
    else if (cnt > k)
        return getk(vec, k, begin, pos - 1);
    else
        return getk(vec, k - cnt, pos + 1, end);
}

template <typename T>
void topk(vector<T> &vec, int k)
{
    int pos = getk(vec, k, 0, vec.size() - 1);
    partition(vec, 0, vec.size() - 1, pos);
}

void test()
{
    vector<int> vec = {3, 6, 1, 0, 9, 2, 8, 4, 7, 5};

    topk(vec, 5);
    for (const auto &x : vec)
        cout << x << ' ';
    cout << endl;
}

int main()
{
    test();
}

上面被注釋掉的是堆的實現(xiàn)，由于沒有做封裝，兩種實現(xiàn)調(diào)用的方法參數(shù)有些不同。

先寫到這里吧，要是有時間再進行補充和完善，從網(wǎng)上偷了不少圖，尤其是從架構(gòu)師之路上的一篇文章，學(xué)到了許多，這篇文章算是我對這幾個問題的一個總結(jié)，網(wǎng)上將這三個問題放在一起講的文章也比較少，但他們內(nèi)在的算法原理其實是相關(guān)的，希望能幫到一些讀者。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

從快速排序，堆排序到top k問題

從快速排序，堆排序到top k問題

快速排序

partition函數(shù)

快速排序?qū)崿F(xiàn)

堆排序

堆

堆的調(diào)整

堆排序的實現(xiàn)

top k 問題

排序

暴力

堆

partition

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

從快速排序，堆排序到top k問題

快速排序

partition函數(shù)

快速排序?qū)崿F(xiàn)

堆排序

堆

堆的調(diào)整

堆排序的實現(xiàn)

top k 問題

排序

暴力

堆

partition

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

從快速排序，堆排序到top k問題