HTML5Academy-Codesmith：在之前的《算法之旅》中，给大家分享了冒泡排序的方法和选择排序的方法。它们都属于时间复杂度为O(n^2)的“慢”排序。今天给大家分享一下各种排序算法中使用最广泛、速度最快的排序算法——快速排序法【平均时间复杂度为O(nlogn)】。Tips1：关于“算法”和“排序”的基础知识，在前面的“选择排序法”中已经详细讲解过了。Tips2：如无特殊说明，本文中的快速排序是从小到大排序的。快速排序法原理快速排序是分区交换排序的一种，采用分而治之的策略，通常称为分治法。分而治之的基本思想：将原问题分解为若干规模较小但结构与原问题相似的子问题。递归求解这些子问题，然后将这些子问题的结果组合成原问题的结果。基本原则是从序列中选择一个数字作为“基线”；所有小于“基线”的数字都移到“基线”的左侧；所有大于或等于“基线”的数字都移到“基线”的右侧；本次移动结束后，“基准”处于两个序列的中间，不再参与后续排序；对于“benchmark”左右两个子序列，重复上述步骤，直到所有子序列都剩下最多一个数。SchematicDiagram现有一个序列[8,4,7,2,0,3,1]，下面演示快速排序方法如何对其进行排序。将实现快速排序的步骤分解为选择“基数”并将其与原数组分离。先获取基数的索引值，然后用拼接数组的方法提取基数。Tips:本例中，benchmark的索引值=parseInt(sequencelength/2)Tips:拼接方法会改变原来的数组。例如，arr=[1,2,3]；基索引值为1，基值为2，原数组变为arr=[1,3]；遍历序列，拆分序列并与“base”比较大小，拆分为两个子序列，小于“benchmark”的数存入leftArr数组，大于等于的数存入leftArr数组“基准”存储在rightArr数组中。”的数字存放在rightArr中，因为需要遍历序列并将每个数字与“reference”进行比较，所以需要使用for语句实现递归调用，遍历子序列并将结果组合起来subsequences定义一个函数，形参在接收数组函数quickSort(arr){};实现递归调用遍历子序列，使用concat数组的方式组合子序列的结果判断长度子序列。在递归调用过程中，当子序列长度等于1时，停止递归调用，返回当前数组。快速排序完整代码效率时间复杂度快速排序的最坏情况：每次选择的“基线”是序列中的最小数/最大数，类似于冒泡排序法（每次只确定一个数[基数]的顺序），时间复杂度为O(n^2)bestcase:the"baseline"每次选择的是序列中的中间数（是中位数，不是上面的位置），然后每次把当前序列分成两个等长的子序列。此时第一次有n/2、n/2两个子序列，第二次有n/4、n/4、n/4、n/4四个子序列，以此类推，nnumbers一共需要logn次完成排序（2^x=n,x=logn），然后每次的复杂度都是n，时间复杂度是O(nlogn)。空间复杂度最坏情况：n-1次递归调用，其空间复杂度为O(n)最佳情况：需要logn次递归调用，其空间复杂度为O(logn)算法稳定性Quicksort是一种不稳定的排序算法例如：现有序列为[1,0,1,3]，选择“基”数作为第二个1，经过第一轮比较后，变为[0,1,1,3]，左边序列为[0]，右边的序列是[1,3]（右边序列中的1就是前面的第一个1）。不难发现，破坏了原来序列中两个1的顺序，改变了顺序。自然是一种“不稳定”的排序算法关于O在之前的文章《冒泡排序法》中，我们已经详细解释了O是什么，这里就不多说了，直接上图链接到相关的文章算法之旅|选择排序算法之旅|HappyBubbleSort每天生活很辛苦，代码不容易，但不要忘记微笑！
