快速排序

核心思想：

1、选取一个左边第一个元素为基数，从两头遍历集合( i、j 分别从两端索引)

2、i 索引大于 基数的 值，j 索引小于 基数的值 （j 先索引，然后 i 索引，当遇到符合的条件时停止索引）

3、交换两个索引的数值，然后继续索引

4、当 i 与 j 相遇时 结束当前索引

5、将基数所在位置与 i，j 所索引位置的值进行交换

6、递归调用两端的集合

快速排序的时间复杂度为O(log2N)

package com.jason.sort;

/**
 * @program: LeetCode
 * @description: 快速排序
 * @author: CodeDuck
 * @create: 2020-07-17 20:23
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {6, 7, 18, 3, 5, 4, 10, 9};
        quickSort(arr);
        for (int a : arr) {
            System.out.println(a);
        }
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * @Description: 快速排序
     * @Param: int[] 数组
     */
    private static void quickSort(int[] arr, int left, int right) {

        if (left >= right) {    // 当满足条件时结束当前递归
            return;
        }

        int i = left;   // 左索引
        int j = right;  // 右索引

        // 从数组的最左端开始，选取基准数
        int baseNum = arr[left];

        // 关于为什么是 右边的 J 先走问题
        // 此排序为升序排序，如果 I 先走，走到最后与J相遇是主动跑到J位置上
        // 此时的数是大于基数的，不能将此数同基数交换
        while (i < j) {
            while (arr[j] >= baseNum && i < j) {    // 从右至左选择小于基数的数
                j--;
            }
            while (arr[i] <= baseNum && i < j) {    // 从左至右选择大于基数的数
                i++;
            }

            if (i < j) {
                swap(arr, i, j);                    // 交换两个数值
            }
        }

        arr[left] = arr[i];                         // 将当前i与j相遇的值与技术交换
        arr[i] = baseNum;

        quickSort(arr, left, i - 1);            // 递归调用基数左边的集合
        quickSort(arr, i + 1, right);            // 递归调用基数右边的集合

    }

    /**
     * @Description: 交换元素
     * @Param: arr 元素组
     * @Param: i，j数组下标
     * @return: void
     */
    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快速排序

原文：https://www.cnblogs.com/code-duck/p/13332842.html