一、基本概念

專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)開平免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了近1000家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

      找出一個元素（理論上可以隨便找一個）作為基準(zhǔn)(pivot),然后對數(shù)組進(jìn)行分區(qū)操作,使基準(zhǔn)左邊元素的值都不大于基準(zhǔn)值,基準(zhǔn)右邊的元素值 都不小于基準(zhǔn)值，如此作為基準(zhǔn)的元素調(diào)整到排序后的正確位置。遞歸快速排序，將其他n-1個元素也調(diào)整到排序后的正確位置。最后每個元素都是在排序后的正 確位置，排序完成。所以快速排序算法的核心算法是分區(qū)操作，即如何調(diào)整基準(zhǔn)的位置以及調(diào)整返回基準(zhǔn)的最終位置以便分治遞歸。

二、選擇基準(zhǔn)元

1、固定基準(zhǔn)元

      如果輸入序列是隨機(jī)的，處理時間是可以接受的。如果數(shù)組已經(jīng)有序時，此時的分割就是一個非常不好的分割。因?yàn)槊看蝿澐种荒苁勾判蛐蛄袦p一，此時為最壞情況，快速排序淪為冒泡排序，時間復(fù)雜度為Θ(n^2)。而且，輸入的數(shù)據(jù)是有序或部分有序的情況是相當(dāng)常見的。因此，使用第一個元素作為基準(zhǔn)元是非常糟糕的，應(yīng)該立即放棄這種想法。

2、隨機(jī)基準(zhǔn)元

      這是一種相對安全的策略。由于基準(zhǔn)元的位置是隨機(jī)的，那么產(chǎn)生的分割也不會總是會出現(xiàn)劣質(zhì)的分割。在整個數(shù)組數(shù)字全相等時，仍然是最壞情況，時間復(fù)雜度是O(n^2）。實(shí)際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為1/(2^n）。所以隨機(jī)化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達(dá)到O（n×log(n))的期望時間復(fù)雜度。

3、三數(shù)取中

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

三、partition算法

      partition算法是快速排序的核心，在學(xué)習(xí)快排之前，可以先學(xué)習(xí)一下這個算法。下面先貼代碼:

  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];  //獲取數(shù)組中間元素的下標(biāo)
    while (left<=right){         //從兩端交替向中間掃描
      while (num[left]prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最終將基準(zhǔn)數(shù)歸位 
        left++;
        right--;
      }
    }
    return left;
  }

當(dāng)前標(biāo)題：java簡單快速排序?qū)嵗馕?創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://weahome.cn/article/dgodih.html