降序穩定排序

---

在本文中，我們將討論穩定排序的含義以及如何在保持排序演算法穩定性的前提下將陣列按降序排序。

讓我們首先討論穩定排序演算法的特徵。

排序演算法如果在排序時保留輸入資料中具有相同值的專案的原始順序，則稱為穩定的。因此，如果存在兩個或多個具有相同值的專案，則穩定排序演算法不會更改它們在排序輸出中的相對位置。

穩定排序演算法在處理諸如記錄之類的複雜資料結構時非常有用，在這些資料結構中，維護具有相同值的專案的原始順序至關重要。這是因為穩定排序演算法確保具有相等值的專案在排序輸出中保持其原始順序。可以在此類場景中使用的一些穩定排序演算法示例包括合併排序、插入排序和氣泡排序。

問題陳述

分配給我們一個包含 n 個元素的陣列，我們必須以降序對給定陣列進行排序，以使在排序時保留輸入資料中具有相同值的專案的原始順序。

Input: Nums [] = { 5, 3, 1, 3, 2 }

如果我們使用穩定排序演算法以降序對給定陣列 nums 進行排序，則獲得的陣列為：

Result: { 5, 3, 3, 2, 1 }

解決此問題的一種方法可能是實現用於降序的氣泡排序。

示例

此方法的程式碼如下所示：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void sort(vector<int>&nums, int size){
   for (int iterator = size ; iterator >= 0; iterator--)
      for (int it = size ; it > size - iterator ; it--)
         if (nums[it] > nums[it - 1])
            swap(nums[it] , nums[it-1]);
}
int main(){
   vector<int> numbers = { 5, 3, 1, 3, 2  };
   sort(numbers, 5);
   cout<<" The given array after sorting in descending order using Stable sort method is: "<< endl;
   for (int iterator = 0; iterator < numbers.size(); ++iterator) {
      cout<<  numbers[iterator] << " ";
   }
   return 0;
}

輸出

The given array after sorting in descending order using Stable sort method is: 
5 3 3 2 1

示例

使用合併排序實現

眾所周知，穩定排序也可以使用合併排序方法完成，下面給出了另一種使用合併排序的實現：

程式碼如下：

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

// this function is used to sort the array
void merge( vector<int>& nums, int left, int midelement, int temp) {
   vector<int> temparr(temp - left + 1);
   int iterator = left, j = midelement + 1, k = 0;
    
   while (iterator <= midelement && j <= temp) {
      if (nums[iterator] >= nums[j]) {
         temparr[k++] = nums[iterator++];
      } else {
         temparr[k++] = nums[j++];
      }
   }    
   while (iterator <= midelement){
      temparr[k++] = nums[iterator++];
   }    
   while (j <= temp){
      temparr[k++] = nums[j++];
   }    
   for (int p = 0; p < k; ++p) {
      nums[left + p] = temparr[p];
   }
}
void m_sort_helper( vector<int>& nums, int l, int t ) {
   if (l < t) {
      int midelement = (l + t) / 2;
      m_sort_helper ( nums, l, midelement );
      m_sort_helper( nums, midelement + 1, t );
      merge( nums, l, midelement, t );
   }
}
void merge_sort( vector<int>& nums ){
   m_sort_helper(nums, 0, nums.size() - 1);
}
int main() {
   vector<int> nums = {5, 3, 1, 3, 2};
   merge_sort( nums );
   cout<<" The given array after sorting in descending order using Stable sort method is: "<< endl;
   for (int iterator = 0; iterator < nums.size(); ++iterator ) {
      cout << nums[ iterator ] << " ";
   }
   return 0;
}

輸出

The given array after sorting in descending order using Stable sort method is: 
5 3 3 2 1

示例

使用內建庫函式

穩定排序也可以使用內建庫函式執行。

std::stable_sort 是 C++ 中的一個函式，可用於對容器（如向量或陣列）中的元素進行排序。該函式以穩定的方式對元素進行排序，這意味著相等元素在排序過程完成後會保留其相對順序。

該函式接受三個引數：要排序的容器的開始和結束迭代器，以及定義排序順序的比較函式。您可以使用它來按升序或降序對元素進行排序。

此方法的程式碼如下所示：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
   std::vector<int> nums = {5, 3, 1, 3, 2};
   std::stable_sort(nums.begin(), nums.end(), std::greater<int>());
   cout<<" The given array after sorting in descending order using Stable sort method is: "<< endl;
   for (int num : nums) {
      std::cout << num << " ";
   }    
   return 0;
}

輸出

The given array after sorting in descending order using Stable sort method is: 
5 3 3 2 1

結論

在本文中，我們討論了可以執行穩定排序操作的不同方法，包括以降序執行穩定排序的方法，我們還了解了穩定排序以及為什麼以穩定順序對陣列進行排序很重要。