之前一起看了归并排序和一些利用归并排序可以解决的经典题目，今天我们再来说一下另一个高频考点，快速排序。甚至比归并排序考的还勤。你或许已经掌握了快速排序，或者看过一些其他文章，不过我相信，读完这个文章肯定还会有所收获！
今天我们来说一下快速排序，这个排序算法也是面试的高频考点，原理很简单，我们一起来扒一下他吧。
我们先来说一下快速排序的基本思想，很容易理解。
1.先从数组中找一个基准数
2.让其他比它大的元素移动到数列一边，比他小的元素移动到数列另一边，从而把数组拆解成两个部分。
3.再对左右区间重复第二步，直到各区间只有一个数。
见下图
上图则为一次快排示意图，下面我们再利用递归，分别对左半边区间也就是 [3,1,2] 和右半区间 [7,6,5,8] 执行上诉过程，直至区间缩小为 1 也就是第三条，则此时所有的数据都有序。
简单来说就是我们利用基准数通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比基准数小，另一部分记录的关键字均比基准数大，然后分别对这两部分记录继续进行分割，进而达到有序。
我们现在应该了解了快速排序的思想，那么大家还记不记得我们之前说过的归并排序，他们两个用到的都是分治思想，那他们两个有什么不同呢？见下图
注：这里我们以区间的第一个元素作为基准数
虽然归并排序和快速排序都用到了分治思想，但是归并排序是自下而上的，先处理子问题，然后再合并，将小集合合成大集合，最后实现排序。
快速排序是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数需要利用辅助数组保存元素。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
我们根据思想可知，快速排序算法的核心就是如何利用基准数将记录分区，这里我们主要介绍两种容易理解的方法，一种是挖坑填数，另一种是利用双指针思想进行元素交换。
下面我们先来介绍下挖坑填数的分区方法
基本思想是我们首先以序列的第一个元素为基准数，然后将该位置挖坑，下面判断 nums[hight] 是否大于基准数，如果大于，则左移 hight 指针，直至找到一个小于基准数的元素，将其填入之前的坑中，则 hight 位置会出现一个新的坑，此时移动 low 指针，找到大于基准数的元素，填入新的坑中。不断迭代直至完成分区。
大家直接看我们的视频模拟吧，一目了然。
注：为了便于理解所以采取了挖坑的形式展示
是不是很容易就理解啦，下面我们直接看代码吧。
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (low < hight) {
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
}
public int partition (int[] nums, int low, int hight) {
int pivot = nums[low];
while (low < hight) {
//移动hight指针
while (low < hight && nums[hight] >= pivot) {
hight--;
}
//填坑
if (low < hight) nums[low] = nums[hight];
while (low < hight && nums[low] <= pivot) {
low++;
}
//填坑
if (low < hight) nums[hight] = 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 hight) {
if (low < hight) {
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
}
public int partition (int[] nums, int low, int hight) {
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
//基准值归位
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;
}
}快速排序的时间复杂度分析
快排也是用递归来实现的。所以快速排序的时间性能取决于快速排序的递归树的深度。
如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那么此时的递归树是平衡的，性能也较好，递归树的深度也就和之前归并排序求解方法一致。
我们每一次分区需要对数组扫描一遍，做 n 次比较，所以最优情况下，快排的时间复杂度是 O(nlogn)。
但是大多数情况下我们不能划分的很均匀，比如数组为正序或者逆序时，即 [1,2,3,4] 或 [4,3,2,1] 时，此时为最坏情况，那么此时我们则需要递归调用 n-1 次，此时的时间复杂度则退化到了 O(n^2)。
快速排序的空间复杂度分析
快速排序主要时递归造成的栈空间的使用，最好情况时其空间复杂度为O (logn),对应递归树的深度。最坏情况时则需要 n-1 次递归调用，此时空间复杂度为O(n)。
快速排序的稳定性分析
快速排序是一种不稳定的排序算法，因为其关键字的比较和交换是跳跃进行的，见下图。
此时无论使用哪一种方法，第一次排序后，黄色的 1 都会跑到红色 1 的前面，所以快速排序是不稳定的排序算法。
好啦，快速排序我们掌握的差不多了，下面我们一起来看看如何对其优化吧。
快速排序的迭代写法
该方法实现也是比较简单的，借助了栈来实现，很容易实现。主要利用了先进后出的特性，这里需要注意的就是入栈的顺序，这里算是一个小细节，需要注意一下，其中分区函数和上面一致。大家只需看入栈出栈情况即可。
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 hight = stack.pop();
if (low < hight) {
int index = partition(nums, low, hight);
stack.push(index - 1);
stack.push(low);
stack.push(hight);
stack.push(index + 1);
}
}
return nums;
}
public int partition (int[] nums, int low, int hight) {
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
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;
}
}快速排序优化
三数取中法
我们在上面的例子中选取的都是 nums[low] 做为我们的基准值，那么当我们遇到特殊情况时呢？见下图
我们按上面的方法，选取第一个元素做为基准元素，那么我们执行一轮排序后，发现仅仅是交换了 2 和 7 的位置，这是因为 7 为序列的最大值。
所以我们的 pivot 的选取尤为重要，选取时应尽量避免选取序列的最大或最小值做为基准值。则我们可以利用三数取中法来选取基准值。
也就是选取三个元素中的中间值放到 nums[low] 的位置，做为基准值。这样就避免了使用最大值或最小值做为基准值。
所以我们可以加上这几行代码实现三数取中法。
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low); 其含义就是让我们将中间元素放到 nums[low] 位置做为基准值，最大值放到 nums[hight],最小值放到 nums[mid],即 [4,2,3] 经过上面代码处理后，则变成了 [3,2,4]。
此时我们选取 3 做为基准值，这样也就避免掉了选取最大或最小值做为基准值的情况。
三数取中法
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (low < hight) {
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
}
public int partition (int[] nums, int low, int hight) {
//三数取中，大家也可以使用其他方法
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
//下面和之前一样，仅仅是多了上面几行代码
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
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;
}
}和插入排序搭配使用
我们之前说过，插入排序在元素个数较少时效率是最高的，没有看过的同学可以去看一下之前的文章，所以当元素数量较少时，快速排序反而不如插入排序好用。
所以我们可以设定一个阈值，当元素个数大于阈值时使用快速排序，小于等于该阈值时则使用插入排序。我们设定阈值为 7 。
三数取中+插入排序
class Solution {
private static final int INSERTION_SORT_MAX_LENGTH = 7;
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort (int[] nums, int low, int hight) {
if (hight - low <= INSERTION_SORT_MAX_LENGTH) {
insertSort(nums,low,hight);
return;
}
int index = partition(nums,low,hight);
quickSort(nums,low,index-1);
quickSort(nums,index+1,hight);
}
public int partition (int[] nums, int low, int hight) {
//三数取中，大家也可以使用其他方法
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
int pivot = nums[low];
int start = low;
while (low < hight) {
while (low < hight && nums[hight] >= pivot) hight--;
while (low < hight && nums[low] <= pivot) low++;
if (low >= hight) break;
swap(nums, low, hight);
}
swap(nums,start,low);
return low;
}
public void insertSort (int[] nums, int low, int hight) {
for (int i = low+1; i <= hight; ++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;
}
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}好啦，我们的插入排序和快速排序的搭配使用就搞定啦。
我们继续看下面这种情况
那么我们为什么不能将相同元素放到一起呢？这样就能大大减小递归调用时的区间大小，见下图。
这样就减小了我们的左右区间大小，只需对区间 [3,1,2,4] 和 [8] 执行相同操作即可，我们将数组切分成了三部分，小于基准数的左区间，大于基准数的右区间，等于基准数的中间区间。
下面我们来看一下如何达到上面的情况，我们先来进行视频模拟，模拟之后应该就能明白啦。
我们来剖析一下视频，其实原理很简单，我们利用探路指针也就是 i，遇到比 pivot 大的元素，则和 right 指针进行交换，交换后 right 指向的元素肯定比 pivot 大，则 right--，但是，此时我们的 nums[i] 指向的元素并不知道情况，所以我们的 i 指针先不动，继续判断。
如果此时 nums[i] < pivot 则与 left 指针交换，注意此时我们的 left 指向的值肯定是等于 povit的，所以交换后我们要 left++,i++, nums[i] == pivot 时，仅需要 i++ 即可，继续判断下一个元素。我们也可以借助这个思想来解决经典的荷兰国旗问题。
好啦，我们下面直接看代码吧。
三数取中+三向切分+插入排序
class Solution {
private static final int INSERTION_SORT_MAX_LENGTH = 7;
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int nums[], int low, int hight) {
//插入排序
if (hight - low <= INSERTION_SORT_MAX_LENGTH) {
insertSort(nums,low,hight);
return;
}
//三数取中
int mid = low + ((hight-low) >> 1);
if (nums[low] > nums[hight]) swap(nums,low,hight);
if (nums[mid] > nums[hight]) swap(nums,mid,hight);
if (nums[mid] > nums[low]) swap(nums,mid,low);
//三向切分
int left = low, i = low + 1, right = hight;
int pvoit = nums[low];
while (i <= right) {
if (pvoit < nums[i]) {
swap(nums,i,right);
right--;
} else if (pvoit == nums[i]) {
i++;
} else {
swap(nums,left,i);
left++;
i++;
}
}
quickSort(nums,low,left-1);
quickSort(nums,right+1,hight);
}
public void insertSort (int[] nums, int low, int hight) {
for (int i = low+1; i <= hight; ++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;
}
}
public void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}好啦，一些常用的优化方法都整理出来啦，还有一些其他的优化算法九数取中，优化递归操作等因为不常用就不在这里进行描述啦，
感兴趣的可以自己看一下。好啦，这期的文章就到这里啦，我们下期见，拜了个拜。
本文由哈喽比特于3年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/h1rqXj3ivyZDOw-kAwFLIQ
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
