02-快速排序算法

数据结构可视化：快速排序算法-Quick Sort

实现一个快速排序算法，并分析其时间复杂度和空间复杂度。

public class QuickSort {
    public void sort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            if (nums[i] < pivot && nums[j] > pivot) {
                swap(nums, i, j);
                i++;
                j--;
            } else if (nums[i] >= pivot) {
                i++;
            } else if (nums[j] <= pivot) {
                j--;
            }
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

快速排序算法的时间复杂度为O(nlogn)，其中n为数组的长度。空间复杂度为O(logn)，因为快速排序算法使用递归实现，每次递归需要使用O(logn)的栈空间。在最坏情况下，即数组已经有序的情况下，快速排序算法的时间复杂度为O(n^2)，但这种情况出现的概率较低。快速排序算法是一种常用的排序算法，因为其平均时间复杂度较低，适用于大规模数据的排序。

验证：

public static void main(String[] args) {
    int[] nums = {6, 3, 5, 1, 2, 8, 4, 9};
    QuickSort quickSort = new QuickSort();
    quickSort.sort(nums);
    //nums = [9, 8, 6, 5, 4, 3, 2, 1]
    System.out.println("nums = " + Arrays.toString(nums));
}