DIV CSS 佈局教程網

快速排序原理深入解析與 Java 實作
編輯:關於JavaScript     

快速排序(Quick Sort)因為高效而被廣泛使用,Sun 的 JDK 中 Arrays.sort 對基本型別陣列採用的正是快排。它體現了經典的分治思想(divide and conquer)。

三個步驟

Divide(分割):選取一個基元 X(通常取陣列第一個元素),透過分區操作(partitioning)把陣列切成兩半:左半部分小於等於 X,右半部分大於等於 X。

Conquer(求解):對左右兩個子陣列遞歸地呼叫 Divide 過程。

Combine(合併):快排是就地排序(in place sort),不需要任何合併操作。

分區過程詳解

快排的核心就在分區。以《算法導論》的經典範例說明:

初始化:選取基元 P = 2(陣列首元素),令 i = 1,j = i + 1 = 2(陣列下標從 1 開始)。

循環不變量:2 到 i 之間的元素都小於或等於 P,i+1 到 j 之間的元素都大於或等於 P。

循環過程:j 從 2 走到 n,逐一考察 j 位置的元素。若它大於或等於 P,繼續循環;若小於 P,就把 j 位置的元素與 i+1 位置的元素交換,並將 i 加一。這樣就維持了上述循環不變量。

循環結束後還有一個關鍵動作:必須把 i 位置的元素與陣列首元素交換,才能把基元放到最終的正確位置。

為什麼要就地排序

有人會想到更直白的做法:把基元另外存到一個同樣大小的陣列中,遇到比它小的放左半部,比它大的放右半部。這種做法時間複雜度同樣是 Θ(n),但空間複雜度多了一倍。就地排序正是快排在實用上的優勢所在。

Java 實作

public class QuickSort {
  private static void QuickSort(int[] array, int start, int end)
  {
    if (start < end)
    {
      int key = array[start];   // 初始化保存基元
      int i = start, j;         // 初始化 i, j
      for (j = start + 1; j <= end; j++)
        // 若此處元素小於基元,就與 i+1 處元素交換並將 i 加一;否則繼續循環
        if (array[j] < key)
        {
          int temp = array[j];
          array[j] = array[i + 1];
          array[i + 1] = temp;
          i++;
        }

      array[start] = array[i];  // 交換 i 處元素和基元
      array[i] = key;

      QuickSort(array, start, i - 1);   // 遞歸調用
      QuickSort(array, i + 1, end);
    }
  }

  public static void main(String[] args)
  {
    int[] array = new int[]{11, 213, 134, 44, 77, 78, 23, 43};
    QuickSort(array, 0, array.length - 1);
    for (int i = 0; i < array.length; i++)
    {
      System.out.println((i + 1) + "th:" + array[i]);
    }
  }
}

快排的平均時間複雜度為 O(n log n),但最壞情況(例如陣列已排序且每次固定取首元素為基元)會退化到 O(n²)。實務上的改善方式是隨機選取基元,或在遞歸深度過大時改用插入排序處理小區間。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved