首頁  >  文章  >  Java  >  Java實作快速排序QuickSort的實例

Java實作快速排序QuickSort的實例

黄舟
黄舟原創
2017-10-09 09:53:111909瀏覽

下面小編就為大家帶來一篇Java快速排序QuickSort(實例)。小編覺得蠻不錯的,現在就分享給大家,也給大家做個參考。一起跟著小編過來看看吧

快速排序

---------------- -------------------------------------------------- ----

想法

如上圖:每趟快速排序開始時,設定一個key,key=array[ low],然後由high向左,找到小於key的值,複製到low位置,然後再由low向右找到大於key的值,複製到high位置,直到low=high結束,

將key的複製到low位置。

上圖中第一輪劃分後找到32的位置,然後遞歸的對32左邊和右邊的進行排序。

程式碼:


package Sort;
import java.util.Arrays;
public class QuickSort {

 public static void main(String[] args) {
  int array[]={32, 12, 7, 78, 23, 45};
  quickSort(array,0,array.length-1);
  System.out.println(Arrays.toString(array));
 }
 public static void quickSort(int array[],int left,int right)
 {
  if(left>=right)
  {
   return ;
  }
  int i=left;
  int j=right;
  int key=array[left];
  while(i<j)
  {
   while(i<j&&array[j]>key)
   {
    j--;
   }
   array[i]=array[j];
   //从后往前找到第一个比key小的数与array[i]交换;
   while(i<j&&array[i]<key)
   {
    i++;
   }
   array[j]=array[i];
   //从前往后找到第一个比key大的数与array[j]交换;
  }
  array[i]=key;
  //一趟快排之后已经将key的位置找到。
  quickSort(array,left,i-1);
  //对key左边的进行排序
  quickSort(array,i+1,right);
  //对key右边的进行排序
 }
}

以上是Java實作快速排序QuickSort的實例的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn