Java基礎算法之快速排序（Quick Sort）

快速排序（Quick Sort）

• • • 1、算法介紹（遞歸）
    • 2、舉例示範
    • 3、圖解
    • 4、代碼實作
    • 5、執行結果
    • 6、其他排序

1、算法介紹（遞歸）

1. 首先确認一個分界值（這裡使用中間的數），然後通過分界值将數組分為左右兩部分。
2. 使用左右指針進行周遊，左指針指向大于分界值的資料，右指針指向小于分界值的資料，然後左右指針進行交換資料，交換後左指針進行前移，右指針進行後移
3. 将小于分界值的資料放到分界值的左邊，将大于分界值的資料放到分界值的右邊。
4. 然後将左右兩邊各取一個分界值，同樣将小于分界值的資料放到分界值的左邊，大于分界值的資料放到分界值的右邊。

2、舉例示範

原數組：[117, 101, 106, 100, 112, 60, 90, 110]

分界值：100

左指針指向：117

右指針指向：60

然後進行交換

交換後：[90, 101, 106, 100, 112, 60, 117, 110]

重複執行，知道分界值左邊全部小于分界值和分界值右邊全部大于分界值。

執行結果：[90, 60, 100, 106, 112, 101, 117, 110]

此時左指針指向下标：3

此時右指針指向下标：2

然後再将 [0, 左指針 - 1] 數組重複上面過程

然後再将 [右指針 + 1, 7] 數組重複上面過程

詳細見圖解

3、圖解

4、代碼實作

package sort;

import java.util.Arrays;

/**
 * <p>
 *
 * </p>
 *
 * @author: D
 * @since: 2020/9/10
 * @version: 1
 */
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] arr = {117, 101, 106, 100, 112, 60, 90, 110};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序後的結果： " + Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int left, int right) {
        System.out.println();
        System.out.printf("周遊的數組範圍[%d, %d]", left, right);
        //左右下标
        int leftIndex = left;
        int rightIndex = right;
        int pivot = arr[(left + right) / 2];
        System.out.println();
        System.out.println("基準值 = " + pivot);
        int temp;
        //讓比pivot小的放到左邊，大的放到右邊
        while (leftIndex < rightIndex) {
            //左邊尋找大于等于pivot的值才推出
            while (arr[leftIndex] < pivot) {
                leftIndex++;
            }
            //右邊邊尋找小于等于pivot的值才推出
            while (arr[rightIndex] > pivot) {
                rightIndex--;
            }
            //如果成立 說明pivot左右兩邊的值已經是小于等于大于小于pivot的值
            if (leftIndex >= rightIndex) {
                break;
            }
            System.out.println("交換前結果： " + Arrays.toString(arr));
            System.out.println("目前左指針：" + leftIndex + "，指向的資料：" + arr[leftIndex]);
            System.out.println("目前右指針 = " + rightIndex+ "，指向的資料：" + arr[rightIndex]);
            // 左指針沒有超過右指針 然後将左指針和右指針進行交換
            //交換
            temp = arr[leftIndex];
            arr[leftIndex] = arr[rightIndex];
            arr[rightIndex] = temp;

            //如果交換完後發現arr[leftIndex] == pivot的值 将右指針前移
            if (arr[leftIndex] == pivot) {
                System.out.println("交換完後發現arr[rightIndex] == pivot的值 将左指針後移");
                rightIndex--;
            }
            //如果交換完後發現arr[rightIndex] == pivot的值 将左指針後移
            if (arr[rightIndex] == pivot) {
                System.out.println("交換完後發現arr[rightIndex] == pivot的值 将左指針後移");
                leftIndex++;
            }

            System.out.println("交換的結果： " + Arrays.toString(arr));
            System.out.println("交換後左指針 = " + leftIndex);
            System.out.println("交換後右指針 = " + rightIndex);
        }
        System.out.println("之後的左右指針");

        //左右指針相同 将右指針前移 左指針後移
        if (leftIndex == rightIndex) {
            System.out.println("左右指針相同 将右指針前移 左指針後移");
            leftIndex++;
            rightIndex--;
        }
        System.out.println("leftIndex：" + leftIndex);
        System.out.println("rightIndex：" + rightIndex);
        System.out.println("left: " + left);
        System.out.println("right: " + right);

        // 兩個條件都不滿足則排序完成
        if (left < rightIndex) {
            quickSort(arr, left, rightIndex);
        }
        if (leftIndex < right) {
            quickSort(arr, leftIndex, right);
        }
    }
}

           

5、執行結果

6、其他排序

選擇排序（Selection Sort）

插入排序（Insertion Sort）

希爾排序（Shell Sort）

冒泡排序（Bubble Sort）

堆排序（Heap Sort）