各種排序算法的穩(wěn)定性和時間復(fù)雜度小結(jié)(編輯修改稿)
2025-07-20 07:22 本頁面
【文章內(nèi)容簡介】 兩個方向，左邊的i下標(biāo)一直往右走，當(dāng)a[i] = a[center_index]，其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個元素。而右邊的j下標(biāo)一直往左走，當(dāng)a[j] a[center_index]。如果i和j都走不動了，i = j, 交換a[i]和a[j],重復(fù)上面的過程，直到ij。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現(xiàn)在中樞元素5和3(第5個元素，下標(biāo)從1開始計)交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻。 (5)歸并排序 歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認(rèn)為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序?？梢园l(fā)現(xiàn)，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個當(dāng)前元素相等時，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。 (6)基數(shù)排序 基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前?；鶖?shù)排序基于分別排序，分別收集，所以其是穩(wěn)定的排序算法。 (7)希爾排序(shell) 希爾排序是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ?，希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1