亚洲日韩精品久久,午夜偷拍精品久久

快捷導(dǎo)航

java簡(jiǎn)單快速排序?qū)嵗馕?/h1>

更新時(shí)間：2017年08月11日 09:09:59 作者：五歲i

這篇文章主要為大家詳細(xì)介紹了java簡(jiǎn)單快速排序?qū)嵗?，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

一、基本概念

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

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

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

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

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

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

3、三數(shù)取中

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

三、partition算法

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

  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)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最終將基準(zhǔn)數(shù)歸位 
        left++;
        right--;
      }
    }
    return left;
  }

這個(gè)方法的思路是先找一個(gè)樞紐元（這個(gè)方法實(shí)現(xiàn)里面找的是第一個(gè)元素，具體其實(shí)大有文章不過(guò)這里先簡(jiǎn)化描述），再?gòu)臄?shù)組的兩邊（具體從哪里到哪里由傳進(jìn)來(lái)額參數(shù)決定）生成兩個(gè)指針left和right，每次發(fā)現(xiàn)左邊的元素大于樞紐元?jiǎng)ti停下來(lái)，右邊的元素小于樞紐元j就停下來(lái)，并且交換這個(gè)兩個(gè)數(shù)的位置。直到兩個(gè)指針left，right相遇。再把樞紐元插入left的位置，也就是它應(yīng)該在的位置。

這么做最后的結(jié)果是讓數(shù)組的[left，right]部分呈現(xiàn)出2部分，樞紐元最終位置以左都是小于等于樞紐元的，以右都是大于等于樞紐元的。而樞紐元?jiǎng)t被插入到了一個(gè)絕對(duì)正確的位置。

四、排序算法實(shí)現(xiàn)

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一個(gè)數(shù)組中取一個(gè)基準(zhǔn)數(shù)字，把小的數(shù)放基準(zhǔn)的左邊，大的數(shù)放基準(zhǔn)的右邊。
 * 基準(zhǔn)左邊和右邊分別是新的序列。在新的序列中再取一個(gè)基準(zhǔn)數(shù)字，小的放左邊，大的放右邊。
 * 這個(gè)里面用到的遞歸。我們需要三個(gè)參數(shù)，一個(gè)是數(shù)組，另外兩個(gè)是序列的邊界
 * @author HJS
 */
public class QuickSort{

  void sort(int num[],int left,int right){
    if (left<right){
      int index=partition(num,left,right); //算出樞軸值 
      sort(num,left,index-1);    //對(duì)低子表遞歸排序
      sort(num,index+1,right);    //對(duì)高子表遞歸排序
    }
  }

  /**
   * 調(diào)用partition(num,left,right)時(shí)，對(duì)num[]做劃分，
   * 并返回基準(zhǔn)記錄的位置
   * @param num
   * @param left
   * @param right
   * @return
   */
  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)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最終將基準(zhǔn)數(shù)歸位 
        left++;
        right--;
      }
    }
    return left;
  }


  public void swap(int[] num,int left,int right){
    int temp = num[left];
    num[left] = num[right];
    num[right] = temp;
  }
  public static void main(String args[]){
    int[] num={7,3,5,1,2,8,9,2,6};
    new QuickSort().sort(num,0,num.length-1);
    for(int n:num) {
      System.out.print(n+" ");
    }
  }
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: