快捷導(dǎo)航

java數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解

更新時(shí)間：2017年05月03日 10:59:53 作者：android小豬

這篇文章主要介紹了java數(shù)據(jù)結(jié)構(gòu)與算法之快速排序,結(jié)合實(shí)例形式詳細(xì)分析了快速排序的原理、實(shí)現(xiàn)步驟、相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了java數(shù)據(jù)結(jié)構(gòu)與算法之快速排序。分享給大家供大家參考，具體如下：

交換類排序的另一個(gè)方法，即快速排序。

快速排序：改變了冒泡排序中一次交換僅能消除一個(gè)逆序的局限性，是冒泡排序的一種改進(jìn)；實(shí)現(xiàn)了一次交換可消除多個(gè)逆序。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

步驟:

1、從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot）；
2、重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
3、遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

算法實(shí)現(xiàn)代碼如下：

package exp_sort;
public class QuickSort {
  public static void Qsort(int array[], int left, int right) {
    int pos;
    if (left < right) {
      pos = quickSort(array, left, right);
      //遞歸排序
      Qsort(array, left, pos - 1);
      Qsort(array, pos + 1, right);
    }
  }
  /**
   * 一趟快速排序
   *
   * @param array
   * @param left
   * @param right
   * @return
   */
  public static int quickSort(int array[], int left, int right) {
    int low, high;
    int temp = array[left]; // 選擇基準(zhǔn)記錄（樞紐元）
    low = left;
    high = right;
    while (low < high) {
      // high從右到左找小于temp的記錄
      while (low < high && array[high] >= temp) {
        high--;
      }
      // 找到小于temp的記錄則交換
      if (low < high) {
        array[low] = array[high];
        low++;
      }
      // low從左到右找到大于temp的記錄
      while (low < high && array[low] < temp) {
        low++;
      }
      // 找到大于temp的記錄，則交換
      if (low < high) {
        array[high] = array[low];
        high--;
      }
    }
    //將游標(biāo)放在當(dāng)前位置，此時(shí)low=high
    array[low] = temp;
    return low;
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    Qsort(array, 0, 7);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

樞紐元的選取：

1、基本的快速排序：選取地一個(gè)元素作為樞紐元。實(shí)際中應(yīng)盡量避免將第一個(gè)元素作為樞紐元（極端情況是：初始狀態(tài)是已排好序或者反序的）。

2、隨機(jī)化快排序 : 隨機(jī)的選取樞紐元。

3、平衡快排 : 三數(shù)中值分割法：樞紐元的最好選擇是數(shù)組中的中值，該中值，即左端、右端和中心位置上的三個(gè)元素的中值（推薦）。

算法分析：該算法是在實(shí)踐中最快的一種排序算法，它的平均運(yùn)行時(shí)間是O(N log N)，該算法之所以快，主要是由于非常精煉和高度優(yōu)化的內(nèi)部循環(huán)。它的最壞情況的性能是O(N^2)，但是這種情況可以改變?？焖倥判蚴且环N分治的遞歸算法。該算法比歸并排序算法排序快。

1、最壞情況的分析

當(dāng)樞紐元是最小元素時(shí)，此時(shí)就相當(dāng)于是對(duì)整個(gè)數(shù)組進(jìn)行遞歸排序，時(shí)間復(fù)雜度為：O(N^2)

2、最好情況的分析

樞紐元正好位于中間，此時(shí)是對(duì)兩個(gè)子數(shù)組進(jìn)行遞歸排序，時(shí)間復(fù)雜度是：O(N log N)，這和歸并排序的分析完全相同。

3、平均情況的分析

時(shí)間復(fù)雜度是：O( N log N)

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: