什么是排序算法的穩(wěn)定性？

穩(wěn)定： 如果 a = b， a原本在b的前面， 排序之后， a仍然在b的前面， 那么這個(gè)排序算法就是穩(wěn)定的。反之， 就是不穩(wěn)定的排序算法。

穩(wěn)定的排序算法有：

一.快速排序

思想：選取中間的數(shù)為基準(zhǔn)值， 然后將比它小的放在左邊， 比它大的放在右邊， 然后將左右兩邊的數(shù)組進(jìn)行同樣的操作， 使用遞歸的思想。

注意三點(diǎn)：

1.要判斷遞歸的邊界條件， 當(dāng)數(shù)組的長度 <= 1 時(shí)， 跳出遞歸;

2.最后進(jìn)行數(shù)組合并時(shí)， 需要將基準(zhǔn)值也合并進(jìn)去;

3.splice是對原數(shù)組進(jìn)行操作， 返回的是要?jiǎng)h除的數(shù)組;

二.冒泡排序

冒泡排序的原理：

比方說有五個(gè)數(shù)字54321， 要按從小到大排列；

首先比較前兩個(gè)， 就是5和4， 如果第一個(gè)小于第二個(gè)， 不做操作， 如果第一個(gè)大于第二個(gè)， 那么交換二者的位置， 即變成45321， 然后比較第二個(gè)和第三個(gè)，交換位置， 變成43521， 然后第三個(gè)和第四個(gè)， 第四個(gè)和第五個(gè)， 這樣一次循環(huán)下來， 變成43215；

所以， 一層循環(huán)的效果就是挑出最大的一個(gè)數(shù)字5， 冒泡到最后面。接著相似方法挑出第二大， 第三大的數(shù)字等。那么一層循環(huán)就不夠用， 必須再嵌套一層。

像這個(gè)例子， 五個(gè)數(shù)字， 起碼要進(jìn)行四輪循環(huán)才行。 至于為什么要this.length - i， 是因?yàn)榈谝淮伪容^五個(gè)數(shù)字， 第二個(gè)只要比較前四個(gè)就行了，第五個(gè)肯定是最大的了。

改進(jìn)后的冒泡排序：

改進(jìn)的思路： 將每趟排序中最后一次進(jìn)行交換的位置pos記錄下來， 下次排序只要掃描到pos即可。

三.選擇排序

最直觀的排序算法

依次找出第一大、 第二大、 第三大...依次放在數(shù)組中

歡迎關(guān)注。