快速掌握java排序演算法-快速排序（圖文）

概念

快速排序屬於交換排序，主要步驟是使用基準元素進行比較，把小於基準元素的移動到一邊，大於基準元素的移動到另一邊。從而把陣列分成兩部分，然後再從這兩部分選取出基準元素，重複上面的步驟。流程如下：

（推薦影片：java影片教學）  

紫色：基準元素
綠色：大於基準元素
黃色：小於基準元素

這種想法叫做分治法。

基準元素

基準元素的選取可隨機選取。下面使用中我會使用第一位的元素作為基準元素。

排序過程

排序分割過程如下圖：

紫色為基準元素，（每一輪都重新選取）
綠色為其他元素

第一輪

第二輪

##第三輪

如上圖所示：

若元素個數為n，因為排序過程中需要和全部元素都比較一遍，所以時間複雜度為O(n)，

而平均情況下排序輪次需要logn輪，因此快速排序的平均時間複雜度為O(nlogn)。

排序的實作方法

實作方法有雙邊循環法和單邊循環法

雙邊循環法

首選選取基準元素(pivot)4，並設定指標left和right，指向陣列最左和最右兩個元素，如下：

##第一次循環，先從right指針指向的資料(rightData)開始和基準元素比較

若rightData >= pivot，則right指針向左移動，若rightData left指標指向資料(leftData)與基準元素比較，若leftData pivot，交換left和right指向的元素。

第一輪指標移動完後，得到如下結構：

#然後left和right指向的元素進行交換：

第一輪循環結束，重新切換到right指針，重複上述步驟。

第二輪循環後，得：

第三輪循環後，得：

第四輪循環後，得：

判斷到left和right指標指向同一個元素，指標停止移動，使pivot和指標元素進行交換，得：

宣告該輪迴圈結束，並依照Pivot元素切分為兩部分，這兩部分的陣列再依照上述步驟進行操作。

實作程式碼

public class DoubleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left = pivot) {
                right--;
            }

            // 控制left指针比较并右移
            while (left 

單邊迴圈法

雙邊迴圈法從陣列的兩邊比較並交換元素，而單邊循環法則從陣列的一邊遍歷，一直往後比較和交換，實現起來更加的簡單。

流程如下：

首先也是選取基準元素pivot（可以隨機選擇）

設定一個mark指標指向陣列的起始位置，代表小於基準元素的區域邊界（不理解的就把它理解成是等會用來交換元素的就好了）

原始數組如下：

##

从基准元素下一位开始遍历数组
如果该元素大于基准元素，继续往下遍历
如果该元素小于基准元素，mark指针往右移，因为小于基准元素的区域边界增大了1（即小于基准元素的多了1位），所以mark就 +1，并且该元素和mark指向元素进行交换。

遍历到元素3时，因为3

然后交换元素

然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。

实现代码

public class SingleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 分治（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int mark = startIndex;

        for(int i = startIndex + 1; i<p id="总结" style="white-space: normal;"><strong>总结</strong></p><p>本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。</p><p>参考资料：《小灰的算法之旅》 第四章。</p><p>本文来自php中文网，<a href="https://www.php.cn/java/base/" target="_blank">java教程</a>栏目，欢迎学习！  </p>

以上是快速掌握java排序演算法-快速排序（圖文）的詳細內容。更多資訊請關注PHP中文網其他相關文章！