c++ list.sort的穩(wěn)定性如何保證

c++
小樊
81
2024-09-27 17:25:42

C++ STL（Standard Template Library）中的list.sort()函數(shù)并不保證穩(wěn)定性。穩(wěn)定性是指在排序過(guò)程中，如果兩個(gè)元素相等，它們?cè)谂判蚝蟮南鄬?duì)順序不會(huì)改變。list.sort()使用的是歸并排序算法，而歸并排序是不穩(wěn)定的排序算法。

如果你需要一個(gè)穩(wěn)定的排序算法，可以考慮使用C++ STL中的stable_sort()函數(shù)。stable_sort()使用的是歸并排序算法的穩(wěn)定版本，可以保證相等元素的相對(duì)順序不變。需要注意的是，stable_sort()要求輸入范圍必須是有序的，或者在排序過(guò)程中會(huì)重新構(gòu)造有序狀態(tài)。

以下是一個(gè)使用stable_sort()的示例：

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> my_list = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    // 使用 stable_sort 對(duì) list 進(jìn)行排序
    std::stable_sort(my_list.begin(), my_list.end());

    // 輸出排序后的結(jié)果
    for (const auto& item : my_list) {
        std::cout << item << " ";
    }

    return 0;
}

輸出結(jié)果為：

1 1 2 3 3 4 5 5 5 6 9

可以看到，相等元素（如兩個(gè)1）在排序后的相對(duì)順序沒(méi)有改變。

0 踩