Arrays.sort()根據(jù)入?yún)㈩?lèi)型選擇以下排序算法
- 基本類(lèi)型數(shù)組使用快速排序
- 對(duì)象數(shù)組使用歸并排序
原因
- 使用不同類(lèi)型的排序算法主要是由于快速排序是不穩(wěn)定的再扭，而合并排序是穩(wěn)定的氧苍。這里的穩(wěn)定是指比較相等的數(shù)據(jù)在排序之后仍然按照排序之前的前后順序排列。對(duì)于基本數(shù)據(jù)類(lèi)型泛范，穩(wěn)定性沒(méi)有意義让虐，而對(duì)于對(duì)象類(lèi)型，穩(wěn)定性是比較重要的罢荡，因?yàn)閷?duì)象相等的判斷可能只是判斷關(guān)鍵屬性赡突，最好保持相等對(duì)象的非關(guān)鍵屬性的順序與排序前一直；
- 另外一個(gè)原因是由于合并排序相對(duì)而言比較次數(shù)比快速排序少柠傍，移動(dòng)（對(duì)象引用的移動(dòng)）次數(shù)比快速排序多麸俘，而對(duì)于對(duì)象來(lái)說(shuō)，比較一般比移動(dòng)耗時(shí)惧笛。
補(bǔ)充一點(diǎn)合并排序的時(shí)間復(fù)雜度是n*logn, 快速排序的平均時(shí)間復(fù)雜度也是n*logn从媚，但是合并排序的需要額外的n個(gè)引用的空間。
