直接插入排序演算法穩定嗎

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

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

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

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

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

③ 簡單(直接)選擇排序的穩定性

簡單選擇排序是不穩定排序。

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的。

(3)直接插入排序演算法穩定嗎擴展閱讀：

簡單選擇排序的最優情況：

最好情況下，即待排序記錄初始狀態就已經是升序排列了，則不需要移動記錄。

對於不穩定的排序演算法，只要舉出一個實例，即可說明它的不穩定性；而對於穩定的排序演算法，必須對演算法進行分析從而得到穩定的特性。

排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法。

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

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

參考資料來源：網路-簡單選擇排序

參考資料來源：網路-排序演算法穩定性

④ 誰能幫我具體分析下插入排序、冒泡排序、選擇排序三種方法的優劣著重分析三種排序所耗費的時間，穩定性

排序方法 最壞時間復雜度 最好時間復雜度 平均時間復雜度 穩定性
直接插入 O(n2) O(n) O(n2) 穩定
簡單選擇 O(n2) O(n2) O(n2) 不穩定
起泡排序 O(n2) O(n) O(n2) 穩定
快速排序 O(n2) O(nlog2n) O(nlog2n) 不穩定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) 不穩定
歸並排序 O(nlog2n) O(nlog2n) O(nlog2n) 穩定

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

一、穩定排序演算法

1、冒泡排序

2、雞尾酒排序

3、插入排序

4、桶排序

5、計數排序

6、合並排序

7、基數排序

8、二叉排序樹排序

二、不穩定排序演算法

1、選擇排序

2、希爾排序

3、組合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

一個排序演算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。

做這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個對象間之比較，就會被決定使用在原先數據次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。

(5)直接插入排序演算法穩定嗎擴展閱讀：

排序演算法的分類：

1、通過時間復雜度分類

計算的復雜度（最差、平均、和最好性能），依據列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且壞的性能是 O(n^2)。對於一個排序理想的性能是 O(n)。

而僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要 O(nlogn)。

2、通過空間復雜度分類

存儲器使用量（空間復雜度）（以及其他電腦資源的使用）

3、通過穩定性分類

穩定的排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。

⑥ 插入排序的穩定性

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，所以插入排序是穩定的。

⑦ 插入排序和選擇排序哪個演算法更有效

一、選擇排序
原理：將初始序列(A[0]~A[n-1])作為待排序序列，第一趟在待排序序列(A[0]~A[n-1])中找到最小值元素，將其與第一個元素A[0]交換，這樣子序列(A[0])已經有序，下一趟在排序在待排序子序列(A[1]~A[n-1])中進行。第i趟排序在待排序子序列(A[i-1]~A[n-1])中找到最小值元素，與該子序列中第一個元素A[i-1]交換。經過 n-1 趟排序後使得初始序列有序。

其他說明：選擇排序的最好、最壞和平均情況的時間復雜度都為O(n2)，而且它還需交換元素(n-1)次和移動元素3(n-1)次；它是不穩定的排序演算法。
二、插入排序
原理：將初始序列中的第一個元素作為一個有序序列，然後將剩下的 n-1 個元素按關鍵字大小依次插入該有序序列，每插入一個元素後依然保持該序列有序，經過 n-1 趟排序後使初始序列有序。

其他說明：插入排序在最好的情況下時間復雜度為O(n)，比較次數為(n-1)次，移動元素次數是2(n-1)；最壞的情況下時間復雜度為O(n2)；插入排序是穩定的排序演算法。
三、冒泡排序
原理：第一趟在序列(A[0]~A[n-1])中從前往後進行兩個相鄰元素的比較，若後者小，則交換，比較 n-1 次；第一趟排序結束，最大元素被交換到A[n-1]中，下一趟排序只需要在子序列(A[0]~A[n-2])中進行；冒泡排序最多進行 n-1 趟。基本的冒泡排序可以利用旗標的方式稍微減少一些比較的時間，當尋訪完序列後都沒有發生任何的交換動作，表示排序已經完成，而無需再進行之後的比較與交換動作。

其他說明：冒泡排序最好的情況下只需進行一趟排序，(n-1)次比較，此時的時間復雜度為O(n)，無需移動元素；最壞的情況下進行 n-1 趟排序，時間復雜度為O(n2)；冒泡排序是穩定的排序演算法。