原文: https://zhuanlan.zhihu.com/p/...
欢送关注我知乎号: https://www.zhihu.com/people/...
疾速排序QuickSort采纳了分治法Divide-and-ConquerMethod，通过将数组链表或其余元素集分为待排序汇合和已排序汇合，并在一次次迭代中将待排序汇合的元素转化到已排序汇合当中直到全副元素都为已排序则实现排序。
疾速排序利用这一策略，节约了解决已排序元素的老本。算法只关注残余待排序的元素，其中地位间断的未排序元素子串又分为：S1(左侧），pivot(替换枢纽元)，S2（右侧）
以疾速排序来实现升序排序为例：
先从数组当选取出一个数组作为枢轴元pivot。（选取枢纽元的策略很要害）
将待排序汇合所有小于枢轴元pivot的元素移至s1(左侧），所有大于枢轴元pivot的元素移至s2（右侧）：（双指针中的相向指针法）
先将枢轴元pivot(准有序局部)放到最左或者最右辨别出待排序局部。
将i, j别离指向待排序局部索引的最左和最右。
如果i索引指向的元素小于枢纽元，则i++；否则，i进行。j索引指向的元素大于枢纽元，j--；否则，j进行。
如果i<j，则替换两个元素，持续循环3，4步骤；否则跳出循环，将i对应的元素与枢纽元pivot替换（这时候实现了宰割）
这个时候定义枢轴元pivot为已排序局部，对残余未排序局部S1(左侧）S2(右侧)持续循环步骤1，2，3直到所有元素都已排序。
最原始的疾速排序
最原始的疾速排序采纳最简略粗犷的枢纽元选取策略，即选取第一个或最初一个元素为pivot。
该计划的均匀工夫复杂度为O(nlogn)，当遇到数组刚好有序的状况下会呈现最坏工夫复杂度O(n^2)，因为当输出序列自身有序时，会导致S1或S2汇合为空，除枢纽元外所有元素都在S1或S2，此时遍历替换的工夫效率大幅降落，因为节约了另一个区间的作用。
Python代码
nums = [23,2,4,6,2,5,1,6,13,54,8]def quicksort(nums, left, right): # left为最左索引，righ为最右索引 if left >= right: return pivot = left //取第一个元素为pivot i, j = left, right while i < j: while nums[pivot] <= nums[j] and i < j: j -= 1 while nums[pivot] >= nums[i] and i < j: i += 1 if i < j: nums[i], nums[j] = nums[j], nums[i] nums[pivot], nums[i] = nums[i], nums[pivot] quicksort(nums, left, i-1) quicksort(nums, i+1, right)def quicksort2(nums, left, right): # 用栈代替递归 if left >= right: return stack = [] while stack or left < right: if left < right: pivot = left i, j = left, right while i < j: while nums[pivot] <= nums[j] and i < j: j -= 1 while nums[pivot] >= nums[i] and i < j: i += 1 if i < j: nums[i], nums[j] = nums[j], nums[i] nums[pivot], nums[i] = nums[i], nums[pivot] stack.append((left, i, right)) right = i - 1 else: left, mid, right = stack.pop() left = mid + 1quicksort2(nums, 0, len(nums)-1)print(nums) 因为堆栈存储(递归等价于栈代替），疾速排序空间复杂度O(logn)
所以S1和S2约均衡，疾速排序的效率越高，即中值（中位数）是枢纽元最好的抉择（因为能够将序列均分为两个子序列，归并排序通知咱们，这时候是O(NlogN）
但要计算一组数组的中位数就比拟耗时，会减慢快排的效率。
小问题：为什么当轴元pivot放入左侧时, 必须先平移右指针j，而不能先平移左指针i ?
答案：为了防止平移替换过程中, pivot本人被替换掉。
疾速排序的优化
三数中值疾速排序（三数中值法选取枢轴元pivot）
尽管计算一组数组的中位数就比拟耗时，会减慢快排的效率。但能够通过计算数组的第一个left，两头地位(right-left)/2(向下或向上取整)，最初一个right元素的中值来代替。
Python代码
def quicksort_opt1(nums, left, right): if left >= right: return stack = [] while stack or left < right: if left < right: l, m, r = left, (right-left)//2, right # 第一个, 两头地位, 最初一个 pivot = findmedian(l, m, r) # 三数取中值法选取枢轴元pivot i, j = left, right while i < j: while nums[pivot] <= nums[j] and i < j: j -= 1 while nums[pivot] >= nums[i] and i < j: i += 1 if i < j: nums[i], nums[j] = nums[j], nums[i] nums[pivot], nums[i] = nums[i], nums[pivot] stack.append((left, i, right)) right = i - 1 else: left, mid, right = stack.pop() left = mid + 1def findmedian(l, m, r): if nums[l] <= nums[m]: if nums[m] <= nums[r]: return m else: if nums[l] >= nums[r]: return l else: return r else: if nums[m] >= nums[r]: return m else: if nums[l] >= nums[r]: return r else: return l用三数中值法来选取枢轴元pivot肯定水平上防止了最坏的状况产生。
然而即便这样，咱们的疾速排序算法依然有可能呈现最坏的状况：工夫复杂度O(n^2)
因为反复的元素越多会给算法带来越多的无用功，会波及以下一个问题：
简略说是遇到与枢纽元相等的元素时，左右索引指针的平移须要进行吗？
如果只有一个进行：这将导致所有等于枢纽元pivot的元素都挪动到同一侧(S1或S2)，在极其状况下所有元素都是反复，会产生最坏状况O(n^2)
如果都不进行：在极其状况下所有元素都是反复，整个过程枢纽元pivot相当于对整个数组进行了一次遍历，工夫复杂度是(n + n-1 +...+2+1)=(1/2)(1+n)*n， 即工夫复杂度O(n^2)，其实推演一下会发现基于疾速排序的执行规定这种状况跟状况1是等价的，都不进行相当于始终只有一个指针在平移，而且是始终平移到开端才进行。
如果都进行：在极其状况下所有元素都是反复，尽管看似会进行很屡次“无意义”的替换，但因为每次双指针相遇的地点都是数组的中点，这个时候恰好将序列分为两个均等调配的子序列，还是归并排序的原理，达到分治法效率最大化，以此类推会让枢纽元pivot以logn的速度走残缺个数组。所以这种办法最坏状况的工夫复杂度为O(nlogn)
反复元素解决思路：三向切分疾速排序
三向切分疾速排序举荐简书上这个博客
疾速排序(Quick Sort)
www.jianshu.com/p/779bc4b61254
双路疾速排序
图解疾速排序及双路三路疾速排序 - SegmentFault 思否
segmentfault.com/a/1190000021726667
双路疾速排序把待排序区域用指针 i , j 分为三个子区域:
(<nums[pivot])，未知，(>nums[pivot])
将&amp;lt;v和&amp;gt;v两局部放在数组的两端，用i指向&amp;lt;v局部的下一个元素，用j指向&amp;gt;v局部的前一个元素。
从i开始向后遍历，如果遍历的元素&amp;lt;v，则持续向后遍历，直到遍历的元素&amp;gt;v，则进行遍历。同样从j开始向前遍历，如果遍历的元素&amp;gt;v，则持续向前遍历，直到遍历的元素&amp;lt;v，则进行遍历。
替换i指向的元素和j指向的元素。而后i++，j--持续比拟下一个。
Python代码
def quicksort_opt2(nums, left, right): if left >= right: return stack = [] while stack or left < right: if left < right: l, m, r = left, (right-left)//2, right # 第一个, 两头地位, 最初一个 pivot = findmedian(l, m, r) # 三数取中值法选取枢轴元pivot nums[pivot], nums[left] = nums[left], nums[pivot] pivot = left i, j = left+1, right while i <= j: # 为什么不能是 i < j? # 此处先平移j和先平移i对后果没有影响,因为 i=left+1避开了pivot while nums[i] < nums[pivot] and i <= j: #不能改为nums[i] <= nums[pivot], 因为这种形式将间断呈现的这些值归为其中一方, 使得两棵树不均衡 i += 1 while nums[j] > nums[pivot] and i <= j: j -= 1 if i <= j: nums[i], nums[j] = nums[j], nums[i] j -= 1 i += 1 nums[pivot], nums[j] = nums[j], nums[pivot] #因为pivot搁置在右边, 所以不可与左侧指针i替换---->会造成有限循环 stack.append((left, j, right)) right = j - 1 else: left, mid, right = stack.pop() left = mid + 1nums = [23,2,4,6,2,5,1,6,13,54,8]quicksort_opt2(nums, 0, len(nums)-1)print(nums) 问题1：为什么此处不能用 i < j 代替 i <= j 当作循环条件？
问题2：为什么平移完结后, pivot要跟 j 替换 而不是 i ？为什么跟 i 替换会造成有限循环？
那么在此基础上，咱们是否再次优化，将前文提到的反复元素'无意义'的替换也省了？ 当然能够，上面的三路疾速排序就是围绕这点进行优化。
三路疾速排序 3 way quick sort
在双路快排把未排序区域分为三个子区域的根底上，三路快排多分了一个子区域用来寄存反复且等于pivot的元素，来辨认并跳过他们。
在双路疾速排序的根底上，咱们把等于v的元素独自作为一个局部。lt指向小于v局部的最初一个元素，gt指向大于v局部的第一个元素。
从i开始向后遍历，如果遍历的元素e=v，则e间接合并到=v局部，而后i++持续遍历。如果遍历的元素e&amp;lt;v，则将e和=v局部的第一个元素（lt+1指向的元素）替换，而后lt++，i++持续遍历。如果遍历的元素e&amp;gt;v，则将e和&amp;gt;v局部前一个元素（gt-1指向的元素）替换，而后gt--，不过此
Python代码
def quicksort_opt3(nums, left, right): if left >= right: return stack = [] while stack or left < right: if left < right: l, m, r = left, (right-left)//2, right pivot = findmedian(l, m, r) nums[pivot], nums[left] = nums[left], nums[pivot] pivot = left lt, gt = left, right + 1 i = left + 1 while i < gt: if nums[i] < nums[pivot]: nums[i], nums[lt+1] = nums[lt+1], nums[i] i += 1 lt += 1 elif nums[i] > nums[pivot]: nums[i], nums[gt-1] = nums[gt-1], nums[i] gt -= 1 else:# nums[i] == nums[pivot] i += 1 nums[pivot], nums[lt] = nums[lt], nums[pivot] stack.append((left, lt, right)) right = lt - 1 else: left, mid, right = stack.pop() left = mid + 1nums = [23,2,4,6,2,5,1,6,13,54,8]quicksort_opt3(nums, 0, len(nums)-1)print(nums) 疾速排序复杂度剖析
疾速排序的均匀工夫复杂度为O(nlogn)
疾速排序均匀复杂度数学证实可参考此答复：
https://www.zhihu.com/questio...
疾速排序的短板：
即便是三路疾速排序也做不到堆排序那样保障最坏工夫复杂度为O(nlogn)
疾速排序是不稳固排序 (所谓稳固就是当待排数组中存在反复元素的时候，排序后反复元素的绝对程序不会扭转)
当待排序序列元素数量很小(N<=20)的时候，疾速排序不如插入排序快，并且插入排序是稳固排序。
github代码出处: https://github.com/stevezkw19...
欢送关注我的github：stevezkw1998 - Overview