JAVA算法起步之疾速排序實例。本站提示廣大學習愛好者:(JAVA算法起步之疾速排序實例)文章只能為提供參考,不一定能成為您想要的結果。以下是JAVA算法起步之疾速排序實例正文
疾速排序一聽這個名字能夠感到很快,然則他的算法時光龐雜度最壞情形卻跟拔出排序是一樣的。之所以成為疾速排序是由於他的均勻效力比堆排序還要快,疾速排序也是基於分治思惟與合並排序差不多,然則疾速排序是舊址的,直接在原數組操作不須要再開拓新的存儲空間。疾速排序的思惟很簡略,就是選定一個症結字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]);
}
}
}