快速排序（QuickSort）Java版

• 2021 年 4 月 10 日
• 筆記
• 算法

快速排序
　　快速排序是對冒泡排序的一種改進。
　　它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，
整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
　　快速排序算法中,每一次遞歸時以第一個數為基準數,找到數組中所有比基準數小的.再找到所有比基準數大的.小的全部放左邊,大的全部放右邊,確定基準數的正確位置
核心思想：分治思想
時間複雜度：O(n)
實現步驟
      1，從右開始找比基準數小的
      2，從左開始找比基準數大的
      3，交換兩個值的位置
      4，紅色繼續往左找，藍色繼續往右找，直到兩個箭頭指向同一個索引為止
      5，基準數歸位

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        //1、創建數組
        int arr[] = {6, 1, 3, 5, 8, 9, 10, 2, 4, 7, 1};
        //2、調用快排方法
        quickSort(arr, 0, arr.length - 1);
        //3、打印數組
        System.out.println(Arrays.toString(arr));
    }
    //快速排序
    private static void quickSort(int[] arr, int left, int right) {
        //遞歸結束條件
        if (right < left) {
            return;
        }
        //定義兩個遍歷存放初始的left和right方便後面歸為
        int left1 = left;
        int right1 = right;
        //確定出基準數
        int baseNumber = arr[left1];
        //定義一個交換變量
        int temp;
        //排序
        while (left != right) {
            //2.1、從右邊開始找比基準數小的
            while (arr[right] >= baseNumber && right > left) {
                right--;
            }
            //2.2、從左邊開始找比基準數大的
            while (arr[left] <= baseNumber && right > left) {
                left++;
            }
            //2.3、交換兩個值得位置
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        //基準數歸為
        temp = arr[left];
        arr[left] = arr[left1];
        arr[left1] = temp;
        //遞歸調用，將左半部分排好序
        quickSort(arr, left1, left - 1);
        //遞歸調用，將由半部分排好序
        quickSort(arr, left1 + 1, right1);
    }
}