跟着AI学算法快速排序，剖析排序过程

快速排序是一种基于比较的排序算法，是排序算法中平均性能最优的一种算法之一。其基本思想是通过不断地选取一个基准值（pivot），将待排序序列划分为两个子序列，其中一个子序列中的所有元素都小于等于基准值，另一个子序列中的所有元素都大于基准值，然后对这两个子序列分别递归地进行排序，最终得到一个有序序列。

快速排序算法的关键在于如何选取基准值。一般来说，可以选择待排序序列的第一个元素、最后一个元素、中间元素或随机元素作为基准值。选定基准值之后，可以使用两个指针（i,j）分别从序列的左右两端向中间扫描，当i指向一个大于等于基准值的元素时，停止扫描；当j指向一个小于等于基准值的元素时，停止扫描。然后交换i和j指向的元素，继续扫描直到i>=j为止。最后将基准值与i指向的元素交换位置，即可完成一次划分。

执行过程请移步文章末尾：排序执行过程。

快速排序算法的时间复杂度为O(nlogn)（最坏情况下为O(n^2)），空间复杂度为O(logn)。

AI编码实现：

在该代码中，我们使用了两个函数，分别是quickSort和partition。其中，quickSort函数是递归调用的，它用来对整个数组进行排序。partition函数则用来将待排序数组划分为两部分，并返回枢轴的索引位置。在partition函数中，我们首先选取数组的第一个元素作为枢轴，并使用两个指针i和j分别从待排序序列的左右两端开始扫描。当i指向一个大于等于枢轴值的元素时，停止扫描；当j指向一个小于等于枢轴值的元素时，停止扫描。然后交换i和j指向的元素，继续扫描直到i>=j为止。最后将枢轴值与j指向的元素交换位置，即可完成一次划分。

本地测试：

为了能够打印排序过程，代码稍作修改。

package com.algorithm.sort;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] arr, int left, int right, int deep) {
        deep++;
        System.out.println("-------------------------------");
        System.out.println("递归深度："+deep+"; 开始");
        System.out.println("比较 left: "+left+", right: " + right+";");
        if (left < right) {
            System.out.println("排序数组："+Arrays.toString(Arrays.copyOfRange(arr, left, right+1)));
            System.out.println("递归深度："+deep+"; 开始排序，获取枢轴");
            int pivotIndex = partition(arr, left, right); // 将待排序数组划分为两部分，并返回枢轴的索引位置
            System.out.println("递归深度："+deep+"; 排序结束。枢轴：["+arr[pivotIndex]+"]; 新数组："+Arrays.toString(arr));
            System.out.println("开始枢轴：["+arr[pivotIndex]+"]左侧部分快速排序");
            quickSort(arr, left, pivotIndex - 1, deep); // 对左半部分进行快速排序
            System.out.println("开始枢轴：["+arr[pivotIndex]+"]右侧部分快速排序");
            quickSort(arr, pivotIndex + 1, right, deep); // 对右半部分进行快速排序
        } else {
            System.out.println("left >= right, 递归返回");
        }
        System.out.println("递归深度："+deep+"结束");
        System.out.println("-------------------------------");
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left]; // 选取数组的第一个元素作为枢轴
        int i = left + 1; // i指针从左端点开始
        int j = right; // j指针从右端点开始
        System.out.println("枢纽元素："+pivot+";比枢纽元素小放左边，比枢纽元素大放右边");
        while (i <= j) {
            while (i <= j) { // 从左端点开始找到第一个大于等于枢轴的元素
                System.out.println("左侧开始，下标i："+i+",比较：["+arr[i]+", "+pivot+"]");
                if (arr[i] >= pivot) {
                    System.out.println("比枢纽元素大，停止比较，该元素待交换");
                    break;
                }
                System.out.println("比枢纽元素小，不动，下标加1");
                i++;
            }
            while (i <= j) { // 从右端点开始找到第一个小于等于枢轴的元素
                System.out.println("右侧开始，下标j："+j+", 比较：["+arr[j]+", "+pivot+"]");
                if (arr[j] <= pivot) {
                    System.out.println("比枢纽元素小，停止比较，该元素待交换");
                    break;
                }
                System.out.println("比枢纽元素小，不动，下标减1");
                j--;
            }
            if (i < j) { // 交换i和j指向的元素
                System.out.println("交换["+arr[i]+", "+arr[j]+"];");
                swap(arr, i, j);
                System.out.println("左侧下标加1；右侧下标减1");
                i++;
                j--;
            } else {
                System.out.println("同一元素，不交换");
            }
            System.out.println("新数组："+Arrays.toString(Arrays.copyOfRange(arr, left, right+1)));
        }
        // 将枢轴值放到正确的位置上
        System.out.println("枢纽元素与小于枢纽元素的最后一个元素交换：["+pivot+", "+arr[j]+"]");
        swap(arr, left, j);

        return j;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 9, 1};
        System.out.println("选择排序");
        System.out.println("初始数组："+Arrays.toString(arr));
        System.out.println("==========================================");
        quickSort(arr, 0, arr.length - 1, 0);
        System.out.println("==========================================");
        System.out.print("最终数组："+Arrays.toString(arr));
    }
}

排序执行过程：

快速排序
初始数组：[5, 2, 8, 3, 9, 1]
==========================================
-------------------------------
递归深度：1; 开始
比较 left: 0, right: 5;
排序数组：[5, 2, 8, 3, 9, 1]
递归深度：1; 开始排序，获取枢轴
枢纽元素：5;比枢纽元素小放左边，比枢纽元素大放右边
左侧开始，下标i：1,比较：[2, 5]
比枢纽元素小，不动，下标加1
左侧开始，下标i：2,比较：[8, 5]
比枢纽元素大，停止比较，该元素待交换
右侧开始，下标j：5, 比较：[1, 5]
比枢纽元素小，停止比较，该元素待交换
交换[8, 1];
左侧下标加1；右侧下标减1
新数组：[5, 2, 1, 3, 9, 8]
左侧开始，下标i：3,比较：[3, 5]
比枢纽元素小，不动，下标加1
左侧开始，下标i：4,比较：[9, 5]
比枢纽元素大，停止比较，该元素待交换
右侧开始，下标j：4, 比较：[9, 5]
比枢纽元素小，不动，下标减1
同一元素，不交换
新数组：[5, 2, 1, 3, 9, 8]
枢纽元素与小于枢纽元素的最后一个元素交换：[5, 3]
递归深度：1; 排序结束。枢轴：[5]; 新数组：[3, 2, 1, 5, 9, 8]
开始枢轴：[5]左侧部分快速排序
-------------------------------
递归深度：2; 开始
比较 left: 0, right: 2;
排序数组：[3, 2, 1]
递归深度：2; 开始排序，获取枢轴
枢纽元素：3;比枢纽元素小放左边，比枢纽元素大放右边
左侧开始，下标i：1,比较：[2, 3]
比枢纽元素小，不动，下标加1
左侧开始，下标i：2,比较：[1, 3]
比枢纽元素小，不动，下标加1
同一元素，不交换
新数组：[3, 2, 1]
枢纽元素与小于枢纽元素的最后一个元素交换：[3, 1]
递归深度：2; 排序结束。枢轴：[3]; 新数组：[1, 2, 3, 5, 9, 8]
开始枢轴：[3]左侧部分快速排序
-------------------------------
递归深度：3; 开始
比较 left: 0, right: 1;
排序数组：[1, 2]
递归深度：3; 开始排序，获取枢轴
枢纽元素：1;比枢纽元素小放左边，比枢纽元素大放右边
左侧开始，下标i：1,比较：[2, 1]
比枢纽元素大，停止比较，该元素待交换
右侧开始，下标j：1, 比较：[2, 1]
比枢纽元素小，不动，下标减1
同一元素，不交换
新数组：[1, 2]
枢纽元素与小于枢纽元素的最后一个元素交换：[1, 1]
递归深度：3; 排序结束。枢轴：[1]; 新数组：[1, 2, 3, 5, 9, 8]
开始枢轴：[1]左侧部分快速排序
-------------------------------
递归深度：4; 开始
比较 left: 0, right: -1;
left >= right, 递归返回
递归深度：4结束
-------------------------------
开始枢轴：[1]右侧部分快速排序
-------------------------------
递归深度：4; 开始
比较 left: 1, right: 1;
left >= right, 递归返回
递归深度：4结束
-------------------------------
递归深度：3结束
-------------------------------
开始枢轴：[3]右侧部分快速排序
-------------------------------
递归深度：3; 开始
比较 left: 3, right: 2;
left >= right, 递归返回
递归深度：3结束
-------------------------------
递归深度：2结束
-------------------------------
开始枢轴：[5]右侧部分快速排序
-------------------------------
递归深度：2; 开始
比较 left: 4, right: 5;
排序数组：[9, 8]
递归深度：2; 开始排序，获取枢轴
枢纽元素：9;比枢纽元素小放左边，比枢纽元素大放右边
左侧开始，下标i：5,比较：[8, 9]
比枢纽元素小，不动，下标加1
同一元素，不交换
新数组：[9, 8]
枢纽元素与小于枢纽元素的最后一个元素交换：[9, 8]
递归深度：2; 排序结束。枢轴：[9]; 新数组：[1, 2, 3, 5, 8, 9]
开始枢轴：[9]左侧部分快速排序
-------------------------------
递归深度：3; 开始
比较 left: 4, right: 4;
left >= right, 递归返回
递归深度：3结束
-------------------------------
开始枢轴：[9]右侧部分快速排序
-------------------------------
递归深度：3; 开始
比较 left: 6, right: 5;
left >= right, 递归返回
递归深度：3结束
-------------------------------
递归深度：2结束
-------------------------------
递归深度：1结束
-------------------------------
==========================================
最终数组：[1, 2, 3, 5, 8, 9]