排序算法的穩(wěn)定性
排序算法的穩(wěn)定性是指兩個相等的元素在排序前后其相對位置是不變的抛猖。而與時間復(fù)雜度沒有直接關(guān)系脉漏，所以要注意區(qū)分相關(guān)的概念秩伞。
穩(wěn)定:冒(冒泡排序)直(直接插入排序)歸(歸并排序)基(基數(shù)排序尿这，不常用)
不穩(wěn)定:選(選擇排序)希(希爾排序)快(快速排序)堆(堆排序)
常見的6種排序算法的平均時間復(fù)雜度分析
冒n2直n2
歸nlog2n
選n2快nlog2n
堆nlog2n
排序時間復(fù)雜度與初始狀態(tài)是否有關(guān)(循環(huán)次數(shù))
歸并切油，選擇排序只磷，堆排序，由于平均最差相同泌绣，所以初始順序不影響其排序復(fù)雜度選擇
排序比較次數(shù)與初始狀態(tài)是否有關(guān)
算法性能與初始狀態(tài)是否有關(guān)
直接插入钮追，歸并，快排阿迈，堆有關(guān)
冒泡元媚，選擇無關(guān)
初始序列基本有序的情況
冒泡n最好 直接插入n最好
快排n2最差
空間復(fù)雜度
只有快排的空間復(fù)雜度，和堆排序的空間復(fù)雜度比較多堆排序需要額外的輔助空間n
快排的空間復(fù)雜度苗沧，如果就地快排1
使用遞歸平均是logn刊棕，最差情況，退化成冒泡是n
附:
上圖有錯:快排的空間復(fù)雜度待逞，如果就地快排1
使用遞歸平均是logn甥角，最差情況，退化成冒泡是n
