北大青鳥北京，通州北大青鳥校區學術部：Java的排序之“快速排序”

北京北大青鳥通州校區學術部老師講解：什么是快速排序？

北京北大青鳥專家解答：快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。最壞情況的時間復雜度為O(n2)，最好情況時間復雜度為O(nlog2n)。 （北京北大青鳥）

另外 java沒指針概念 可以認為是句柄

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一躺快速排序。一趟快速排序的算法是： （北京北大青鳥）

1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N；

2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換；

4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換；

5）、重復第3、4步，直到I=J；

例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）

                  A[1]    A[2]    A[3]    A[4]    A[5]     A[6]    A[7]：

                    49       38      65      97      76      13       27

進行第一次交換后： 27       38      65      97      76      13       49

                  ( 按照算法的第三步從后面開始找)

進行第二次交換后： 27       38      49      97      76      13       65

                 ( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )

進行第三次交換后： 27       38      13      97      76      49       65

( 按照算法的第五步將又一次執行算法的第三步從后開始找)

進行第四次交換后： 27       38      13      49      76      97       65

( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 )

     此時再執行第三步的時候就發現I=J，從而結束一躺快速排序，那么經過一躺快速排序之后的結果是：27       38      13      49      76      97       65，即所以大于49的數全部在49的后面，所以小于49的數全部在49的前面。 （北京北大青鳥）

     快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最后把此數據序列變成一個有序的序列，根據這種思想對于上述數組A的快速排序的全過程：

初始狀態                       {49    38    65    97    76    13    27}  

進行一次快速排序之后劃分為     {27    38    13}    49 {76    97    65}

分別對前后兩部分進行快速排序   {13}   27   {38}

                               結束        結束   {49   65}   76   {97}

                                                   49 {65}        結束

                                                       結束

//下面是一個示例,
public class QuickSort {
/**主方法*/
public static void main(String[] args) {
    //聲明數組
    int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5};
    //應用快速排序方法
    quickSort(nums, 0, nums.length-1);
    //顯示排序后的數組
    for(int i = 0; i < nums.length; ++i) {
      System.out.print(nums[i] + ",");
    }
    System.out.println("");
}

/**快速排序方法*/
public static void quickSort(int[] a, int lo0, int hi0) {
    int lo = lo0;
    int hi = hi0;

    if (lo >= hi)
      return;

    //確定指針方向的邏輯變量
    boolean transfer=true;

    while (lo != hi) {
      if (a[lo] > a[hi]) {
        //交換數字
        int temp = a[lo];
        a[lo] = a[hi];
        a[hi] = temp;
        //決定下標移動，還是上標移動
        transfer = (transfer == true) ? false : true;
      }

      //將指針向前或者向后移動
      if(transfer)
        hi--;
      else
        lo++;

      //顯示每一次指針移動的數組數字的變化
      /*for(int i = 0; i < a.length; ++i) {
        System.out.print(a[i] + ",");
      }
      System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
      System.out.println("");*/
    }

    //將數組分開兩半，確定每個數字的正確位置
    lo--;
    hi++;
    quickSort(a, lo0, lo);
    quickSort(a, hi, hi0);
}
}
（北京北大青鳥）

相關鏈接：Java的排序之“堆排序”