快速排序逻辑

快速排序采用分治法的思想，每次找到一个数的正确位置，并将左右两侧调整为小于大于该数的两部分，递归两侧找到每一个数字的正确位置

在交换过程中，相同大小的元素可能会改变它们的相对顺序，所以快速排序不稳定

复杂度分析

平均时间复杂度：O(nlogn)

空间复杂度：O(logn)

最差情况的时间复杂度，待排序数组已经是有序的或者逆序的，此时每次划分只能得到一个很小或很大的子数组，其时间复杂度为O(n^2)；

递归调用栈的最大深度为n，因此最坏情况下的空间复杂度为O(n)

代码实现

class Main {
    public static void quickSort(int[] arr, int left, int right) {
        // 保证数组存在值
        if(left < right) {
            int temp = arr[left];
            int i = left + 1, j = right;
            // 左右指针，找到左边第一个大于temp的和右边第一个小于temp的，交换
            while(i <= j) {
                while(i <= j && arr[i] < temp) i++;
                while(i <= j && arr[j] > temp) j--;
                if(i <= j) {
                    swap(arr, i, j);
                    i++;
                    j--;
                }
            }
            // 将第一个值放到合适的位置
            swap(arr, left, j);
            // 左右区间分别快排
            quickSort(arr, left, j-1);
            quickSort(arr, i, right);
        }
        return;
    }

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

使用场景

快速排序适用于各种规模的待排序数组，它的性能好于其他排序算法，尤其适用于大规模数据的排序。