快速排序（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);
    }
}