快速排序一聽這個名字可能感覺很快，但是他的算法時間復雜度最壞情況卻跟插入排序是一樣的。之所以成為快速排序是因為他的平均效率比堆排序還要快，快速排序也是基于分治思想與歸并排序差不多，但是快速排序是原址的，直接在原數組操作不需要再開辟新的存儲空間。快速排序的思想很簡單，就是選定一個關鍵字k將原數組分成兩份g1與g2，g1中所有的元素都比k小或者相等，而g2中所有的數據都比k大或者等于，這樣對g1與g2分別進行快速排序，最終我們得到的就是一個有序的數組。代碼中的sort方法就是對剛才語句的描述。而關鍵的算法就是去尋找k的位置將原數組分為大小兩部分的過程。方法getPlocation就是快速排序的核心。他的實現原理有點像插入排序只是有點像。每次都把map中end位置的元素作為關鍵字，通過與end元素對比將數組分成大小兩部分，而i與j則是兩個分割線，i與j之間的數都是比core大的元素，i與j就像一條貪吃蛇，當j的下一個數比core大的時候j+1，i到j的長度增大了，而如果比core小的話，i與j都向前走一下，并將那個小數放在i的前面。這樣循環一遍后，start到end-1之間就是按大小分開的，最后將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]);
}
}
}
