程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> JAVA算法起步之疾速排序實例

JAVA算法起步之疾速排序實例

編輯:關於JAVA

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]);
  }
 }
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved