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

快速排序的思想：

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

對(duì)待排序序列進(jìn)行劃分：

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

圖示劃分：

代碼實(shí)現(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));
    }
 
    //排序方法-假設(shè)從小到大排序
    public static void quickSort(Integer[] arr,int low,int high){
        if(low < high){
            int part=partition(arr,low,high);
            //遞歸調(diào)用
            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];
        //從兩端交替向內(nèi)掃描
        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];
        }
        //設(shè)置樞軸
        arr[low]=pivot;
        //返回樞軸元素位置
        return low;
    }
 
}

空間效率：

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

時(shí)間效率：

快速排序算法的運(yùn)行時(shí)間依賴于劃分是否平衡，即根據(jù)樞軸元素 pivot 將序列劃分為兩個(gè)子序列中的元素個(gè)數(shù)，而劃分是否平衡又依賴于所使用的樞軸元素。下面我們?cè)诓煌那闆r下來分析快速排序的漸進(jìn)時(shí)間復(fù)雜度。

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

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

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

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

最新評(píng)論