快速排序（Quick Sort）是一种常用的排序算法，采用分治法（Divide and Conquer）进行排序。其基本思路是通过选择一个基准元素（pivot），将待排序的数组分成两部分，一部分所有元素都小于基准元素，另一部分所有元素都大于基准元素。然后递归地对这两部分继续进行排序，最终达到排序整个数组的效果。

快速排序的步骤：

1. 选择基准元素：选择数组中的一个元素作为基准元素（常见的选择有第一个元素、最后一个元素、随机选择等）。
2. 分区操作：将数组分成两部分，小于基准的放左边，大于基准的放右边。基准元素最终的位置已经确定。
3. 递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序，直到子数组的大小为1或0，排序完成。

时间复杂度：

• 最佳情况：O(n log n)，发生在每次分割时都能平衡地分成两部分。
• 最坏情况：O(n^2)，当数组已经有序或反向有序时，每次选择的基准元素都可能是最小或最大的元素，从而导致不均匀的分割。
• 平均情况：O(n log n)，在大多数情况下，快速排序的时间复杂度表现良好。

空间复杂度：

• 快速排序是原地排序，只需要 O(log n) 的栈空间来存储递归调用的状态。
• 空间复杂度主要取决于递归的深度，最坏情况下是 O(n)，但平均情况下是 O(log n)。

快速排序的Java实现代码：

public class QuickSort {

    // 主函数：调用快速排序
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSortHelper(arr, 0, arr.length - 1);
    }

    // 快速排序的核心递归函数
    private static void quickSortHelper(int[] arr, int left, int right) {
        if (left < right) {
            // 分区操作，返回基准元素的正确位置
            int pivotIndex = partition(arr, left, right);
            // 递归对基准元素左侧和右侧的子数组排序
            quickSortHelper(arr, left, pivotIndex - 1);
            quickSortHelper(arr, pivotIndex + 1, right);
        }
    }

    // 分区操作，返回基准元素的最终位置
    private static int partition(int[] arr, int left, int right) {
        // 选择最右边的元素作为基准元素
        int pivot = arr[right];
        int i = left - 1; // i 指向比基准小的元素区域的最后一个元素
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                // 交换 arr[i + 1] 和 arr[j]
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准元素放到正确位置
        swap(arr, i + 1, right);
        return i + 1; // 返回基准元素的索引
    }

    // 交换数组中两个元素的位置
    private 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 = {3, 6, 8, 10, 1, 2, 1};
        System.out.println("Original array: ");
        printArray(arr);
        
        quickSort(arr);

        System.out.println("Sorted array: ");
        printArray(arr);
    }

    // 打印数组的辅助函数
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

代码解析：

• quickSort：是快速排序的入口方法，接收一个数组作为参数，检查数组是否为空或大小小于2，若满足条件则无需排序，直接返回。
• quickSortHelper：是一个递归函数，通过分区操作将数组划分为左右两部分，然后递归地对这两部分继续排序。
• partition：分区操作方法，它选择数组的最后一个元素作为基准元素，并通过两端的指针进行交换，将小于基准的元素放到左边，大于基准的元素放到右边。最终，基准元素被放到正确位置并返回其索引。
• swap：交换数组中两个元素的辅助函数。
• printArray：打印数组内容的辅助函数。

复杂度分析：

• 时间复杂度：
  • 最佳情况：O(n log n)，当每次分区都能将数组平衡地分成两部分。
  • 最坏情况：O(n^2)，当每次分区都选到数组的极端元素（如最小或最大），导致每次只能减少一个元素的排序，递归的深度为 n。
  • 平均情况：O(n log n)，是快速排序最常见的表现。
• 空间复杂度：
  • 最好和平均情况下：O(log n)，由于递归的深度受限于树的高度。
  • 最坏情况下：O(n)，当数组已经是排序好的，或者每次选到的基准元素极端时，递归的深度为 n。