企业官网建设流程全解析

目录

一、快速排序的基本想法

二、三路划分中 4 个区域的含义

三、为什么三个分支中指针移动方式不同

情况一：nums[i] < key

情况二：nums[i] == key

情况三：nums[i] > key

四、Java 中的交换方法

五、题目一：颜色分类

六、题目二：排序数组——三路快速排序

七、题目三：数组中的第 K 个最大元素

八、题目四：最小的 k 个数

九、4 道题共同形成的快速排序规律

规律二：从右边交换元素时，当前指针不能移动

规律三：完整排序要递归两边

规律四：只找答案时只递归一边

规律五：快速选择的关键是重新计算 k

十、常用 Java 写法

获取数组长度

生成随机下标

交换数组中的两个元素

前置自增与后置自增

十一、这一阶段的总结

快速排序最容易让初学者困惑的地方，是代码中同时出现多个指针，而且有些指针移动、有些指针不移动。真正理解它的关键，不是先背完整代码，而是先弄清楚每个区间分别保存什么。

本文涉及的题目链接：

• 75：颜色分类
• 912：排序数组
• 215：数组中的第 K 个最大元素
• 剑指 Offer 40：最小的 k 个数

一、快速排序的基本想法

快速排序的基本过程是：

1. 选出一个基准元素，代码中叫key；
2. 把数组中比key小、等于key、比key大的元素分开；
3. 如果要完整排序，就继续处理还没有排好序的区域；
4. 如果只需要找某一个位置的答案，就只处理可能包含答案的区域。

这里使用的是三路划分：

小于 key | 等于 key | 大于 key

如果数组中有很多重复数字，等于key的中间部分已经不需要再次排序，因此三路划分比只分成左右两部分更适合重复元素较多的情况。

二、三路划分中 4 个区域的含义

假设当前处理的区间是[l, r]，准备使用key进行划分。代码定义：

int left = l - 1; int right = r + 1; int i = l;

在循环过程中，始终保持下面的关系：

[l, left] 小于 key [left + 1, i - 1] 等于 key [i, right - 1] 还没有判断 [right, r] 大于 key

其中：

• left表示“小于key”区域的最后位置；
• i表示当前正在判断的位置；
• right表示“大于key”区域的起始位置；
• [i, right - 1]是还没有判断的部分。

循环条件是：

while(i < right)

当i == right时，未处理区域为空，整个区间划分完成。

三、为什么三个分支中指针移动方式不同

情况一：nums[i] < key

当前元素应该放到左边。把它与left + 1位置交换，并让left和i都向右移动：

swap(nums, ++left, i++);

交换之后，当前位置已经确认处理完毕，所以i可以加一。

情况二：nums[i] == key

当前元素已经属于中间区域，不需要交换，只让i向右移动：

i++;

情况三：nums[i] > key

当前元素应该放到右边。把它与right - 1位置交换，并让right向左移动：

swap(nums, --right, i);

这里i不能移动，因为从右边交换过来的新元素原来还没有判断，必须在下一轮继续检查。

因此要牢牢记住：

小于 key：left 和 i 都移动 等于 key：只有 i 移动 大于 key：只有 right 移动，i 不动

四、Java 中的交换方法

Java 的基本类型参数传递的是值，不能通过下面这种方法交换数组中的两个位置：

void swap(int a, int b) { int t = a; a = b; b = t; }

因为这个方法只能交换局部变量的副本。对于数组，需要传入数组和两个下标：

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

这个方法在下面几道题中都会使用。

五、题目一：颜色分类

1. 题目描述

给定一个只包含0、1、2的数组，要求原地排序，使相同的数字相邻，并按0、1、2的顺序排列。

例如：

输入：[2, 0, 2, 1, 1, 0] 输出：[0, 0, 1, 1, 2, 2]

不能使用库提供的排序方法。

题目链接：75：颜色分类

2. 算法思路

这道题可以直接看成三路划分：

• 0就是“小于基准的元素”，放在左边；
• 1留在中间；
• 2就是“大于基准的元素”，放在右边。

不需要真正选择一个key，直接根据当前数字是0、1还是2进行处理。

3. Java 代码

class Solution { public void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } public void sortColors(int[] nums) { int left = -1; int right = nums.length; int i = 0; while(i < right) { if(nums[i] == 0) { swap(nums, ++left, i++); } else if(nums[i] == 1) { i++; } else { swap(nums, --right, i); } } } }

4. 为什么left从-1开始，right从nums.length开始

一开始数组中还没有确认任何0或2：

0 区间为空：[0, -1] 2 区间为空：[nums.length, nums.length - 1]

所以：

left = -1; right = nums.length;

这是一种用“区间为空”的方式初始化指针的写法。

5. 复杂度

每个元素都被处理，时间复杂度是O(n)；只在原数组中交换，空间复杂度是O(1)。

六、题目二：排序数组——三路快速排序

1. 题目描述

给定一个整数数组，要求将数组按升序排列。

例如：

输入：[5, 2, 3, 1] 输出：[1, 2, 3, 5]

题目链接：912：排序数组

2. 算法思路

对区间[l, r]：

1. 如果区间只有一个元素或为空，就不需要处理；
2. 随机选择一个下标，得到基准元素key；
3. 使用三路划分，把区间分成小于、等于、大于key的三部分；
4. 对左边和右边继续递归排序；
5. 中间等于key的部分不用处理。

随机选择基准是为了尽量避免每次都选到很差的基准，从而降低出现极端情况的概率。

3. Java 代码

import java.util.Random; class Solution { public int[] sortArray(int[] nums) { qsort(nums, 0, nums.length - 1); return nums; } public void qsort(int[] nums, int l, int r) { if(l >= r) return; // 在 [l, r] 中随机选择一个元素作为 key int key = nums[new Random().nextInt(r - l + 1) + l]; int left = l - 1; int right = r + 1; int i = l; while(i < right) { if(nums[i] < key) { swap(nums, ++left, i++); } else if(nums[i] == key) { i++; } else { swap(nums, --right, i); } } // [l, left] 小于 key，[right, r] 大于 key qsort(nums, l, left); qsort(nums, right, r); } public void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }

4.new Random().nextInt()是什么

Random是 Java 中用于生成随机数的类。

new Random().nextInt(x)

会生成0到x - 1之间的随机整数。

因此：

new Random().nextInt(r - l + 1) + l

得到的是[l, r]范围中的随机下标。

5. 递归出口为什么是l >= r

当l > r时，区间为空；当l == r时，区间只有一个元素。这两种情况都已经天然有序，不需要继续递归。

6. 复杂度

平均时间复杂度是O(n log n)。如果基准选择非常不理想，最坏可能达到O(n^2)，随机选择基准可以降低出现这种情况的概率。递归调用会占用栈空间，平均空间复杂度通常是O(log n)。

七、题目三：数组中的第 K 个最大元素

1. 题目描述

给定一个整数数组和整数k，返回数组排序后第k个最大的元素。这里的“第 k 个”允许重复数字参与排序，不是第 k 个不同的数字。

例如：

输入：[3, 2, 1, 5, 6, 4]，k = 2 输出：5

题目链接：215：数组中的第 K 个最大元素

2. 为什么不需要完整排序

如果把整个数组排好序，再取第k个最大元素，时间复杂度是O(n log n)。

三路划分以后，数组已经分成：

小于 key | 等于 key | 大于 key

对于第k大的元素，只需要判断它位于哪一块：

• 如果“大于key”的数量已经不少于k，答案在右边；
• 如果“大于或等于key”的数量已经不少于k，答案就是key；
• 否则答案在左边，但需要减去右边和中间已经占用的数量。

这就是快速选择。它与快速排序使用同样的划分方式，但不会递归处理两个区间，而是只递归一个区间。

3. Java 代码

import java.util.Random; class Solution { public int findKthLargest(int[] nums, int k) { return qsort(nums, 0, nums.length - 1, k); } public int qsort(int[] nums, int l, int r, int k) { if(l == r) { return nums[l]; } int key = nums[new Random().nextInt(r - l + 1) + l]; int left = l - 1; int right = r + 1; int i = l; while(i < right) { if(nums[i] < key) { swap(nums, ++left, i++); } else if(nums[i] == key) { i++; } else { swap(nums, --right, i); } } // c 是大于 key 的元素个数，b 是等于 key 的元素个数 int c = r - right + 1; int b = right - left - 1; if(c >= k) { return qsort(nums, right, r, k); } else if(c + b >= k) { return key; } else { return qsort(nums, l, left, k - b - c); } } public void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }

4. 为什么进入左边时要修改k

假设右边有c个比key大的数字，中间有b个等于key的数字。如果答案在左边，说明这c + b个数字已经排在答案前面了。

因此，原本要找第k大，进入左区间后只需要找：

k - b - c

大的元素。

5. 复杂度

平均时间复杂度是O(n)，因为每次只继续处理一个区间。递归栈平均需要O(log n)的空间。

八、题目四：最小的 k 个数

1. 题目描述

给定整数数组arr，找出其中最小的k个数。返回顺序可以任意。

例如：

输入：[3, 2, 1]，k = 2 输出：[1, 2] 或 [2, 1]

题目链接：剑指 Offer 40：最小的 k 个数

2. 算法思路

仍然使用三路划分。划分以后：

小于 key | 等于 key | 大于 key

设：

• a：小于key的元素数量；
• b：等于key的元素数量。

分三种情况：

• 如果a > k，最小的k个数全部在左边，继续处理左区间；
• 如果a + b >= k，左边和中间已经足够组成最小的k个数，不需要继续处理；
• 否则还需要从右边找k - a - b个元素。

3. Java 代码

import java.util.Random; class Solution { public int[] getLeastNumbers(int[] nums, int k) { qsort(nums, 0, nums.length - 1, k); int[] ret = new int[k]; for(int i = 0; i < k; i++) { ret[i] = nums[i]; } return ret; } public void qsort(int[] nums, int l, int r, int k) { if(l >= r) return; int key = nums[new Random().nextInt(r - l + 1) + l]; int left = l - 1; int right = r + 1; int i = l; while(i < right) { if(nums[i] < key) { swap(nums, ++left, i++); } else if(nums[i] == key) { i++; } else { swap(nums, --right, i); } } int a = left - l + 1; int b = right - left - 1; if(a > k) { qsort(nums, l, left, k); } else if(a + b >= k) { return; } else { qsort(nums, right, r, k - a - b); } } public void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }

4. 为什么可以直接取数组前k个数

快速选择过程保证最小的k个数字被放到了数组的前k个位置。前k个数字内部不一定有序，但题目允许任意顺序返回，所以复制出来即可。

5.k在两道题中含义不同

第 215 题中的k表示“第 k 大”的名次；第 40 题中的k表示“需要多少个最小数字”。

两道题虽然都使用快速选择，但判断方向不同：

第 k 大：先数右边大于 key 的元素 最小的 k 个：先数左边小于 key 的元素

6. 复杂度

平均时间复杂度是O(n)，返回结果需要O(k)的空间，递归栈平均需要O(log n)的空间。

九、4 道题共同形成的快速排序规律

规律一：三路划分的核心不是代码，而是区间含义

[l, left] 小于 key [left + 1, i - 1] 等于 key [i, right - 1] 未处理 [right, r] 大于 key

只要这四个区间的含义没有混淆，代码就不会完全靠死记。

规律二：从右边交换元素时，当前指针不能移动

swap(nums, --right, i);

右边换来的元素没有判断，所以i保持不变；下一轮继续检查nums[i]。

规律三：完整排序要递归两边

排序数组时：

qsort(nums, l, left); qsort(nums, right, r);

左右两边都要继续处理。

规律四：只找答案时只递归一边

找第k大或者最小的k个数时，不需要把没有答案的那一边排好，只递归可能包含答案的区间。

规律五：快速选择的关键是重新计算 k

当已经排除了一部分元素后，进入下一个区间时，k不一定还是原来的值。进入左边或右边以前，要减去已经确定在前面的元素数量。

十、常用 Java 写法

获取数组长度

nums.length

生成随机下标

new Random().nextInt(r - l + 1) + l

这句话表示在[l, r]中随机取一个下标。

交换数组中的两个元素

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

前置自增与后置自增

++left

先加一再使用新值。

i++

先使用当前值，再加一。

因此：

swap(nums, ++left, i++);

可以理解为：先扩大左边区域，再完成交换，最后让当前扫描位置向右移动。

十一、这一阶段的总结

快速排序和快速选择并不是两套完全不同的东西，它们共享同一个核心：围绕key做三路划分。

• 需要把整个数组排好：左右两边都递归，这就是快速排序；
• 只需要找到某个排名或某个数量范围：根据区间数量判断答案在哪，只递归一边，这就是快速选择；
• 数组中有很多重复元素：把等于key的部分单独拿出来，可以避免对它们重复处理。

我现在理解这类题时，会先画出四个区间，再确定每种情况下哪个指针移动，最后才写代码。尤其是“大于key”的分支，交换以后i不移动，这个细节决定了三路划分是否正确。