【算法基础】排序之快速排序 Sort_QuickSort

方法讲解

快速排序是一种高效的排序算法，被广泛应用于各种场景中。它的基本思想是分而治之，与归并排序类似，但在合并时不同。下面是快速排序的基本步骤和特点：

基本步骤

选择基准（Pivot Selection）:

快速排序首先选择一个元素作为基准。这个基准可以是数组中的任何一个元素，比如第一个元素、最后一个元素或者中间值。

分区（Partitioning）:

1.数组被重新排列，所有比基准小的元素都移动到基准的左边，所有比基准大的元素都移动到右边。这个过程结束时，基准元素处于其最终位置。
2.这是一个关键步骤，因为它保证了基准左边的元素都不大于基准，而基准右边的元素都不小于基准。

递归排序（Recursive Sorting）:

1.然后，地对基准左边和右边的子数组进行快速排序的过程。
2.递归持续进行，直到每个子数组只有一个元素或为空，这时数组就被排序好了。

详细过程

1.首先选择一个基准元素。
2.对数组进行分区操作，将所有小于基准的元素移动到左边，所有大于基准的元素移动到右边。
3.递归地在基准左侧和右侧的子数组上重复这个过程。
4.当子数组缩小到只有一个元素或没有元素时，整个数组就被排序好了。

特点和复杂度

时间复杂度:

最坏情况：O(n²)，当基准元素选择不佳时。
平均情况：O(n log n)，这使得快速排序在大多数情况下非常高效。

空间复杂度:

O(log n)，因为快速排序是递归的，需要堆栈空间。

不稳定性:

快速排序是一种不稳定的排序算法，相同的元素在排序后可能会改变其原始的顺序。

应用场景:

由于其高效性，快速排序在实际应用中非常普遍，特别是在内存中容易处理的数据集上。

Code_JAVA

// An highlighted block
public class Solution {
   
    /**
     * 快速排序
     * @param A an integer array
     */
    public void sortIntegers(int[] A) {
   
        quickSort(A, 0, A.length - 1