Quicksort

本文介绍如何通过阿里云Quick BI连接AnalyticDB for PostgreSQL数据库。 在Quick BI中新建AnalyticDB for PostgreSQL数据源登录Quick BI控制台。单击工作空间>数据源，进入数据源管理页面。单击新建数据源>AnalyticDB for PostgreSQL。在添加AnalyticDB for PostgreSQL数据源页面进行参数配置。 配置项说明显示名称数据源名称。数据库地址AnalyticDB for PostgreSQL的连接地址 。端口链接地址对应的端口号。数据库数据库名。Schema数据库Schema名。用户名AccessKey ID。密码Access Key Secret。完成上述参数配置后，单击连接测试测试连通性，测试通过后，单击添加添加数据源。使用Quick BI成功连接AnalyticDB for PostgreSQL数据源后，用户可以参考以下步骤学习如何在Quick BI中完成报表分析等操作。 创建数据集制作仪表板制作电子表格制作数据门户关于Quick BI的更过功能，请参见Quick BI相关文档。 本文作者：陆封阅读原文 本文为云栖社区原创内容，未经允许不得转载。

来源 | 愿码(ChainDesk.CN)内容编辑愿码Slogan | 连接每个程序员的故事网站 | http://chaindesk.cn愿码愿景 | 打造全学科IT系统免费课程，助力小白用户、初级工程师0成本免费系统学习、低成本进阶，帮助BAT一线资深工程师成长并利用自身优势创造睡后收入。官方公众号 | 愿码 | 愿码服务号 | 区块链部落免费加入愿码全思维工程师社群 | 任一公众号回复“愿码”两个字获取入群二维码本文阅读时长：6min你是否理解QuickSort与MergeSort之间的区别？你稳定和不稳定的排序算法的含义是什么？当面试官问到以上问题应如何回答？如果排序算法保持数字/记录的相对顺序，即如果需要排序1 1 2 3，那么如果不更改前两个排序的顺序，则认为排序算法是稳定的，但如果交换它们，则尽管总体结果或排序顺序保持不变，但它将变得不稳定。当您对对象进行排序时（例如，按键对键值对进行排序），这种差异会变得更加明显。在稳定算法的情况下，保留键值对的原始顺序，如下例所示。实际上，如果您忘记提及这些概念，面试官可能会将此问题视为快速排序与合并排序的后续工作。quicksort和mergesort之间的主要区别之一是快速排序不稳定，而合并排序是一种稳定的排序算法。顺便说一句，如果您不熟悉Quicksort和Mergesort等基本排序算法，那么我建议您学习下全面的数据结构课程，如数据结构和算法：深度使用Java。它将为您提供进一步探索所需的所有基础知识。稳定与不稳定算法假设您需要按键的递增顺序对以下键值对进行排序：INPUT：（4,5）（3,2）（4,3）（5,4）（6,4）现在，有两个密钥相同的两对的可能解决方案即（4,5）和（4,3）如下所示：OUTPUT1：（3,2），（4,5），（4,3），（5,4），（6,4）OUTPUT2：（3,2 ），（4,3），（4,5），（5,4），（6,4）将产生第一个输出的排序算法称为稳定排序算法，因为保持了相等键的原始顺序，您可以看到（4,5）以排序顺序出现在（4,3）之前，这是原始顺序，即在给定的输入中，（4,5）出现在（4,3）之前。产生第二输出的算法将被称为不稳定的排序算法，因为具有相同键的对象的顺序不按排序顺序维持。你可以看到，在第二个输出中，（4,3）出现在（4,5）之前，原始输入中不是这种情况。现在，最大的问题是稳定和不稳定排序算法的一些例子是什么？那么，你可以把所有众所周知的排序算法分成稳定和不稳定的。稳定算法的一些示例是合并排序，插入排序，冒泡排序和二叉树排序。而QuickSort，堆排序和选择排序是不稳定的排序算法。如果你还记得，Collections.sort（）Java Collection框架中的方法使用迭代合并排序，这是一种稳定的算法。如果输入数组被部分排序，它的比较也比NLog（N）少得多。如果您有兴趣了解有关此主题的更多信息，我建议您学习数据结构和算法，比如算法和数据结构-第1部分和第2部分。它是Java程序员算法的综合课程之一。稳定与不稳定算法示例以下图片解释了稳定和不稳定的排序是如何工作的：这就是稳定和不稳定排序算法之间的区别。请记住，如果在排序的输出中保持相等键或数字的原始顺序，则该算法称为排序算法。稳定排序算法的一些常见示例是合并排序，插入排序和冒泡排序。 你还想要知道哪些关于面试题的知识呢？请在下方留言！

只要是个工程师，就或多或少的知道快排，其中很多人都能轻松的写出一个快排的实现。但是大家了解阮一峰快排事件吗，是否知道快排的最佳实践？本文从一个争执讲起，通过生动详实的例子让你真正了解快排。嗯，这确实是一篇炒冷饭的文章，但我希望能把冷饭炒成好吃的蛋炒饭。闲话少叙，马上开始~1. 阮一峰快排事件整个事件用一句话来概括，就是有人diss阮一峰的快排写的不对，如下图。其实从图上也看到了，这个微博并没有发酵起来，直到一篇发表在掘金上的文章《阮一峰版快速排序完全是错的》（文章已经不能访问），然后又被人提问到知乎上，整个事情才变得热闹了起来。Diss的主要点在于两个：一个是拿哨兵用的splice而不是数组下标一个是算法使用的是额外空间而不是原地分割哨兵：快排中的被选中做为比较对象的基准元素这件事情上，绝大多数同学都支持阮老师。其实，我觉得这种粗糙的批评是有问题的。有三个原因：1.1 splice已经被提及，并且时间复杂度没有量级上的区别首先，在阮一峰的快排博客的评论里，他已经提到，splice确实是有问题的，见下图。而且，即使使用了splice，时间复杂度也是O(n)+O(n)=O(n)，在量级上并没有影响。1.2 算法没有规定空间复杂度，并且极端情况下的算法问题是通病另外，快排在维基（中文|英文）的定义上只规定了时间复杂度，对于空间复杂度的定义是，中文：根据实现的方式不同而不同英文：O(n) auxiliary (naive) O(log n) auxiliary所以用空间复杂度来攻击算法是没有依据的。另外，winter在上面知乎的问题中也提及，原地快排的空间复杂度因为不是尾递归必须用栈，空间复杂度是O(log(n))，而即使快排每次都用新的空间，也无非是O(2n)=O(n)而已。当然，若是极端情况下（哨兵每次都把数组分成n-1和1个）阮老师的算法中空间复杂度会退化成O(n的平方)，不过这种情况是非原地快排的通病，而不是阮式算法的特例，所以也不能怪到阮老师头上。1.3 基于通俗易懂的定位更值得肯定阮老师的博客其实一直是通俗易懂的，我也把通俗易懂作为我自己一直的追求。这个算法可能不是没有瑕疵，但是却绝对称不上错。而我们做的也不是抨击瑕疵，而是考虑还有哪些改进的方向。阮老师的这个快排实现确实好记，包括我自己，就是通过阮老师的这个算法才算真正记住了快排。在这个基础上，我觉得这个微博发的没啥意义。2. 快速排序的复杂度分析前面我们BB了半天阮一峰快排事件，中间我们多次提到了快排的时间复杂度和空间复杂度，在本部分，我们将分析为什么它们是这样的。2.1 时间复杂度如果足够理想，那我们期望每次都把数组都分成平均的两个部分，如果按照这样的理想情况分下去，我们最终能得到一个完全二叉树。如果排序n个数字，那么这个树的深度就是log2n+1，如果我们将比较n个数的耗时设置为T(n)，那我们可以得到如下的公式[1]：T(n) ≤ 2T(n/2) + n，T(1) = 0 T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n ……T(n) ≤ nT(1) + (log2n)×n = O(nlogn) 而在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边。这时候我们的比较次数就变为=O(n的平方)2.2 空间复杂度2.2.1 原地排序原地快排的空间占用是递归造成的栈空间的使用，最好情况下是递归log2n次，所以空间复杂度为O(log2n)，最坏情况下是递归n-1次，所以空间复杂度是O(n)。2.2.2 非原地排序对于非原地排序，每次递归都要声明一个总数为n的额外空间，所以空间复杂度变为原地排序的n倍，即最好情况下O(nlog2n)，最差情况下O(n的平方)对于复杂度这块还想了解更详细内容的同学可以参考 《快速排序复杂度分析》3. 快排的最佳实践呢经过上面的部分，想必你对快排在前端的是是非非已经有了一个初步的了解。那么，什么是快排的最佳实践呢？3.1 最简单好记这是阮一峰老师的算法实现的变体，因为用了es6的写法，从而使得代码量变得更加精简，主体更加突出。function quickSortRecursion (arr) { if (!arr || arr.length < 2) return arr; const pivot = arr.pop(); let left = arr.filter(item => item < pivot); let right = arr.filter(item => item >= pivot); return quickSortRecursion(left).concat([pivot], quickSortRecursion(right));}3.2 更高的效率这里贴一个winter的实现，想看更多的实现，可以移步大佬们在github上的互喷地址function wintercn_qsort(arr, start, end){ var midValue = arr[start]; var p1 = start, p2 = end; while(p1 < p2) { swap(arr, p1, p1 + 1); while(compare(arr[p1], midValue) >= 0 && p1 < p2) { swap(arr, p1, p2–); } p1 ++; } if(start < p1 - 1) wintercn_qsort(arr, start, p1 - 1); if(p1 < end) wintercn_qsort(arr, p1, end);}3.3 实际情况下的优化方法刚才也说到，快排其实是存在最差情况的。实际上，在日常工作中，如果真的有这样大数据量级的优化需要，我们往往会根据实际情况对快排进行各种各样的优化。主要的思路有以下几点[3]：合理选择哨兵，尽量避免出现斜树对于重复的元素，一次性的从排来使用选择排序来处理小数组（V8中设定为10）使用堆排序来处理最坏情况的分区用从两边向中间遍历来代替从左向右遍历使用尾递归在不同的线程中并发处理问题因为本文实在有点长，这块就不再做详细的阐述，有需要的同学可以自行参阅《快速排序算法的优化思路总结》。3.总结本文从阮一峰快排事件入手，分析了快排在不同情况下的空间复杂度和时间复杂度，并给出了快排的最佳实践和优化方法。希望能对大家了解快排有所帮助。参考文档：《快速排序复杂度分析》《如何看待文章《面试官：阮一峰版的快速排序完全是错的》？》《快速排序算法的优化思路总结》 ...