快速排序一聽(tīng)這個(gè)名字可能感覺(jué)很快，但是他的算法時(shí)間復(fù)雜度最壞情況卻跟插入排序是一樣的。之所以成為快速排序是因?yàn)樗钠骄时榷雅判蜻€要快，快速排序也是基于分治思想與歸并排序差不多，但是快速排序是原址的，直接在原數(shù)組操作不需要再開(kāi)辟新的存儲(chǔ)空間。快速排序的思想很簡(jiǎn)單，就是選定一個(gè)關(guān)鍵字k將原數(shù)組分成兩份g1與g2，g1中所有的元素都比k小或者相等，而g2中所有的數(shù)據(jù)都比k大或者等于，這樣對(duì)g1與g2分別進(jìn)行快速排序，最終我們得到的就是一個(gè)有序的數(shù)組。代碼中的sort方法就是對(duì)剛才語(yǔ)句的描述。而關(guān)鍵的算法就是去尋找k的位置將原數(shù)組分為大小兩部分的過(guò)程。方法getPlocation就是快速排序的核心。他的實(shí)現(xiàn)原理有點(diǎn)像插入排序只是有點(diǎn)像。每次都把map中end位置的元素作為關(guān)鍵字，通過(guò)與end元素對(duì)比將數(shù)組分成大小兩部分，而i與j則是兩個(gè)分割線，i與j之間的數(shù)都是比core大的元素，i與j就像一條貪吃蛇，當(dāng)j的下一個(gè)數(shù)比core大的時(shí)候j+1，i到j(luò)的長(zhǎng)度增大了，而如果比core小的話，i與j都向前走一下，并將那個(gè)小數(shù)放在i的前面。這樣循環(huán)一遍后，start到end-1之間就是按大小分開(kāi)的，最后將core放在中間，將core的位置返回就是分界線了。
public class QuickSort {
public int getPlocation(int[] map,int start,int end){
int core=map[end];
int i=start-1;
for(int j=start;j<=end-1;j++){
if(map[j]<=core){
i++;
int cache=map[j];
map[j]=map[i];
map[i]=cache;
}
}
i++;
map[end]=map[i];
map[i]=core;
return i;
}
public void sort(int[] map,int start,int end){
if(start<end){
int p=getPlocation(map, start, end);
sort(map, start, p-1);
sort(map,p+1,end);
}
}
public static void main(String[] args) {
int[] map=new int[]{4,1,5,3,7,12,65,7};
QuickSort qs=new QuickSort();
qs.sort(map, 0, map.length-1);
for (int i = 0; i < map.length; i++) {
System.out.println(map[i]);
}
}
}
