08、🌟快速排序算法｜一定要懂的快排优化

厨子大约 19 分钟数据结构算法基础面试题解析排序算法程序厨校招社招算法题精讲

快速排序

今天我们来说一下快速排序，这个排序算法也是面试的高频考点，原理很简单，我们一起来扒一下他吧。

我们先来说一下快速排序的基本思想。

1.先从数组中找一个基准数

2.让其他比它大的元素移动到数列一边，比他小的元素移动到数列另一边，从而把数组拆解成两个部分。

3.再对左右区间重复第二步，直到各区间只有一个数。

见下图

上图则为一次快排示意图，下面我们再利用递归，分别对左半边区间也就是 [3,1,2] 和右半区间 [7,6,5,8] 执行上诉过程，直至区间缩小为 1 也就是第三条，则此时所有的数据都有序。

简单来说就是我们利用基准数通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比基准数小，另一部分记录的关键字均比基准数大，然后分别对这两部分记录继续进行排序，进而达到有序。

我们现在应该了解了快速排序的思想，那么大家还记不记得我们之前说过的归并排序，他们两个用到的都是分治思想，那他们两个有什么不同呢？见下图

注：快速排序我们以序列的第一个元素作为基准数

虽然归并排序和快速排序都用到了分治思想，但是归并排序是自下而上的，先处理子问题，然后再合并，将小集合合成大集合，最后实现排序。而快速排序是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题

我们根据思想可知，排序算法的核心就是如何利用基准数将记录分区，这里我们主要介绍两种容易理解的方法，一种是挖坑填数，另一种是利用双指针思想进行元素交换。

下面我们先来介绍下挖坑填数的分区方法

基本思想是我们首先以序列的第一个元素为基准数，然后将该位置挖坑，下面判断 nums[high] 是否大于基准数，如果大于则左移 high 指针，直至找到一个小于基准数的元素，将其填入之前的坑中，则 high 位置会出现一个新的坑，此时移动 low 指针，找到大于基准数的元素，填入新的坑中。不断迭代直至完成分区。

大家直接看我们的视频模拟吧，一目了然。

动画模拟

注：为了便于理解所以采取了挖坑的形式展示

是不是很容易就理解啦，下面我们直接看代码吧。

代码

Java Code:

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

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

    }
    public void quickSort (int[] nums, int low, int high) {

        if (low < high) {
            int index = partition(nums,low,high);
            quickSort(nums,low,index-1);
            quickSort(nums,index+1,high);
        }

    }
    public int partition (int[] nums, int low, int high) {

            int pivot = nums[low];
            while (low < high) {
                //移动hight指针
                while (low < high && nums[high] >= pivot) {
                    high--;
                }
                //填坑
                if (low < high) nums[low] = nums[high];
                while (low < high && nums[low] <= pivot) {
                    low++;
                }
                //填坑
                if (low < high) nums[high] = nums[low];
            }
            //基准数放到合适的位置
            nums[low] = pivot;
            return low;
    }
}

C++

#include <vector>

class Solution {
public:
    // 对外接口：对整数向量进行快速排序
    std::vector<int> sortArray(std::vector<int>& nums) {
        quickSort(nums, 0, static_cast<int>(nums.size()) - 1);
        return nums;
    }

private:
    // 快速排序递归函数：排序nums[low..high]区间
    void quickSort(std::vector<int>& nums, int low, int high) {
        if (low < high) {
            // 获取基准元素的最终位置
            int pivotIndex = partition(nums, low, high);
            // 递归排序基准左侧子数组
            quickSort(nums, low, pivotIndex - 1);
            // 递归排序基准右侧子数组
            quickSort(nums, pivotIndex + 1, high);
        }
    }

    // 分区函数：选取基准元素，将数组分为"小于基准"和"大于基准"两部分
    int partition(std::vector<int>& nums, int low, int high) {
        // 选取区间第一个元素作为基准
        int pivot = nums[low];

        // 双指针交替移动，完成分区
        while (low < high) {
            // 从右向左找第一个小于基准的元素
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            // 将小于基准的元素填入左侧坑位
            if (low < high) {
                nums[low] = nums[high];
            }

            // 从左向右找第一个大于基准的元素
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            // 将大于基准的元素填入右侧坑位
            if (low < high) {
                nums[high] = nums[low];
            }
        }

        // 将基准元素放入最终位置
        nums[low] = pivot;
        // 返回基准元素的索引
        return low;
    }
};

下面我们来看一下交换思路，原理一致，实现也比较简单。

见下图。

其实这种方法，算是对上面方法的挖坑填坑步骤进行合并，low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，然后两个元素交换位置，最后再将基准数归位。两种方法都很容易理解和实现，即使是完全没有学习过快速排序的同学，理解了思想之后也能自己动手实现，下面我们继续用视频模拟下这种方法的执行过程吧。

两种方法都很容易实现，对新手非常友好，大家可以自己去 AC 一下啊。

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

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

    }

    public void quickSort (int[] nums, int low, int high) {

        if (low < high) {
            int index = partition(nums,low,high);
            quickSort(nums,low,index-1);
            quickSort(nums,index+1,high);
        }

    }

    public int partition (int[] nums, int low, int high) {

            int pivot = nums[low];
            int start = low;

            while (low < high) {
                while (low < high && nums[high] >= pivot) high--;
                while (low < high && nums[low] <= pivot) low++;
                if (low >= high) break;
                swap(nums, low, high);
            }
            //基准值归位
            swap(nums,start,low);
            return low;
    }
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
     }
}

C++

#include <vector>

class Solution {
public:
    // 对数组进行快速排序
    std::vector<int> sortArray(std::vector<int>& nums) {
        quickSort(nums, 0, static_cast<int>(nums.size()) - 1);
        return nums;
    }

private:
    // 快速排序递归函数
    void quickSort(std::vector<int>& nums, int low, int high) {
        if (low < high) {
            // 获取分区后基准元素的位置
            int pivotIndex = partition(nums, low, high);
            // 递归排序左半部分
            quickSort(nums, low, pivotIndex - 1);
            // 递归排序右半部分
            quickSort(nums, pivotIndex + 1, high);
        }
    }

    // 分区函数：采用双指针交换法
    int partition(std::vector<int>& nums, int low, int high) {
        // 选取区间第一个元素作为基准值
        int pivot = nums[low];
        // 记录基准值初始位置
        int start = low;

        // 双指针遍历，进行分区
        while (low < high) {
            // 从右向左找第一个小于基准值的元素
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            // 从左向右找第一个大于基准值的元素
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            // 若指针未交叉，则交换找到的两个元素
            if (low >= high) {
                break;
            }
            swap(nums, low, high);
        }

        // 将基准值交换到正确位置（分区点）
        swap(nums, start, low);
        // 返回基准值最终位置
        return low;
    }

    // 交换数组中两个位置的元素
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

时间复杂度分析

快排也是用递归来实现的。所以快速排序的时间性能取决于快速排序的递归树的深度。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那么此时的递归树是平衡的，性能也较好，递归树的深度也就和之前归并排序求解方法一致，然后我们每一次分区需要对数组扫描一遍，做 n 次比较，所以最优情况下，快排的时间复杂度是 O(nlogn)。

但是大多数情况下我们不能划分的很均匀，比如数组为正序或者逆序时，即 [1,2,3,4] 或 [4,3,2,1] 时，此时为最坏情况，那么此时我们则需要递归调用 n-1 次，此时的时间复杂度则退化到了 O(n^2)。

空间复杂度分析

快速排序主要时递归造成的栈空间的使用，最好情况时其空间复杂度为 O (logn),对应递归树的深度。最坏情况时则需要 n-1 次递归调用，此时空间复杂度为 O(n).

稳定性分析

快速排序是一种不稳定的排序算法，因为其关键字的比较和交换是跳跃进行的，见下图。

此时无论使用哪一种方法，第一次排序后，黄色的 1 都会跑到红色 1 的前面，所以快速排序是不稳定的排序算法。

好啦，快速排序我们掌握的差不多了，下面我们一起来看看如何对其优化吧。

快速排序的迭代写法

该方法实现也是比较简单的，借助了栈来实现，很容易实现。主要利用了先进后出的特性，这里需要注意的就是入栈的顺序，这里算是一个小细节，需要注意一下。

Java

class Solution {

     public int[] sortArray(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        stack.push(nums.length - 1);
        stack.push(0);
        while (!stack.isEmpty()) {
            int low = stack.pop();
            int high = stack.pop();

            if (low < high) {
                int index = partition(nums, low, high);
                stack.push(index - 1);
                stack.push(low);
                stack.push(high);
                stack.push(index + 1);
            }
        }
        return nums;
    }

    public int partition (int[] nums, int low, int high) {

            int pivot = nums[low];
            int start = low;
            while (low < high) {

                while (low < high && nums[high] >= pivot) high--;
                while (low < high && nums[low] <= pivot) low++;
                if (low >= high) break;
                swap(nums, low, high);
            }
            swap(nums,start,low);
            return low;

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

C++

#include <vector>
#include <stack>  // 用于栈操作

class Solution {
public:
    // 非递归方式实现快速排序
    std::vector<int> sortArray(std::vector<int>& nums) {
        // 创建栈用于模拟递归调用栈
        std::stack<int> stk;
        
        // 先推入高位索引，再推入低位索引（栈是后进先出）
        stk.push(static_cast<int>(nums.size()) - 1);
        stk.push(0);
        
        // 栈非空时继续处理
        while (!stk.empty()) {
            int low = stk.top();  // 先弹出低位索引
            stk.pop();
            int high = stk.top(); // 再弹出高位索引
            stk.pop();
            
            // 当区间有效时进行分区操作
            if (low < high) {
                int pivotIndex = partition(nums, low, high);
                
                // 推入左子区间 [low, pivotIndex-1]
                stk.push(pivotIndex - 1);
                stk.push(low);
                
                // 推入右子区间 [pivotIndex+1, high]
                stk.push(high);
                stk.push(pivotIndex + 1);
            }
        }
        
        return nums;
    }

private:
    // 分区函数：采用双指针交换法
    int partition(std::vector<int>& nums, int low, int high) {
        int pivot = nums[low];  // 选取区间第一个元素作为基准值
        int start = low;        // 记录基准值初始位置
        
        // 双指针遍历交换
        while (low < high) {
            // 从右向左找第一个小于基准值的元素
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            // 从左向右找第一个大于基准值的元素
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            // 若指针未交叉则交换元素
            if (low >= high) {
                break;
            }
            swap(nums, low, high);
        }
        
        // 将基准值放到正确位置
        swap(nums, start, low);
        return low;  // 返回基准值最终位置
    }
    
    // 交换数组中两个元素
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

快速排序优化

三数取中法

我们在上面的例子中选取的都是 nums[low] 做为我们的基准值，那么当我们遇到特殊情况时呢？见下图

我们按上面的方法，选取第一个元素做为基准元素，那么我们执行一轮排序后，发现仅仅是交换了 2 和 7 的位置，这是因为 7 为序列的最大值。所以我们的 pivot 的选取尤为重要，选取时应尽量避免选取序列的最大或最小值做为基准值。则我们可以利用三数取中法来选取基准值。

也就是选取三个元素中的中间值放到 nums[low] 的位置，做为基准值。这样就避免了使用最大值或最小值做为基准值。

所以我们可以加上这几行代码实现三数取中法。

    // 计算中间索引（避免直接相加可能的溢出）
    int mid = low + ((high - low) >> 1);

    // 三数取中：确保nums[low]为三个位置中的中间值
    if (nums[low] > nums[high]) {
        swap(nums, low, high);
    }
    if (nums[mid] > nums[high]) {
        swap(nums, mid, high);
    }
    if (nums[mid] > nums[low]) {
        swap(nums, mid, low);
    }

其含义就是让我们将中间元素放到 nums[low] 位置做为基准值，最大值放到 nums[high],最小值放到 nums[mid],即 [4,2,3] 经过上面代码处理后，则变成了 [3,2,4].此时我们选取 3 做为基准值，这样也就避免掉了选取最大或最小值做为基准值的情况。

#include <vector>

class Solution {
public:
    // 对数组进行快速排序（带三数取中优化）
    std::vector<int> sortArray(std::vector<int>& nums) {
        quickSort(nums, 0, static_cast<int>(nums.size()) - 1);
        return nums;
    }

private:
    // 快速排序递归函数
    void quickSort(std::vector<int>& nums, int low, int high) {
        if (low < high) {
            // 获取分区后基准元素的位置
            int pivotIndex = partition(nums, low, high);
            // 递归排序左半部分
            quickSort(nums, low, pivotIndex - 1);
            // 递归排序右半部分
            quickSort(nums, pivotIndex + 1, high);
        }
    }

    // 分区函数（带三数取中优化）
    int partition(std::vector<int>& nums, int low, int high) {
        // 三数取中：从首、中、尾三个位置选择中间值作为基准
        int mid = low + ((high - low) >> 1);  // 计算中间索引（避免溢出）
        
        // 三次比较交换，确保nums[low]为三个位置中的中间值
        if (nums[low] > nums[high]) {
            swap(nums, low, high);
        }
        if (nums[mid] > nums[high]) {
            swap(nums, mid, high);
        }
        if (nums[mid] > nums[low]) {
            swap(nums, mid, low);
        }

        // 以经过优化的nums[low]作为基准值
        int pivot = nums[low];
        int start = low;  // 记录基准值初始位置

        // 双指针遍历交换
        while (low < high) {
            // 从右向左找第一个小于基准值的元素
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            // 从左向右找第一个大于基准值的元素
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            // 若指针未交叉则交换元素
            if (low >= high) {
                break;
            }
            swap(nums, low, high);
        }

        // 将基准值放到正确位置
        swap(nums, start, low);
        return low;  // 返回基准值最终位置
    }

    // 交换数组中两个位置的元素
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

我们之前说过，插入排序在元素个数较少时效率是最高的，所以当元素数量较少时，快速排序反而不如插入排序好用，所以我们可以设定一个阈值，当元素个数大于阈值时使用快速排序，小于等于该阈值时则使用插入排序。我们设定阈值为 7 。

三数取中+插入排序

#include <vector>

class Solution {
private:
    // 定义使用插入排序的最大子数组长度
    static const int INSERTION_SORT_MAX_LENGTH = 7;

public:
    // 主排序接口
    std::vector<int> sortArray(std::vector<int>& nums) {
        quickSort(nums, 0, static_cast<int>(nums.size()) - 1);
        return nums;
    }

private:
    // 快速排序主函数（含小规模数组插入排序优化）
    void quickSort(std::vector<int>& nums, int low, int high) {
        // 当子数组长度较小时，使用插入排序效率更高
        if (high - low <= INSERTION_SORT_MAX_LENGTH) {
            insertSort(nums, low, high);
            return;
        }
        
        // 对长数组使用快速排序
        int pivotIndex = partition(nums, low, high);
        quickSort(nums, low, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, high);
    }

    // 分区函数（带三数取中优化）
    int partition(std::vector<int>& nums, int low, int high) {
        // 三数取中：从首、中、尾选择中间值作为基准，优化基准选择
        int mid = low + ((high - low) >> 1);  // 安全计算中间索引（避免溢出）
        
        // 三次比较交换，确保nums[low]为三个位置的中间值
        if (nums[low] > nums[high]) {
            swap(nums, low, high);
        }
        if (nums[mid] > nums[high]) {
            swap(nums, mid, high);
        }
        if (nums[mid] > nums[low]) {
            swap(nums, mid, low);
        }

        // 以优化后的nums[low]作为基准值
        int pivot = nums[low];
        int start = low;  // 记录基准值初始位置

        // 双指针交换法分区
        while (low < high) {
            // 从右向左找第一个小于基准值的元素
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            // 从左向右找第一个大于基准值的元素
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            // 指针未交叉则交换元素
            if (low >= high) {
                break;
            }
            swap(nums, low, high);
        }

        // 基准值归位
        swap(nums, start, low);
        return low;  // 返回基准值最终位置
    }

    // 插入排序（用于小规模子数组）
    void insertSort(std::vector<int>& nums, int low, int high) {
        // 从第二个元素开始，逐个插入到前面的有序部分
        for (int i = low + 1; i <= high; ++i) {
            int temp = nums[i];  // 保存当前待插入元素
            int j;
            
            // 找到插入位置
            for (j = i - 1; j >= 0; --j) {
                if (temp < nums[j]) {
                    nums[j + 1] = nums[j];  // 元素后移
                    continue;
                }
                break;  // 找到插入位置，退出循环
            }
            
            // 将待插入元素放到正确位置
            nums[j + 1] = temp;
        }
    }

    // 交换数组中两个位置的元素
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

我们继续看下面这种情况

我们对其执行一次排序后，则会变成上面这种情况，然后我们继续对蓝色基准值的左区间和右区间执行相同操作。也就是 [2,3,6,3,1,6] 和 [8,6] 。我们注意观察一次排序的结果数组中是含有很多重复元素的。

那么我们为什么不能将相同元素放到一起呢？这样就能大大减小递归调用时的区间大小，见下图。

这样就减小了我们的区间大小，将数组切分成了三部分，小于基准数的左区间，大于基准数的右区间，等于基准数的中间区间。

下面我们来看一下如何达到上面的情况，我们先来进行视频模拟，模拟之后应该就能明白啦。

我们来剖析一下视频，其实原理很简单，我们利用探路指针也就是 i，遇到比 pivot 大的元素，则和 right 指针进行交换，此时 right 指向的元素肯定比 pivot 大，则 right--，但是，此时我们的 nums[i] 指向的元素并不知道情况，所以我们的 i 指针不动，如果此时 nums[i] < pivot 则与 left 指针交换，注意此时我们的 left 指向的值肯定是等于 povit 的，所以交换后我们要 left++,i++, nums[i] == pivot 时，仅需要 i++ 即可，继续判断下一个元素。我们也可以借助这个思想来解决经典的荷兰国旗问题。

好啦，我们下面直接看代码吧。

三数取中+三向切分+插入排序

C++

#include <vector>

class Solution {
private:
    // 定义使用插入排序的最大子数组长度
    static const int INSERTION_SORT_MAX_LENGTH = 7;

public:
    // 主排序接口
    std::vector<int> sortArray(std::vector<int>& nums) {
        if (nums.empty()) return nums; // 处理空数组情况
        quickSort(nums, 0, static_cast<int>(nums.size()) - 1);
        return nums;
    }

private:
    // 快速排序主函数（含多种优化）
    void quickSort(std::vector<int>& nums, int low, int high) {
        // 小规模数组使用插入排序
        if (high - low <= INSERTION_SORT_MAX_LENGTH) {
            insertSort(nums, low, high);
            return;
        }

        // 三数取中：优化基准值选择
        int mid = low + ((high - low) >> 1);
        if (nums[low] > nums[high]) {
            swap(nums, low, high);
        }
        if (nums[mid] > nums[high]) {
            swap(nums, mid, high);
        }
        if (nums[mid] > nums[low]) {
            swap(nums, mid, low);
        }

        // 三向切分：将数组分为 <pivot、=pivot、>pivot 三部分
        int left = low;               // 小于基准区的右边界
        int i = low + 1;              // 当前遍历指针
        int right = high;             // 大于基准区的左边界
        int pivot = nums[low];        // 基准值（经三数取中优化）

        while (i <= right) {
            if (pivot < nums[i]) {
                // 当前元素大于基准值，交换到右侧大于区
                swap(nums, i, right);
                right--;
            } else if (pivot == nums[i]) {
                // 当前元素等于基准值，直接跳过
                i++;
            } else {
                // 当前元素小于基准值，交换到左侧小于区
                swap(nums, left, i);
                left++;
                i++;
            }
        }

        // 递归排序小于区和大于区（等于区已就位，无需排序）
        quickSort(nums, low, left - 1);
        quickSort(nums, right + 1, high);
    }

    // 插入排序（用于小规模子数组）
    void insertSort(std::vector<int>& nums, int low, int high) {
        for (int i = low + 1; i <= high; ++i) {
            int temp = nums[i];  // 保存当前待插入元素
            int j;
            // 找到插入位置并移动元素
            for (j = i - 1; j >= low; --j) {  // 修正边界：j >= low而非j >= 0
                if (temp < nums[j]) {
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = temp;  // 插入元素
        }
    }

    // 交换数组中两个位置的元素
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

好啦，一些常用的优化方法都整理出来啦，还有一些其他的优化算法九数取中，优化递归操作等就不在这里进行描述啦，感兴趣的可以自己看一下。好啦，这期的文章就到这里啦，我们下期见，拜了个拜。

08、🌟快速排序算法｜一定要懂的快排优化

# 快速排序

# 动画模拟

# 代码

# 时间复杂度分析

# 空间复杂度分析

# 稳定性分析

# 快速排序的迭代写法

# 快速排序优化

# 三数取中法

# 三数取中+插入排序

# 三数取中+三向切分+插入排序