1.快速排序簡(jiǎn)介

快速排序是對(duì)冒泡排序的一種改進(jìn)?；舅枷霝椋和ㄟ^一趟排序?qū)⒁判虻臄?shù)據(jù)分割為獨(dú)立的兩個(gè)部分，其中一部分的所有數(shù)據(jù)比另外一部分的所有數(shù)據(jù)要小，然后按照此方法對(duì)這兩部分分別進(jìn)行快速排序，整個(gè)過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

2.思路簡(jiǎn)介及圖解

快速排序算法通過多次比較和交換來實(shí)現(xiàn)排序，其排序流程如下：

(1)首先設(shè)定一個(gè)分界值，通過該分界值將數(shù)組分成左右兩部分。

(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于或等于分界值。

(3)然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。

(4)重復(fù)上述過程，可以看出，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。

光看思路簡(jiǎn)介其實(shí)還不是很好理解，下面來舉例說明

一般情況下，我們會(huì)把數(shù)組中的一個(gè)數(shù)當(dāng)作基準(zhǔn)數(shù)（方便起見，會(huì)將數(shù)組最左邊的當(dāng)作基準(zhǔn)數(shù)），然后從兩邊進(jìn)行檢索。按照如下步驟進(jìn)行：

• 先從右邊檢索比基準(zhǔn)數(shù)小的
• 再從左邊檢索比基準(zhǔn)數(shù)大的
• 一旦檢索到，就停下，并將檢索到的兩個(gè)元素進(jìn)行交換
• 重復(fù)上述步驟，直到檢索相遇，則替換基準(zhǔn)數(shù)，并更新區(qū)間，遞歸進(jìn)行
• 最終序列會(huì)變得有序

思路圖解：

該圖出自網(wǎng)絡(luò)，方便起見就以序列：{6，1，8，0，0，9，5，3，7} 為例子

具體分析一下第一趟排序：以6為基準(zhǔn)數(shù)的步驟

1.紅色塊標(biāo)識(shí)基準(zhǔn)數(shù)，left、right初始位置如圖所示：

2.right不斷向左移動(dòng)，尋找比基準(zhǔn)數(shù)小的數(shù)，如圖所示，找到了3

3.此時(shí)left開始移動(dòng)，不斷向右移動(dòng)，尋找比基準(zhǔn)數(shù)大的數(shù)，找到了8，這時(shí)，left、right都找到了對(duì)應(yīng)的數(shù)，進(jìn)行交換：

4.right繼續(xù)向左尋找比基準(zhǔn)數(shù)6小的數(shù)，找到后，left繼續(xù)向右尋找比基準(zhǔn)數(shù)大的數(shù)，當(dāng)left與right都找到對(duì)應(yīng)的數(shù)后，再次進(jìn)行交換。

5.重復(fù)上述步驟，right繼續(xù)向左走，但是此時(shí)，left與right相遇，指向了5的位置，則將基準(zhǔn)數(shù)與該位置的數(shù)進(jìn)行交換，這樣就可以觀察到，6的左邊都是比6小的，右邊都是比6大的。

6.該過程需要遞歸進(jìn)行，直到序列有序。即以5為基準(zhǔn)數(shù)，遞歸6左邊的區(qū)間，再遞歸右邊的，反復(fù)進(jìn)行，直到left >right退出。

3.實(shí)現(xiàn)代碼及運(yùn)行結(jié)果

import java.util.Arrays;

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {6,1,8,0,0,9,5,3,7};
        quickSort(arr, 0, arr.length-1);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    //快速排序
    public static void quickSort(int[] arr, int left, int right) {
        //邊界條件
        if (left > right){
            return;
        }

        //定義基準(zhǔn)數(shù)和左右指針
        int l = left;
        int r = right;
        int base = arr[left];

        //循環(huán)，將比基準(zhǔn)數(shù)小的放在左邊，比基準(zhǔn)數(shù)大的放在右邊
        while (l != r){
            //先從右邊找比基準(zhǔn)數(shù)小的，停下
            while (arr[r] >= base && l < r){
                r--;
            }
            //從左邊找比基準(zhǔn)數(shù)大的，停下
            while (arr[l] <= base && l < r){
                l++;
            }
            //此時(shí)已經(jīng)找到對(duì)應(yīng)的l 和 r，進(jìn)行交換
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //至此，基準(zhǔn)數(shù)兩邊都按照需要排好了，只需要將基準(zhǔn)數(shù)與lr相遇的位置進(jìn)行交換
        arr[left] = arr[l];
        arr[l] = base;
        //打印中間結(jié)果
        System.out.println(Arrays.toString(arr));
        //先向左找
        quickSort(arr, left, r-1);
        //向右遞歸
        quickSort(arr, l+1, right);
    }
}

實(shí)現(xiàn)結(jié)果：

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

最新評(píng)論