名次在生活中非常常見, 看到名次, 大家可能第一時間就想起了大家在學校的時候, 成績的名次; 大家也可能想起對於某一類東西的評測名次...

要想有名次, 就必須有權的概念. 比如一個班裡的所有學生的名次, 以最終的成績為權, 然後進行名次排序

任意給定某個串列, 串列中的任意元素在這個串列中的名次, 是這個串列中比它小的元素的個數. 但是給定的串列並不一定具有惟一性, 也就是說一個串列中可能會有重複的元素, 那麼應該如何處理重複的元素呢. 此處要講述一個關於排序的概念 : 穩定性

一個排序演算法是否具有穩定性的描述是對於一個串列中的相同數字, 如若排序之後這些數字的次序不變, 那麼稱這個排序是穩定的; 否則, 稱這個排序是不穩定的. 例如一個序列

B、C_{1}、P、A、C_{2}、K

如果經過某個排序演算法調整之後, 是這樣的 :

A、B、C_{1}、C_{2}、K、P

那麼這個排序演算法是穩定的; 而如果經過排序演算法調整之後是這樣的 :

A、B、C_{2}、C_{1}、K、P

那麼說這個排序演算法是不穩定的. 其中 C_{1}C_{2} 是兩個相等的值

我們定義一個元素在一個串列中的名次 R

R = 串列中所有小於該元素的個數 + 出現在該元素左側相同元素的個數

從此, 我們可以看到, 這樣計算而來的名次排序是穩定的

Tip : 之後《演算法》系列的文章中將不再出現對排序的穩定性的重新描述

例如陣列 a = {4, 3, 9, 3, 7}, 各個元素的名次 R = {2, 0, 4, 1, 3}

根據上述描述, 對於任意一個串列, 我們首先給串列中的每一個元素計算名次, 其實就是統計出現在某個元素左側相同元素的個數以及比它小的元素的個數, 作為它的名次 :

void rank_element(const int array[], int size, int rank[]) {

    for(auto i {0}; i < size; ++i) {

        rank[i] = 0;

    }

    for(auto i {1}; i < size; ++i) {

        for(auto j {0}; j < i; ++j) {

            if(array[j] > array[i]) {

                ++rank[j];

            }else {

                ++rank[i];

            }

        }

    }

}

我們發現, 因為我們對相同元素進行了處理, 所以得到的排名必定是獨一無二的. 這就好比一個班裡的同學的成績名次, 如若某幾個同學的分數一致, 那麼按照它們出現的先後順序再進行計算

此時, 由於名次已經計算出來了, 於是我們只要對名次進行重新排列即可 :

void ranking_sort(const int array[], int size, const int rank[], int out[]) {

    for(auto i {0}; i < size; ++i) {

        out[rank[i]] = array[i];

    }

}

但是一般來說, 我們希望直接對陣列 array 進行重新排列, 而不是將排序的結果輸出到另外一個陣列, 也就是函式原型為

void ranking_sort(int array[], int size, int rank[]);

這樣, 函式的呼叫者使用函式的時候就會方便一些

此時, 我們需要用到剛剛所提到的, "得到的排名必定是獨一無二的" 這一特性. 考慮最優的結果 : 令 i = 0, i0 開始直到 size, 如果每一次都有 rank[i] == i, 那麼陣列就是有序的. 而並不是每一次都會有最優的結果, 因此我們需要考慮如果 rank[i] != i 的時候, 我們應該如何處理. 容易地, 我們想到交換. 如果 rank[i] == i 並不成立, 那麼我們可以讓陣列元素進行交換, 同時將排名進行交換 :

我們假定目前 i = 0, 那麼 array 中對應的元素為 4, rank 中對應的元素為 2. 此時 rank[0] 和 0 並不相等, 於是和排位在第 2 (實際次序為 3) 的元素進行交換, 得到

我們發現元素 4 已經被放到了對應的位置, 但是元素 9 對應的名次是 4, 也就是 rank[0] 仍然和 0 不相等, 於是繼續進行這樣的交換 :

此時, 元素 9 也已經被放到了對應的位置, 但是元素 7 對應的名次仍然不是 0, 於是繼續進行交換 :

元素 7 已經被放到了對應的位置, 這個時候 rank[0] 仍然不等於 0, 進行最後一次交換 :

在最後一次交換之前, 其實我們已經發現陣列 array 有序, 但是為了維護串列的穩定性, 於是我們需要進行最後一次交換. 此時, rank[0] == 0, 而 i 繼續增加的過程中, 我們會發現總有 rank[i] == i, 於是可以判定陣列有序

我們將函式 ranking_sort 修改如下 :

void ranking_sort(int array[], int size, int rank[]) {

    for(auto i {0}; i < size; ++i) {

        auto &save {rank[i]};

        while(save not_eq i) {

            swap(array[i], array[save]);

            swap(save, rank[save]);

        }

    }

}

其中, 函式 swap 的具體實作如下 :

void swap(int &lhs, int &rhs) {

    auto tmp {rhs};

    rhs = lhs;

    lhs = tmp;

}

Tip : 之後《演算法》系列的文章中, 將不會再出現 swap 函式的實作方式

重新觀察上述所有程式碼, 我們發現我們每一次進行名次排序的時候, 需要進行兩次的函式呼叫. 除此之外, 陣列 rank 也是由我們自己來給出的. 從函式設計的角度來考慮, 這個陣列對函式呼叫者其實沒有任何用處, 除非他想要測試這個函式的正確性, 而這並不是函式呼叫者所要做的工作, 因此上述程式碼需要進一步優化, 這裡的優化是針對函式呼叫者的優化 :

void ranking_sort(int array[], int size) {

    auto rank {::new int[size] {}};

    for(auto i {1}; i < size; ++i) {

        for(auto j {0}; j < i; ++j) {

            if(array[j] > array[i]) {

                ++rank[j];

            }else {

                ++rank[i];

            }

        }

    }

    for(auto i {0}; i < size; ++i) {

        auto &save {rank[i]};

        while(save not_eq i) {

            swap(array[save], array[i]);

            swap(rank[save], save);

        }

    }

    ::delete[] rank;

}

對於泛型的實作方式, 可以參考本人的 GitHub : GitHub 點擊直達, 搜尋 ranking_sort