直接開(kāi)門見(jiàn)山
java中Arrays.sort使用了兩種排序方法窟她，快速排序和優(yōu)化的歸并排序。
快速排序主要是對(duì)哪些基本類型數(shù)據(jù)（int,short,long等）排序蔼水， 而合并排序用于對(duì)對(duì)象類型進(jìn)行排序震糖。使用不同類型的排序算法主要是由于快速排序是不穩(wěn)定的，而合并排序是穩(wěn)定的
歸并排序相對(duì)而言比較次數(shù)比快速排序少徙缴，移動(dòng)（對(duì)象引用的移動(dòng)）次數(shù)比快速排序多试伙，而對(duì)于對(duì)象來(lái)說(shuō)嘁信，比較一般比移動(dòng)耗時(shí)于样。補(bǔ)充一點(diǎn)合并排序的時(shí)間復(fù)雜度是nlogn, 快速排序的平均時(shí)間復(fù)雜度也是nlogn疏叨，但是合并排序的需要額外的n個(gè)引用的空間。
import java.util.Arrays;
import java.util.Comparator;
public class ArraySort {
public static void main(String[] args) {
Dog d2 = new Dog(2);
Dog d1 = new Dog(1);
Dog d3 = new Dog(3);
Dog[] dogArray = {d3,d1,d2};
printDog(dogArray);
Arrays.sort(dogArray,new DogSizeComparator());
printDog(dogArray);
}
public static void printDog(Dog[] dogs){
for (Dog dog:dogs) {
System.out.println(dog.size+" ");
}
System.out.println();
}
}
class Dog{
int size;
public Dog(int s){
this.size = s;
}
}
class DogSizeComparator implements Comparator<Dog> {
@Override
public int compare(Dog o1, Dog o2) {
return o1.size - o2.size;
}
}
源碼中的快速排序穿剖，主要做了以下幾個(gè)方面的優(yōu)化：
1）當(dāng)待排序的數(shù)組中的元素個(gè)數(shù)較少時(shí)蚤蔓，源碼中的閥值為7，采用的是插入排序糊余。盡管插入排序的時(shí)間復(fù)雜度為0(n^2)秀又，但是當(dāng)數(shù)組元素較少時(shí)，插入排序優(yōu)于快速排序贬芥，因?yàn)檫@時(shí)快速排序的遞歸操作影響性能吐辙。
2）較好的選擇了劃分元（基準(zhǔn)元素）。能夠?qū)?shù)組分成大致兩個(gè)相等的部分蘸劈，避免出現(xiàn)最壞的情況昏苏。例如當(dāng)數(shù)組有序的的情況下，選擇第一個(gè)元素作為劃分元威沫，將使得算法的時(shí)間復(fù)雜度達(dá)到O(n^2).
3）根據(jù)劃分元 v 贤惯，形成不變式 v* (
源碼中選擇劃分元的方法:
1）當(dāng)數(shù)組大小為 size=7 時(shí) ，取數(shù)組中間元素作為劃分元棒掠。int n=m>>1;(此方法值得借鑒)孵构。
2）當(dāng)數(shù)組大小size大于7小于等于40時(shí)，取首烟很、中颈墅、末三個(gè)元素中間大小的元素作為劃分元。
3）當(dāng)數(shù)組大小 size>40 時(shí) 雾袱，從待排數(shù)組中較均勻的選擇9個(gè)元素恤筛，選出一個(gè)偽中數(shù)做為劃分元。
普通的快速排序算法谜酒，經(jīng)過(guò)一次劃分后叹俏，將劃分元排到素組較中間的位置，左邊的元素小于劃分元僻族，右邊的元素大于劃分元粘驰，而沒(méi)有將與劃分元相等的元素放在其附近，這一點(diǎn)述么，在Arrays.sort()中得到了較大的優(yōu)化蝌数。
舉例：15、93度秘、15顶伞、41饵撑、6、15唆貌、22滑潘、7、15锨咙、20
舉例：15语卤、93、15酪刀、41粹舵、6、15骂倘、22眼滤、7、15历涝、20
因size大于7小于等于40 ,所以在15诅需、6、和20 中選擇v = 15 作為劃分元睬关。
經(jīng)過(guò)一次換分后： 15诱担、15、7电爹、6蔫仙、41、20丐箩、22摇邦、93、15屎勘、15. 與劃分元相等的元素都移到了素組的兩邊施籍。
接下來(lái)將與劃分元相等的元素移到數(shù)組中間來(lái)，形成：7概漱、6丑慎、15、15瓤摧、15竿裂、15、41照弥、20腻异、22、93.
最后遞歸對(duì)兩個(gè)區(qū)間進(jìn)行排序[7这揣、6]和[41悔常、20影斑、22、93].,所以在15机打、6矫户、和20 中選擇v = 15 作為劃分元。
