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

更新時間：2014年02月10日 15:13:17 作者：

這篇文章主要介紹了JAVA算法起步之快速排序實例,需要的朋友可以參考下

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