关于快速排序:快速排序及其优化超详细解答代码真正理解
原文: 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) ...