一、Python中的排序

（一）內置排序函數sorted()

1. 基本用法
   • sorted()函數可以對所有可迭代對象進行排序操作，返回一個新的列表，原列表不會被修改。
   • 例如，對于一個簡單的數字列表nums = [3, 1, 4, 1, 5, 9, 2, 6]，使用sorted(nums)后會得到[1, 1, 2, 3, 4, 5, 6, 9]。
   • 對于字符串列表，如words = ["apple", "banana", "cherry", "date"]，sorted(words)會按照字母順序排序，得到['apple', 'banana', 'cherry', 'date']。
2. 關鍵字參數
   • key參數
     • 可以通過key參數指定一個函數，該函數會在排序時被調用，用于提取比較的鍵。
     • 比如，如果有一個包含數字和字母的列表mixed_list = ['a', 'c', 'b', 1, 3, 2]，我們想要按照字符的ASCII值進行排序，可以使用sorted(mixed_list, key=str)。因為str函數會將數字轉換為字符串，然后按照字符串的ASCII值排序，結果是[1, 2, 3, 'a', 'b', 'c']。
     • 對于更復雜的數據結構，如一個包含學生信息的列表students = [{'name': 'Alice', 'age': 23}, {'name': 'Bob', 'age': 20}, {'name': 'Charlie', 'age': 22}]，如果按照年齡排序，可以使用sorted(students, key=lambda x: x['age'])，得到[{'name': 'Bob', 'age': 20}, {'name': 'Charlie', 'age': 22}, {'name': 'Alice', 'age': 23}]。
   • reverse參數
     • 用于指定排序順序，默認為False，表示升序排序。如果設置為True，則為降序排序。
     • 例如，sorted(nums, reverse=True)會將數字列表nums降序排序為[9, 6, 5, 4, 3, 2, 1, 1]。

（二）列表的sort()方法

1. 基本用法
   • sort()方法是列表對象的一個方法，它會直接對原列表進行排序，不返回新的列表。
   • 對于列表nums = [3, 1, 4, 1, 5, 9, 2, 6]，調用nums.sort()后，nums就變成了[1, 1, 2, 3, 4, 5, 6, 9]。
2. 關鍵字參數
   • 它也支持key和reverse參數，用法和sorted()函數類似。例如，nums.sort(key=lambda x: -x)會按照數字的相反數進行排序，即降序排序。

二、C++中的排序

（一）標準庫函數sort()

1. 頭文件
   • 在C++中，要使用sort()函數，需要包含頭文件<algorithm>。
2. 基本用法
   • sort()函數的原型是void sort(RandomAccessIterator first, RandomAccessIterator last)，其中first和last分別是迭代器，表示要排序的范圍。
   • 例如，對于一個數組int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};，可以使用sort(arr, arr + 8);來對整個數組進行升序排序。
   • 對于std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};，可以使用sort(vec.begin(), vec.end());來對vector容器中的元素進行排序。
3. 自定義比較函數
   • 可以通過提供第三個參數來自定義排序規則。這個參數是一個比較函數，它接收兩個參數，返回一個布爾值。
   • 比如，要對一個結構體數組按照某個成員進行排序，假設有一個結構體struct Person { std::string name; int age; };和一個數組Person people[] = {{"Alice", 23}, {"Bob", 20}, {"Charlie", 22}};，如果按照年齡升序排序，可以這樣寫：

     bool compareAge(const Person &a, const Person &b) {return a.age < b.age;
     }
     sort(people, people + 3, compareAge);
     

   • 也可以使用C++11的lambda表達式來簡化比較函數的定義，例如sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });可以對vector中的整數進行降序排序。

（二）stable_sort()

1. 穩定性
   • stable_sort()和sort()類似，但它是一個穩定排序算法。穩定排序算法是指當兩個元素相等時，它們在排序后的序列中的相對位置保持不變。
   • 例如，對于一個包含重復元素的數組int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};，使用sort(arr, arr + 8);和stable_sort(arr, arr + 8);都會得到[1, 1, 2, 3, 4, 5, 6, 9]。但如果數組中有對象，且對象的比較鍵相同，但其他屬性不同，stable_sort()會保持這些對象的原始相對順序。
2. 用法
   • 它的用法和sort()類似，也可以接受自定義比較函數。例如，對于一個std::vector<Person>，如果按照名字的字典序進行穩定排序，可以這樣寫：

     stable_sort(vec.begin(), vec.end(), [](const Person &a, const Person &b) {return a.name < b.name;
     });
     

三、Python和C++排序的性能比較

1. Python排序
   • Python的sorted()和sort()方法底層實現是Timsort算法，它是一種混合排序算法，結合了歸并排序和插入排序的優點。對于大多數情況，其時間復雜度為O(nlogn)，在實際應用中表現很高效。
2. C++排序
   • C++的sort()函數通常實現為快速排序、歸并排序或堆排序的混合體，具體實現可能因標準庫的實現而異。它的平均時間復雜度也是O(nlogn)，但在最壞情況下（如快速排序的輸入為已經有序的數組），可能會退化到O(n^2)。不過，現代C++標準庫通常會優化這種情況。
   • stable_sort()通常基于歸并排序，保證了穩定性，時間復雜度為O(nlogn)。