不穩定演算法

❶ 怎樣理解選擇排序演算法的不穩定

怎樣理解選擇排序演算法的不穩定
區別在於：冒泡演算法，每次比較如果發現較小的元素在後面，就交換兩個相鄰的元素。而選擇排序演算法的改進在於：先並不急於調換位置，先從A[1]開始逐個檢查，看哪個數最小就記下該數所在的位置P，等一躺掃描完畢，再把A[P]和A[1]對調，這時A[1]到A[10]中最小的數據就換到了最前面的位置。 所以，選擇排序每掃描一遍數組，只需要一次真正的交換，而冒泡可能需要很多次。比較的次數是一樣的。

❷ 數據結構裡面什麼是穩定的排序，什麼是不穩定的排序，怎麼看，什麼是穩定性

就是說在配需前後，各個關鍵字的相對位置不變。
舉個例子來說吧，假設在排序前數據排列如下：
排序前：5,6（1）,1,4,3,6（2）,（第一個6在第二個6之前）
排序後：1）如果排序後的結果是1,2,3,4,5,6（1），6（2）那麼就說此排序算 法是穩定的，即使穩 定的排序。
2）如果排序後的結果是1,2,3,4,5,6（2），6（1），即6（1）和6（2）相比較排序前
他們的相對順序改變了（第二個6排到第一個6之前了），那麼就說這次排序是不穩定的 排序
像快速排序、希爾排序等演算法都是不穩定排序演算法，冒泡排序、插入排序等演算法是穩定的排序演算法。
希望對你有幫助哦~~

❸ 排序演算法穩定性的判斷方法

對於不穩定的排序演算法，只要舉出一個實例，即可說明它的不穩定性；而對於穩定的排序演算法，必須對演算法進行分析從而得到穩定的特性。需要注意的是，排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法。
例如，對於如下起泡排序演算法，原本是穩定的排序演算法，如果將記錄交換的條件改成r[j]>=r[j+1]，則兩個相等的記錄就會交換位置，從而變成不穩定的演算法。
void BubbleSort(int r[ ], int n){
exchange=n; //第一趟起泡排序的范圍是r[1]到r[n]
while (exchange) //僅當上一趟排序有記錄交換才進行本趟排序
{
bound=exchange; exchange=0；
for (j=1; j if (r[j]>r[j+1]) {
r[j]←→r[j+1]；
exchange=j； //記錄每一次發生記錄交換的位置
}
}
}
再如，快速排序原本是不穩定的排序方法，但若待排序記錄中只有一組具有相同關鍵碼的記錄，而選擇的軸值恰好是這組相同關鍵碼中的一個，此時的快速排序就是穩定的。

❹ 判斷題 9， 直接插入排序演算法是一種不穩定的排序演算法。（）

不對。
ps：直接排序法在最好情況下（待排序列已按關鍵碼有序），每趟排序只需作1次比較而不需要移動元素。所以n個元素比較次數為n-1，移動次數0。
最差的情況下（逆序），其中第i個元素必須和前面的元素進行比較i次，移動個數i+1，所以總共的比較次數
比較多，就不寫出來了
總結：是一種穩定的排序方法，時間復雜度O(n^2)，排序過程中只要一個輔助空間，所以空間復雜度
麻煩接納一下，任務所需，謝謝！

❺ 為什麼快速排序是一個不穩定的排序法

以Ai與Aj為例子

快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，
其中center_index是中樞元素的數組下標，一般取為數組第0個元素。而右邊的
j下標一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，
i <= j, 交換a[i]和a[j],重復上面的過程，直到i>j。
交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的
時候，很有可能把前面的元素的穩定性打亂，比如序列5 3 3 4 3 8 9 10 11，
現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂
，所以快速排序是一個不穩定的排序演算法，不穩定發生在中樞元素和a[j]交換的時刻。

❻ 為什麼說選擇排序不穩定

因為你的序列並非隨機數。

1.你的待排序列有個隱藏的邊界，即滿分、零分。

2.你根據經驗，引入了歸並排序的思想，而且你還對分堆有一個經驗上預測（不同分段人數）。

3.數據的存儲結構（實體的試卷）非常適合「插入」、「分堆」這樣的操作，而最常見的二元swap，就不太便利。

假設滿分為100分：

邊界分數你第一輪遍歷就可以以100%的概率放到正確的位置（比如100分，99分，0分，1分），離邊界越近的分數就越容易達成這個效果（比如98分，97分，3分，2分），砍掉了隨機數測試中可能會出現重排概率。

所以對於你的特例，經過你改良的選擇排序就會非常穩定，而且排序的操作很適合實體的試卷。

選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是：第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小（大）元素，然後放到已排序的序列的末尾。

以此類推，直到全部待排序的數據元素的個數為零。選擇排序是不穩定的排序方法。

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩餘元素裡面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。

那麼，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素後面，那麼交換後穩定性就被破壞了。

舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中兩個5的相對前後順序就被破壞了，所以選擇排序是一個不穩定的排序演算法。

❼ 為什麼快速排序是不穩定的演算法

排序演算法不穩定的含義是:

在排序之前,有兩個數相等.
但是在排序結束之後,它們兩個有可能改變順序.

比如說:
在一個待排序隊列中,A和B相等,且A排在B的前面,而排序之後,A排在了B的後面.這個時候,我們說這種演算法是不穩定的.
(只要有這種可能性,我們就說演算法是不穩定的.)

注: 演算法的不穩定性,與所用的語言沒有關系的.

那麼,快速排序為什麼不穩定呢?

我們來看看快速排序的過程:(還是借用之前的那個假設,假設A,B相等,並和其它一堆數據一起參加排序.)

假設此時的快排是小於等於關鍵字為排在前面的一組組,大於為另外排在後面的一組.

在選取一個數出來分組的時候,如果選到了A,那麼在B<=A的情況下,B將會排在A的前面.

因為有這樣的_可能性_,所以說我們這種演算法是不穩定的.

注:請參考快排的具體演算法.
另外，TO 朱_大志同學,可能我們兩個的教材有一定的差別.

❽ 數據排序演算法的穩定與不穩定

LZ在瞎扯

假設有序列（123，3244，45，【123】）
排序後為（45，123，123，3244）
如果第一個123在排序後還在第二個【123】之前，即
45 123 【123】 3244
則演算法是穩定的
否則
45 【123】 123 3244
即為不穩定

❾ 數據結構的排序演算法中，哪些排序是穩定的，哪些排序是不穩定的

快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序演算法。

基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。

❿ 數據結構 如何判斷演算法是否穩定

如果是復雜度，就多次測試的樣本方差大小，如果小，則演算法復雜度穩定
如果是排序，就看排序前後相同大小的元素相對位置有無變化，如果沒有，則穩定，穩定的排序演算法有冒泡排序，歸並排序和插入排序，其他的常用排序比如快排基本都不是穩定排序