快速排序

快速排序据说是21世纪伟大的发明之一，其思想也应用广泛。

核心

当前版本的快速排序，核心：

1. 首先从数组中寻找一个元素，把所有比该元素小的元素放到该元素的左边(从小到大)，所有比当前元素大的元素放到右边。
2. 当前元素的下标会变化到某个位置，运用递归，再进行第一步操作。

比如元素：
{6,202,100,301,38,8,1}

第一遍：我们默认从最左边的元素开始寻找那么最终结果：
{1, 6, 100, 301, 38, 8, 202}

过程：
我们每次进行比较之前需定义 两个下标：指向当前要比较的元素,指向小于该元素与大于该元素的分界点

1. 因为我们从最左边的元素开始比较，那么所有在该元素右边的位置只要比该元素大即可。
2. {6,202,100,301,38,8,1}如果6与元素比较，202，100等比6大，不用调换位置。
3. 当碰到比6小的元素，6右边第一个元素与1互换位置，将指向要交换的位置加1。

{6,1,202,100,301,38,8}

4. 将最左边的元素与刚才指向的元素下标交换位置
   {1, 6, 100, 301, 38, 8, 202}

5. 返回的下标为1，继续递归，回到第1步。分别比较下标[0,1],[2,6]之间的元素。

图解：

image.png image.png

如果：(e = arr[i]) > (v = arr[l])，那么，继续向下走

image.png

如果：(e = arr[i]) < (v = arr[l]):
那么把i下标的元素与橙色部分元素的最后一个位置交换位置，橙色区域仍然是小于v的元素
然后j++：

image.png

遍历完成之后：

image.png

最后一步操作：

image.png

代码

依赖：

• Lomhok插件

@Slf4j
public class QuickSort {
    public static void main(String[] args) {
        //代码不应该写死的，但为了测试，就写出固定的了。
        int[] a = {6,202,100,301,38,8,1};
        sort(a);
        log.info("排序完成数组{} ", a);
    }


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

    private static void sort(int[] arr, int l, int r) {
        if (l >= r){
            return;
        }
        
        //求下标的过程也被称为Partition，下标左边的元素全部小于arr[p]，下标右边的元素全部大于arr[p]
        int p = partition(arr,l,r);
        sort(arr,l,p);
        sort(arr,p + 1,r);

    }

    private static int partition(int[] arr, int l, int r) {
        int v = arr[l];
        int j = l;
        //为了查看效果，所以把日志都打印出来了。
        log.info("下标{} , {}",l,r);
        log.info("排序前数组{} ", arr);
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v){
                j++;
                Hepler.swap(arr,j,i);
                log.info("排序中数组{} ", arr);
            }
        }

        Hepler.swap(arr,l,j);
        log.info("排序后数组{} ", arr);
        return j;
    }


}

最后

这里演示了快速排序第一版的算法思想与流程，重点在于理解过程。