Java快速排序的簡單範例

這篇文章主要為大家詳細介紹了java簡單快速排序實例，具有一定的參考價值，有興趣的小夥伴們可以參考一下

##一、基本概念

#      找出一個元素（理論上可以隨便找一個）作為基準(pivot),然後對數組進行分區操作,使基準左邊元素的值都不大於基準值,基準右邊的元素值都不小於基準值，如此作為基準的元素調整到排序後的正確位置。遞歸快速排序，將其他n-1個元素也調整到排序後的正確位置。最後每個元素都是在排序後的正 的確位置，排序完成。所以快速排序演算法的核心演算法是分區操作，也就是如何調整基準的位置以及調整回傳基準的最終位置以便分治遞歸。

二、選擇基準元

1、固定標折碼

      若輸入序列是隨機的，處理時間是可以接受的。如果數組已經有順序時，此時的分割就是一個非常不好的分割。因為每次劃分只能使待排序序列減一，此時為最壞情況，快速排序淪為冒泡排序，時間複雜度為Θ(n^2)。而且，輸入的資料是有序或部分有序的情況是相當常見的。因此，使用第一個元素作為基準元是非常糟糕的，應該立即放棄這種想法。

2、隨機基準元

      這是相對安全的策略。由於基準元的位置是隨機的，那麼產生的分割也不會總是會出現劣質的分割。在整個數組數字全相等時，仍然是最壞情況，時間複雜度是O(n^2）。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n）。所以隨機化快速排序可以對於絕大多數輸入資料達到O（n×log(n))的期望時間複雜度。

3、三數取中

      最佳的分割是將待排序的序列分成等長的子序列，最佳的狀態我們可以使用序列的中間的值，也就是第N/2個數。可是，這很難算出來，會明顯減慢快速排序的速度。這樣的中位數的估計可以透過隨機選取三個元素並用它們的中位數作為基準元而得到。事實上，隨機性並沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中位數作為基準元。

三、partition演算法

      partition演算法是快速排序的核心，在學習快排之前，可以先學習這個演算法。下面先貼程式碼:

  public int partition(int[] num,int left,int right){
    if(num==null || num.length<=0 || left<0 || right>=num.length){
      return 0;
    }
    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标
    while (left<=right){         //从两端交替向中间扫描
      while (num[left]<prio)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最终将基准数归位 
        left++;
        right--;
      }
    }
    return left;
  }

    這個方法的想法是先找一個樞紐元（這個方法實作裡面找的是第一個元素，但其實大有文章不過這裡先簡化描述），再從數組的兩邊（具體從哪裡到哪裡由傳進來額參數決定）生成兩個指針left和right，每次發現左邊的元素大於樞紐元則i停下來，右邊的元素小於樞紐元j就停下來，並且交換這個兩個數的位置。直到兩個指針left，right相遇。再把樞紐元插入left的位置，也就是它應該在的位置。

      這麼做最後的結果是讓數組的[left，right]部分呈現出2部分，樞紐元最終位置以左都是小於等於樞紐元的，以右都是大於等於樞紐元的。而樞紐元則被插入到了一個絕對正確的位置。

四、排序演算法實作

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一个数组中取一个基准数字，把小的数放基准的左边，大的数放基准的右边。
 * 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字，小的放左边，大的放右边。
 * 这个里面用到的递归。我们需要三个参数，一个是数组，另外两个是序列的边界
 * @author HJS
 */
public class QuickSort{

  void sort(int num[],int left,int right){
    if (left
以上是Java快速排序的簡單範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！