交換類排序主要是通過兩兩比較待排元素的關鍵字，若發(fā)現(xiàn)與排序要求相逆，則“交換”之。在這類排序方法中最常見的是冒泡排序和快速排序。上一篇簡單寫了冒泡排序，這次簡單寫一寫快速排序。

快速排序的思想：

快速排序是將分治法運用到排序問題中的一個典型例子，其基本思想是：通過一個樞軸（pivot）元素將 n 個元素的序列分為左、右兩個子序列 Ll 和 Lr，其中子序列 Ll中的元素均比樞軸元素小，而子序列 Lr 中的元素均比樞軸元素大，然后對左、右子序列分別進行快速排序，在將左、右子序列排好序后，則整個序列有序，而對左右子序列的排序過程直到子序列中只包含一個元素時結束，此時左、右子序列由于只包含一個元素則自然有序。

對待排序序列進行劃分：

使用兩個指針 low 和 high 分別指向待劃分序列 r 的范圍，取 low 所指元素為樞軸，即 pivot = r[low]。劃分首先從 high 所指位置的元素起向前逐一搜索到第一個比 pivot 小的元素，并將其設置到 low 所指的位置；然后從 low 所指位置的元素起向后逐一搜索到第一個比 pivot 大的元素，并將其設置到 high 所指的位置；不斷重復上述兩步直到 low = high 為止，最后將 pivot 設置到 low 與 high 共同指向的位置。

圖示劃分：

代碼實現(xiàn)：

import java.util.Arrays;
 
public class QuickSortTest {
    public static void main(String[] args){
        Integer[] arr = {5,2,7,3,9,10,8,6,1,4};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
 
    //排序方法-假設從小到大排序
    public static void quickSort(Integer[] arr,int low,int high){
        if(low < high){
            int part=partition(arr,low,high);
            //遞歸調用
            quickSort(arr,low,part-1);
            quickSort(arr,part+1,high);
        }
    }
 
    //劃分方法
    private static int partition(Integer[] arr,int low,int high){
        //使用 r[low]作為樞軸元素
        int pivot = arr[low];
        //從兩端交替向內掃描
        while(low < high){
            while(low<high && arr[high] >= pivot) {high--;}
            //將比 pivot 小的元素移向低端
            arr[low] = arr[high];
            while(low<high && arr[low] <= pivot){low++;}
            //將比 pivot 大的元素移向高端
            arr[high] = arr[low];
        }
        //設置樞軸
        arr[low]=pivot;
        //返回樞軸元素位置
        return low;
    }
 
}

空間效率：

快速排序需要一個堆棧來實現(xiàn)遞歸。若每次劃分都將序列均勻分割為長度相近的兩個子序列，則堆棧的最大深度為 log n，但是，在最壞的情況下，堆棧的最大深度為 n。

時間效率：

快速排序算法的運行時間依賴于劃分是否平衡，即根據(jù)樞軸元素 pivot 將序列劃分為兩個子序列中的元素個數(shù)，而劃分是否平衡又依賴于所使用的樞軸元素。下面我們在不同的情況下來分析快速排序的漸進時間復雜度。

快速排序的最壞情況是，每次進行劃分時，在所得到的兩個子序列中有一個子序列為空。在快速排序過程中，如果總是選擇r[low]作為樞軸元素，則在待排序序列本身已經(jīng)有序或逆向有序時，快速排序的時間復雜度為Ο(n2)。

快速排序的最好情況是，在每次劃分時，都將序列一分為二，正好在序列中間將序列分成長度相等的兩個子序列。此時，算法的時間復雜度T(n) = Θ(n log n)。

在平均情況下，快速排序的時間復雜度 T(n) = kn ㏑ n，其中 k 為某個常數(shù)，經(jīng)驗證明，在所有同數(shù)量級的排序方法中，快速排序的常數(shù)因子 k 是最小的。因此就平均時間而言，快速排序被認為是目前最好的一種內部排序方法。
快速排序的平均性能最好，但是，若待排序序列初始時已按關鍵字有序或基本有序，則快速排序退化為冒泡排序，其時間復雜度為Ο(n2)。為改進之，可以采取隨機選擇樞軸元素pivot的方法，具體做法是，在待劃分的序列中隨機選擇一個元素然后與r[low]交換，再將r[low]作為樞軸元素，作如此改進之后將極大改進快速排序在序列有序或基本有序時的性能，在待排序元素個數(shù)n較大時，其運行過程中出現(xiàn)最壞情況的可能性可以認為不存在。

到此這篇關于Java快速排序案例講解的文章就介紹到這了,更多相關Java快速排序詳解內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論