1.快速排序簡介

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

2.思路簡介及圖解

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

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

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

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

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

光看思路簡介其實還不是很好理解，下面來舉例說明

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

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

思路圖解：

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

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

1.紅色塊標識基準數(shù)，left、right初始位置如圖所示：

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

3.此時left開始移動，不斷向右移動，尋找比基準數(shù)大的數(shù)，找到了8，這時，left、right都找到了對應的數(shù)，進行交換：

4.right繼續(xù)向左尋找比基準數(shù)6小的數(shù)，找到后，left繼續(xù)向右尋找比基準數(shù)大的數(shù)，當left與right都找到對應的數(shù)后，再次進行交換。

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

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

3.實現(xià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;
        }

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

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

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

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

最新評論