算法 Algorithm • 下

前言

本读书笔记节选自krahets大佬编写的《Hello 算法》。勉励自己开始系统的算法学习。

10. 搜索

10.1 二分查找

「二分查找binary search」是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮减少一半搜索范围，直至找到目标元素或搜索区间为空为止。

给定一个长度为n的数组nums，元素按从小到大的顺序排列，数组不包含重复元素。请查找并返回元素target在该数组中的索引。若数组不包含该元素，则返回-1。

如下图所示，先初始化指针i = 0和j = n - 1，分别指向数组首元素和尾元素，代表搜索区间[0, n - 1]。请注意，中括号表示闭区间，其包含边界值本身。

接下来，循环执行以下两步。

计算中点索引m = [(i + j) / 2]，其中[]表示向下取整操作。
判断nums[m]和target的大小关系，分为以下三种情况。
- 当nums[m] < target时，说明target在区间[m + 1, j]中，执行i = m + 1。
- 当nums[m] > target时，说明target在区间[i, m - 1]中，执行j = m - 1。
- 当nums[m] = target时，说明找到target，因此返回索引m。

若数组不包含目标元素，搜索区间最终会缩小为空。此时返回-1。

值得注意的是，由于i和j都是int类型，因此i + j可能会超出int类型的取值范围。为了避免大数越界，通常采用公式m = [i + (j - i) / 2]来计算中点。

/* 二分查找（双闭区间） */
int binarySearch(int[] nums, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = nums.length - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

时间复杂度：在二分循环中，区间每轮缩小一半，循环次数为O(log2n)。
空间复杂度：指针i和j使用常数大小空间。

区间表示方法

除了上述的双闭区间外，常见的区间表示还有“左闭右开”区间，定义为[0, n)，即左边界包含自身，右边界不包含自身。在该表示下，区间[i, j]在i = j时为空。

基于该表示实现具有相同功能的二分查找算法。

/* 二分查找（左闭右开） */
int binarySearchLCRO(int[] nums, int target) {
    // 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
    int i = 0, j = nums.length;
    // 循环，当搜索区间为空时跳出（当 i = j 时为空）
    while (i < j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j) 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
            j = m;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

如下图所示，在两种区间表示下，二分查找算法的初始化、循环条件和缩小区间操作皆有所不同。

由于“双闭区间”表示中的左右边界都被定义为闭区间，因此指针i和j缩小区间操作也是对称的。这样更不容易出错，因此一般建议采用“双闭区间”的写法。

10.2 二分查找插入点

二分查找不仅可用于搜索目标元素，还具有许多变种问题，比如搜索目标元素的插入位置。

无重复元素的情况

给定一个长度为n的有序数组nums和一个元素target，数组不存在重复元素。现将target插入到数组nums中，并保持其有序性。若数组中已存在元素target，则插入到其左方。请返回插入后target在数组中的索引。

如果想要复用上节的二分查找代码，则需要回答以下两个问题。

当数组中包含target时，插入点的索引是否是该元素的索引？
- 题目要求将target插入到相等元素的左边，这意味着新插入的target替换了原来target的位置。当数组包含target时，插入点的索引就是该target的索引。
当数组中不存在target时，插入点是哪个元素的索引？
- 思考二分查找过程，当nums[m] < target时i移动，这意味着指针i在向大于等于target的元素靠近。同理，指针 j始终在向小于等于target的元素靠近。
- 因此二分结束时一定有，i指向首个大于target的元素，j指向首个小于target的元素。易得当数组不包含target时，插入索引为i。

/* 二分查找插入点（无重复元素） */
int binarySearchInsertionSimple(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            return m; // 找到 target ，返回插入点 m
        }
    }
    // 未找到 target ，返回插入点 i
    return i;
}

存在重复元素的情况

在上一题的基础上，规定数组可能包含重复元素，其余不变。

假设数组中存在多个target，则普通二分查找只能返回其中一个target的索引，而无法确定该元素的左边和右边还有多少target。

题目要求将目标元素插入到最左边，所以需要查找数组中最左一个target的索引。初步考虑通过下图所示的步骤实现。

执行二分查找，得到任意一个target的索引，记为k。
从索引k开始，向左进行线性遍历，当找到最左边的target时返回。

此方法虽然可用，但其包含线性查找，因此时间复杂度为O(n)。当数组中存在很多重复的target时，该方法效率很低。

考虑拓展二分查找代码。如下图所示，整体流程保持不变，每轮先计算中点索引m，再判断target和nums[m]大小关系，分为以下几种情况。

当nums[m] < target或nums[m] > target时，说明还没有找到target，因此采用普通二分查找的缩小区间操作，从而使指针i和j向target靠近。
当nums[m] == target时，说明小于target的元素在区间[i, m - 1]中，因此采用j = m - 1来缩小区间，从而使指针j向小于target的元素靠近。

循环完成后，i指向最左边的target，j指向首个小于target的元素，索引i就是插入点。

观察以下代码，判断分支nums[m] > target和nums[m] == target的操作相同，因此两者可以合并。但是因为逻辑性，故此保留。

/* 二分查找插入点（存在重复元素） */
int binarySearchInsertion(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
        }
    }
    // 返回插入点 i
    return i;
}

总的来看，二分查找无非就是给指针i和j分别设定搜索目标，目标可能是一个具体的元素（例如target），也可能是一个元素范围（例如小于target的元素）。

在不断的循环二分中，指针i和j都逐渐逼近预先设定的目标。最终，它们或是成功找到答案，或是越过边界后停止。

10.3 二分查找边界

查找左边界

给定一个长度为n的有序数组nums，数组可能包含重复元素。请返回数组中最左一个元素target的索引。若数组中不包含该元素，则返回-1。

回忆二分查找插入点的方法，搜索完成后i指向最左一个target，因此查找插入点本质上是在查找最左一个target的索引。

通过查找插入点的函数实现查找左边界。请注意，数组中可能不包含target，这种情况可能导致以下两种结果。

插入点的索引i越界。
元素nums[i]与target不相等。

当遇到以上两种情况时，直接返回-1即可。

/* 二分查找最左一个 target */
int binarySearchLeftEdge(int[] nums, int target) {
    // 等价于查找 target 的插入点 （10.2）
    int i = binary_search_insertion.binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i == nums.length || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

查找右边界

那么如何查找最右一个target呢？最直接的方式是修改代码，替换在nums[m] == target情况下的指针收缩操作。

int binarySearchRightmost(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    int result = -1; // 存储找到的最右边的目标值索引，初始为 -1 表示未找到
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            result = m; // 找到一个目标值的实例，保存索引
            i = m + 1; // 继续在右边区间 [m+1, j] 中查找
        }
    }
    // 返回找到的最右边的目标值索引，如果没有找到返回 -1
    return result;
}

下面介绍两种更加取巧的方法。

（1）复用查找左边界

实际上，可以利用查找最左元素的函数来查找最右元素，具体方法为，将查找最右一个target转化为查找最左一个target + 1。

如下图所示，查找完成后，指针i指向最左一个target + 1（如果存在），而j指向最右一个target，因此返回j即可。

请注意，返回的插入点是i，因此需要将其减1，从而获得j。

/* 二分查找最右一个 target */
int binarySearchRightEdge(int[] nums, int target) {
    // 转化为查找最左一个 target + 1
    int i = binary_search_insertion.binarySearchInsertion(nums, target + 1);
    // j 指向最右一个 target ，i 指向首个大于 target 的元素
    int j = i - 1;
    // 未找到 target ，返回 -1
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    // 找到 target ，返回索引 j
    return j;
}

（2）转化为查找元素

当数组不包含target时，最终i和j会分别指向首个大于、小于target的元素。

因此，如下图所示，可以构造一个数组中不存在的元素，用于查找左右边界。

查找最左一个target：可以转化为查找target - 0.5，并返回指针i。
查找最右一个target：可以转化为查找target + 0.5，并返回指针j。

// i 指向最左一个 target
int i = binary_search_insertion.binarySearchInsertion(nums, target - 0.5);
// j 指向最右一个 target
int j = binary_search_insertion.binarySearchInsertion(nums, target + 0.5);

值得注意以下两点。

给定数组不包含小数，这意味着无须关心如何处理相等的情况。
因为该方法引入了小数，所以需要将函数中的变量target改为浮点数类型。

10.4 哈希优化策略

在算法题中，常通过将线性查找替换为哈希查找来降低算法的时间复杂度。

给定一个整数数组nums和一个目标元素target，请在数组中搜索“和”为target的两个元素，并返回它们的数组索引。返回任意一个解即可。

线性查找：时间换空间

考虑直接遍历所有可能的组合。如下图所示，开启一个两层循环，在每轮中判断两个整数的和是否为target，若是则返回它们的索引。

/* 方法一：暴力枚举 */
int[] twoSumBruteForce(int[] nums, int target) {
    int size = nums.length;
    // 两层循环，时间复杂度 O(n^2)
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (nums[i] + nums[j] == target)
                return new int[] { i, j };
        }
    }
    return new int[0];
}

此方法的时间复杂度为O(n^2)，空间复杂度为O(1)，在大数据量下非常耗时。

哈希查找：空间换时间

借助一个哈希表，键值对分别为数组元素和元素索引。循环遍历数组，每轮执行下图所示的步骤。

判断数字target - nums[i]是否在哈希表中，若是则直接返回这两个元素的索引。
将键值对nums[i]和索引i添加进哈希表。

实现代码如下所示，仅需单层循环即可。

/* 方法二：辅助哈希表 */
int[] twoSumHashTable(int[] nums, int target) {
    int size = nums.length;
    // 辅助哈希表，空间复杂度 O(n)
    Map<Integer, Integer> dic = new HashMap<>();
    // 单层循环，时间复杂度 O(n)
    for (int i = 0; i < size; i++) {
        if (dic.containsKey(target - nums[i])) {
            return new int[] { dic.get(target - nums[i]), i };
        }
        dic.put(nums[i], i);
    }
    return new int[0];
}

此方法通过哈希查找将时间复杂度从O(n^2)降低至O(n)，大幅提升运行效率。

由于需要维护一个额外的哈希表，因此空间复杂度为O(n)。尽管如此，该方法的整体时空效率更为均衡，因此它是本题的最优解法。

10.5 重识搜索算法

搜索算法可根据实现思路分为以下两类。

通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等。

暴力搜索

暴力搜索通过遍历数据结构的每个元素来定位目标元素。

“线性搜索”适用于数组和链表等线性数据结构。它从数据结构的一端开始，逐个访问元素，直到找到目标元素或到达另一端仍没有找到目标元素为止。
“广度优先搜索”和“深度优先搜索”是图和树的两种遍历策略。广度优先搜索从初始节点开始逐层搜索，由近及远地访问各个节点。深度优先搜索是从初始节点开始，沿着一条路径走到头为止，再回溯并尝试其他路径，直到遍历完整个数据结构。

暴力搜索的优点是简单且通用性好，无须对数据做预处理和借助额外的数据结构。

然而，此类算法的时间复杂度为O(n)，其中n为元素数量，因此在数据量较大的情况下性能较差。

自适应搜索

自适应搜索利用数据的特有属性（例如有序性）来优化搜索过程，从而更高效地定位目标元素。

“二分查找”利用数据的有序性实现高效查找，仅适用于数组。
“哈希查找”利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
“树查找”在特定的树结构（例如二叉搜索树）中，基于比较节点值来快速排除节点，从而定位目标元素。

此类算法的优点是效率高，时间复杂度可达到O(logn)甚至O(1)。

然而，使用这些算法往往需要对数据进行预处理。例如，二分查找需要预先对数组进行排序，哈希查找和树查找都需要借助额外的数据结构，维护这些数据结构也需要额外的时间和空间开支。

搜索方法选取

给定大小为n的一组数据，可以使用线性搜索、二分查找、树查找、哈希查找等多种方法在该数据中搜索目标元素。

上述几种方法的操作效率与特性如下表所示。

	线性搜索	二分查找	树查找	哈希查找
查找元素	`O(n)`	`O(logn)`	`O(logn)`	`O(1)`
插入元素	`O(1)`	`O(n)`	`O(logn)`	`O(1)`
删除元素	`O(n)`	`O(n)`	`O(logn)`	`O(1)`
额外空间	`O(1)`	`O(1)`	`O(n)`	`O(n)`
数据预处理	`/`	排序`O(nlogn)`	建树`O(nlogn)`	建哈希表`O(n)`
数据是否有序	无序	有序	有序	无序

具体适用参照，这里就不再讨论。

11. 排序

11.1 排序算法

「排序算法sorting algorithm」用于对一组数据按照特定顺序进行排列。它有着广泛的应用，因为有序数据通常能够被更有效地查找、分析和处理。

排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符ASCII码顺序或自定义规则。

评价维度

排序算法通常根据多个维度来进行评价。下面是一些常见的评价指标。

运行效率：期望的排序算法时间复杂度尽量低，且总体操作数量较少（即时间复杂度中的常数项降低）。对于大数据量情况，运行效率显得尤为重要。
就地性：「原地排序」通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
稳定性：「稳定排序」在完成排序后，相等元素在数组中的相对顺序不发生改变。

# 输入数据是按照姓名排序好的
# (name, age)
  ('A', 19)
  ('B', 18)
  ('C', 21)
  ('D', 19)
  ('E', 23)

# 假设使用非稳定排序算法按年龄排序列表，
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变，
# 输入数据按姓名排序的性质丢失
  ('B', 18)
  ('D', 19)
  ('A', 19)
  ('C', 21)
  ('E', 23)

自适应性：「自适应排序」的时间复杂度会受输入数据的影响，即最佳、最差、平均时间复杂度并不完全相等。
是否基于比较：「基于比较的排序」依赖于比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为O(nlogn)。而「非比较排序」不使用比较运算符，时间复杂度可达O(n)，但其通用性相对较差。

运行快、原地、稳定、正向自适应、通用性好。显然，迄今为止尚未发现兼具以上所有特性的排序算法。因此，在选择排序算法时，需要根据具体的数据特点和问题需求来决定。

11.2 选择排序

「选择排序selection sort」的工作原理非常直接，开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组的长度为n，选择排序的算法流程如下图所示。

初始状态下，所有元素未排序，即未排序（索引）区间为[0, n - 1]。
选取区间[0, n - 1]中的最小元素，将其与索引0处元素交换。数组前1个元素已排序。
选取区间[1, n - 1]中的最小元素，将其与索引1处元素交换。数组前2个元素已排序。
以此类推。经过n - 1轮选择与交换后，数组前n - 1个元素已排序。
仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

在代码中，使用k来记录未排序区间内的最小元素。

/* 选择排序 */
void selectionSort(int[] nums) {
    int n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

算法特性

时间复杂度为O(n^2)、非自适应排序：外循环共n - 1轮，第一轮的未排序区间长度为n，最后一轮的未排序区间长度为2，即各轮外循环分别包含n、n - 1、...、3、2轮内循环，求和为((n - 1)(n - 2)) / 2。
空间复杂度O(1)、原地排序：指针i和j使用常数大小的额外空间。
非稳定排序：如下图所示，元素nums[i]有可能被交换至与其相等的元素的右边，导致两者相对顺序发生改变。

11.3 冒泡排序

「冒泡排序bubble sort」通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

如下图所示，冒泡过程可以利用元素交换操作来模拟。从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素 > 右元素”就交换它俩。遍历完成后，最大的元素会被移动到数组的最右端。

算法流程

设数组的长度为n，冒泡排序的步骤如下图所示。

首先，对n个元素执行“冒泡”，将数组的最大元素交换至正确位置。
接下来，对剩余n - 1个元素执行“冒泡”，将第二大元素交换至正确位置。
以此类推，经过n - 1轮“冒泡”后，前n - 1大的元素都被交换至正确位置。
仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。

/* 冒泡排序 */
void bubbleSort(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

效率优化

如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位flag来监测这种情况，一旦出现就立即返回。

经过优化，冒泡排序的最差和平均时间复杂度仍为O(n^2)。但当输入数组完全有序时，可达到最佳时间复杂度O(n)。

/* 冒泡排序（标志优化） */
void bubbleSortWithFlag(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false; // 初始化标志位
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true; // 记录交换元素
            }
        }
        if (!flag)
            break; // 此轮冒泡未交换任何元素，直接跳出
    }
}

算法特性

时间复杂度为O(n^2)、自适应排序：各轮“冒泡”遍历的数组长度依次为n - 1、n - 2、...、2、1，总和为(n - 1) n / 2。在引入flag优化后，最佳时间复杂度可达到O(n)。
空间复杂度为O(1)、原地排序：指针i和j使用常数大小的额外空间。
稳定排序：由于在“冒泡”中遇到相等元素不交换。

11.4 插入排序

「插入排序insertion sort」的工作原理与手动整理一副牌的过程非常相似。

具体来说，在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

下图展示了数组插入元素的操作流程。设基准元素为base，需要将从目标索引到base之间的所有元素向右移动一位，然后再将base赋值给目标索引。

算法流程

插入排序的整体流程如下图所示。

初始状态下，数组的第1个元素已完成排序。
选取数组的第2个元素作为base，将其插入到正确位置后，数组的前2个元素已排序。
选取第3个元素作为base，将其插入到正确位置后，数组的前3个元素已排序。
以此类推，在最后一轮中，选取最后一个元素作为base，将其插入到正确位置后，所有元素均已排序。

/* 插入排序 */
void insertionSort(int[] nums) {
    // 外循环：已排序元素数量为 1, 2, ..., n
    for (int i = 1; i < nums.length; i++) {
        int base = nums[i], j = i - 1;
        // 内循环：将 base 插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        nums[j + 1] = base;        // 将 base 赋值到正确位置
    }
}

算法特性

时间复杂度O(n^2)、自适应排序：最差情况下，每次插入操作分别需要循环n - 1、n - 2、...、2、1次，求和得到(n - 1) n / 2，因此时间复杂度为O(n^2)。在遇到有序数据时，插入操作会提前终止。当输入数组完全有序时，插入排序达到最佳时间复杂度O(n)。
空间复杂度O(1)、原地排序：指针i和j使用常数大小的额外空间。
稳定排序：在插入操作过程中，会将元素插入到相等元素的右侧，不会改变它们的顺序。

插入排序优势

插入排序的时间复杂度为O(n^2)，快速排序的时间复杂度为O(nlogn)。尽管插入排序的时间复杂度相比快速排序更高，但在数据量较小的情况下，插入排序通常更快。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为O(n^2)，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及3个单元操作。插入排序基于元素赋值实现，仅需1个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。
选择排序在任何情况下的时间复杂度都为O(n^2)。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。

11.5 快速排序

「快速排序quick sort」是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是“哨兵划分”，其目标是，选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如下图所示。

选取数组最左端元素作为基准数，初始化两个指针i和j分别指向数组的两端。
循环，在每轮中使用i，j分别寻找第一个比基准数大，小的元素，然后交换这两个元素。
循环执行上一个步骤，直到i和j相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分，左子数组、基准数、右子数组，且满足“左子数组任意元素<=基准数<=右子数组任意元素”。因此，接下来只需对这两个子数组进行排序。

/* 元素交换 */
void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵划分 */
int partition(int[] nums, int left, int right) {
    // 以 nums[left] 作为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left);  // 将基准数交换至两子数组的分界线
    return i;             // 返回基准数的索引
}

算法流程

快速排序的整体流程如下图所示。

首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
然后，对左子数组和右子数组分别递归执行“哨兵划分”。
持续递归，直至子数组长度为1时终止，从而完成整个数组的排序。

/* 快速排序 */
void quickSort(int[] nums, int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right)
        return;
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

算法特性

时间复杂度O(nlogn)、自适应排序：在平均情况下，哨兵划分的递归层数为logn，每层中的总循环数为 n，总体使用O(nlogn)时间。在最差情况下，每轮哨兵划分操作都将长度为n的数组划分为长度为0和n - 1的两个子数组，此时递归层数达到n层，每层中的循环数为n，总体使用O(n^2)时间。
空间复杂度O(n)、原地排序：在输入数组完全倒序的情况下，达到最差递归深度n，使用O(n)栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

附录

文件还未上传 Github