快速排序-part2

快速排序是一种基于比较的排序算法，利用分治法来将一个序列分割成两个子序列进行排序，并利用递归的方式进行排序。快速排序是一种高效的排序算法，其时间复杂度为O(nlogn)，空间复杂度为O(logn)。

【算法步骤】

1.选择基准值：从数列中选择一个元素作为基准值（pivot）。

2.分割：将序列中大于基准值的元素放在基准值的右边，小于基准值的元素放在基准值的左边。此时，基准值的位置已经确定了。

3.递归：对左右两边的子序列分别重复步骤1、步骤2，直到每个子序列只有一个元素时终止递归。

【时间复杂度】

最好情况下，每次选出的基准值都刚好平分整个序列，此时排序效率最高，时间复杂度为O(nlogn)。
最坏情况下，每次选出的基准值总是序列中的最小或最大值，导致递归树退化成只有一条支线，此时时间复杂度为O(n²)。
平均情况下，快速排序的时间复杂度为O(nlogn)。

【空间复杂度】

快速排序的空间复杂度为O(logn)，主要是由于递归调用的栈所占用的空间。

【适用场景】

快速排序适用于数据量较大、数值分布比较均匀的情况下。由于快速排序对于数据分布的依赖性比较强，如果数据分布不均匀，可能会影响排序效率，甚至导致时间复杂度退化到O(n²)。因此，如果要在数据分布不均匀的情况下进行排序，建议采用其他排序算法。

【实现代码】

以下是实现快速排序的Java代码：

Copy Codepublic static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

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

其中，quickSort方法是快速排序的入口，它会递归调用自己对左右子序列进行排序。partition方法是分割方法，用于将序列分割成两个子序列，并返回基准值的位置。swap方法是交换数组中两个元素的值。

测试代码如下：

Copy Codeint[] arr = {5, 3, 1, 6, 8, 4, 2, 7};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));

输出结果为：[1, 2, 3, 4, 5, 6, 7, 8]