快速排序 - 基础及详解 - 个人开发测试

快速排序是一个高效的排序算法，它被应用在大多数的排序任务中，快速排序还被誉为「二十世纪最具影响力的十大算法」之一。

基本思想：

快速排序（Quicksort）的基本思想是通过分而治之的中心思想，将一个数组分成较小的子数组来进行排序。首先，从数组中选择一个元素作为切分元素（pivot），这个切分元素可以是第一个元素或最后一个元素（存在特殊情况）、中间的元素或随机选择的一个元素。接下来，将数组重新排序，使得所有比切分元素小的元素都放在切分元素的左边，所有比切分元素大的元素都放在切分元素的右边。经过这个步骤后，切分元素的位置就是最终排序的位置。然后，对切分元素左边的子数组和右边的子数组递归地应用上述步骤，直到子数组的大小为0或1，此时数组已经是有序的。

排序步骤：

选择切分元素pivot：从数组中选择一个元素作为切分元素。选择切分元素的方法有多种，可以选择第一个元素、最后一个元素、中间的元素或随机选择一个元素。选好pivot后，将其与left或right调换位置。
分区Partition：1，设置两个指针，分别位于数组nums的两侧[left, right]。移动左指针，直到找到一个大于切分元素的元素，移动右指针，直到找到一个小于切分元素的元素，交换这两个元素的位置。重复上述移动左右指针步骤，直到左指针和右指针相遇。
放置切分元素swap pivot ：当左指针和右指针相遇时，切分元素的位置已经确定，将切分元素放到正确的位置上。
递归排序Sorting ：对切分元素左边的子数组和右边的子数组递归地应用上述步骤，选择新的切分元素，进行分区和排序，直至每个子数组的大小为0或1。

总结，快速排序通过选择切分元素、分区、递归排序和合并结果来实现数组的排序。平均时间复杂度为𝑂(𝑛log⁡𝑛)，最坏情况下为𝑂(𝑛^2) - 数组有序且pivot选择为left或right，但通过合理选择切分元素，通常能够达到很高的效率。

代码实现：

主框架：

和归并排序一样，快速排序也是通过递归实现的。我们首先写出快速排序算法的代码框架：

public class Solution {

    public int[] sortArray( int[] nums ) {

        int len = nums.length;  /// 获取数nums长度
        quickSort ( nums, 0, len );
        return nums;

    }

    private void quickSort ( int[] nums, int left, int right ) {

        if ( left >= right ) return;  

        int temp = partition ( nums, left,  right );
        quickSort ( nums, left, temp - 1 );  /// 左边严格小于pivot的区间
        quickSort ( nums, temp + 1, right );  /// 右边严格大于pivot的区间
        
    }

}

第一种方法：经典快速排序

我们实现partition最为常用的方法，为了让代码的语义更容易理解，我们使用lt表示less than，表明严格小于的意思。

public class Solution {

    private int partition ( int[] nums, int left, int right ) {

        int randomIndex = left + (int)( Math.random() * ( right - left + 1) );
        swap(nums, randomIndex, left);
        /// 随机选择pivot的位置，避免最坏时间复杂度𝑂(𝑁^2)
        int pivot = nums[left];
        int lt = left;  /// less than

        for ( int i = left + 1; i <= right ; i++ ) {
            /// 确定循环不变量
            /// [left + 1, lt] < pivot
            /// [lt + 1, i) >= pivot
            if ( nums[i] < pivot ) {
                i++;
                swap( nums, lt, ge );
                /// 交换符合条件的lt与ge的位置。
            }

        }
        /// 最后一步要交换切分元素到正确的位置。
        swap ( nums, left, lt );
        return lt;

    }

    private void swap ( int[] nums, int index1, int index2 ) {

        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;

    }

}

第二种方法：指针对撞

我们叫做指针对撞的快速排序，以下是两种可行的 partition 过程循环不变量的设置，不管是哪一种，和切分元素相等的元素都全部被划分到了一侧，都会使得递归树失衡，即递归树的深度增加。

为了防止以上情况，我们如果想让切分元素相等的元素分散到数组的两侧，可以设置两个变量，往中间靠拢，这连个变量为le和ge，分别表示less than和greater than。

在循环的过程中，总有 [left + 1, le) <= pivot 并且 (ge, right] >= pivot 成立；

public class Solution {

     public int partition(int[] nums, int left, int right) {
        int randomIndex = left + (int)( Math.random() * ( right - left + 1 ) );
        swap(nums, randomIndex, left); /// 随机选择一个元素作为切分元素，并交换切分元素与left的位置

        /// 循环不变量，le = less equals，ge = greater equals
        /// all in [left + 1, le) <= pivot
        /// all in (ge, right] >= pivot
        /// le > ge 的时候终止
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;

        while (true) {
            /// 注意：这里一定是 nums[le] < pivot，等于 pivot 的元素是被交换过来得到的
            while (le <= ge && nums[le] < pivot) {
                le++;
            }
            /// 此时 le 来到第 1 个大于等于 pivot 的位置
            while (le <= ge && nums[ge] > pivot) {
                ge--;
            }
            /// 此时 ge 来到第 1 个小于等于 pivot 的位置
            if (le > ge) {
                break;
            }

            swap(nums, le, ge);
            le++;
            ge--;

        }
        swap(nums, left, ge);
        return ge;

    }

    private void swap(int[] nums, int index1, int index2) {

        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;

    }

}

第三种方法：三向切分

「三向切分的快速排序」其实是之前的两个快速排序版本的结合。在变量 i 遍历的过程中，设置两个变量 lt 和 gt，保持下面的循环不变量的性质。为的是解决快速排序在处理大量重复元素时效率低下的问题。传统的快速排序在处理重复元素时，每次划分只能将一个切分元素放在正确位置，而其他等于切分元素的元素依然需要在后续递归中处理，这会导致效率降低。

三向切分的快速排序通过将数组划分为三部分：小于切分元素的部分、等于切分元素的部分和大于切分元素的部分，从而一次性处理所有切分元素的重复值。这样可以显著减少递归的深度和排序的工作量，提高算法的效率。

具体来说，三向切分的快速排序的步骤如下：

选择切分元素Pivot ：从数组中选择一个元素作为切分元素。选择切分元素的方法有多种，可以选择第一个元素、最后一个元素、中间的元素或随机选择一个元素。选好pivot后，将其与left或right调换位置。
三向分区3-way Partition ：使用三个指针，分别是左指针lt、右指针gt和当前指针i。初始时，lt指向数组的起始位置，gt指向数组的结束位置，i从数组的起始位置开始。当i <= gt时，比较array[i]和切分元素：1）如果 array[i] < 切分元素，交换 array[i] 和 array[lt]，然后 lt 和 i 向右移动。2）如果 array[i] > 切分元素，交换 array[i] 和 array[gt]，gt 向左移动。3）如果 array[i] == 切分元素，i 向右移动。
递归排序Sorting ：对小于切分元素的子数组[left + 1, lt] < pivot和大于切分元素的子数组[gt, right] >= pivot递归地应用上述步骤。而等于基准部分的子数组[lt + 1, i) = pivot已经排序，无需进一步处理。

通过这种方式，三向切分的快速排序在一次分区中有效地处理了所有等于基准的元素，从而减少了递归深度，提高了排序的效率，特别是对于包含大量重复元素的数组。

class Solution {

    public int[] sortArray(int[] nums) {

        int len = nums.length;
        quickSort(nums, 0, len - 1);
        return nums;

    }

    private void quickSort(int[] nums, int left, int right) {

        if (left >= right) return;

        int indexrandom = left + (int) (Math.random() * (right - left + 1));
        swap(nums, indexrandom, left);

        int pivot = nums[left];
        int lt = left;  /// lt = less than
        int gt = right + 1;  /// gt = greater than

        int i = left + 1;
        while (i < gt) {

            if (nums[i] < pivot) {
                lt++;                 /// 严格小于 pivot，先把 lt 向右移动一格
                swap(nums, i, lt);    /// 然后交换 lt 与 i
                i++;                  /// 然后 i 再向右移动一格
            } else if (nums[i] == pivot) {
                i++;                  /// 等于 pivot，i 向右移动一格即可
            } else {
                gt--;                 /// 严格大于 pivot
                swap(nums, i, gt);    /// 先把 gt 向左移动一格，然后交换 gt 与 i，此时 i 无须移动
                                      /// 因为交换过来的是一个我们还没有看到的元素
                                      /// 我们可以在下一轮循环中再根据它的大小执行相应的步骤
            }

        }

        swap(nums, left, lt);  // 大大减少了分治的区间，区间 [lt, gt - 1] 不必递归求解
        quickSort(nums, left, lt - 1);
        quickSort(nums, gt, right);

    }

    private void swap(int[] nums, int index1, int index2) {

        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;

    }

}

三向切分的快速排序能加速排序的原因是：如果执行 partition 的子区间当中，有很多元素都和基准元素相等，那么这些元素都能够在这一轮 partition 中被排定。因为和 pivot 相等的元素都被挤到了中间，它们前面的元素都比 pivot 小，它们后面的元素都比 pivot 大，因此它们就位于排序以后最终应该在的位置。