先简单回顾一下,今天预计分析的题目:
题目叙述:
题目的条件:
如何利用 Quick sort 进行排序
上次说到 Quick Sort 有两种实作方法,分别为
接下来我们会分别介绍两种方式的实作
首先,我们取正中间的元素作为 pivot,并设置 i
, j
指针指向数列左边:
# Partition
i, j, pivot = left, left, (left + right) // 2
其中 left
为数列左侧 index, right
为数列右边 index,以 [5, 2, 3, 1]
为例, left
为 0,而 right
为 4。下图是初始化 i, j, 和选定 pivot。
接着用回圈将 i
指向比 pivot 大的元素;再将 j
指向比 pivot 小的元素
# When the loop stoped, nums[i] >= nums[pivot]
while(i < right and nums[i] < nums[pivot]): i += 1
# When the loop stoped, nums[j] < nums[pivot]
if j < i: j = i
while(j < right and nums[j] >= nums[pivot]): j += 1
由於目标是将小的元素换於左侧,因此若比 pivot 小的元素本来就在左侧,则不需要做任何处理,因此若 j < i
则直接让 j = i
,继续向右开始搜寻以节省时间。下图是第一次扫描, i 停在 0,而 j 停在 1。
回圈结束,此时 nums[i]
为比 nums[pivot]
大的元素,而 nums[j]
为比 nums[pivot]
小的元素,当 i < j
(也就是 大的数 在 小的数左边)则将两者交换,而若有交换到 pivot ,则需更新 pivot 的位置,并将指标们 + 1 ,继续向右扫描。下图是交换数值,并继续扫描。
if i < j and j < right:
# Swap
nums[i], nums[j] = nums[j], nums[i]
if i == pivot: pivot = j
# Move on
i += 1
j += 1
用回圈重复执行 2 ~ 3 步,直到指标扫完所有元素
while(i < right and j < right)
此时数列左侧都是小於 pivot 的数,而右侧都是大於 pivot 的数。由於我们第二步实作大小比较时,让 i
指向大於或「等於」pivot 的元素,因此两侧的交界就在於 i
,若先前是让 j
指向小於或等於 pivot 的元素,则此时交界会在於 j
。下图是扫完、交换完一轮後,指标的最终位置。
将 Pivot 交换至正确位置,也就是上述的交界处。下图是将 Pivot 与 i 交换,放到正确位置。而在此例中,正好 i 和 Pivot 在同一处。
# Put pivot to the correct location
nums[i], nums[pivot] = nums[pivot], nums[i]
至此,我们已经成功找到一个数的正确位置,并将数列切分为小於该数的左侧子数列,和大於该数的右侧子数列。此处我们用递回方式,再将划分出的两个子数列继续进行排序。下图是经过一轮扫描,可确定 3 的正确位置在 index = 2 处,而左右可分为两个子数列,透过递回继续进行排序。
# Recursion
self.QuickSort_Lomuto(left, i)
self.QuickSort_Lomuto(i + 1, right)
最後,设置递回函式的终止条件
# End Condition
if left >= right: return
当 left >= right
时停止,也就是当子数列中没有元素时即停止。
至此,我们已经完成 Lomuto 版本的 Quick Sort ,完整的 Code 如下:
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.nums = nums
self.QuickSort_Lomuto(0, len(nums))
return nums
def QuickSort_Lomuto(self, left: int, right: int) -> None:
nums = self.nums
# End Condition
if left >= right: return
# Partition
i, j, pivot = left, left, (left + right) // 2
# Sort
while(i < right and j < right):
# When the loop stoped, nums[i] >= nums[pivot]
while(i < right and nums[i] < nums[pivot]): i += 1
# When the loop stoped, nums[j] < nums[pivot]
if j < i: j = i
while(j < right and nums[j] >= nums[pivot]): j += 1
if i < j and j < right:
# Swap
nums[i], nums[j] = nums[j], nums[i]
if i == pivot: pivot = j
# Move on
i += 1
j += 1
# Put pivot to the correct location
nums[i], nums[pivot] = nums[pivot], nums[i]
# Recursion
self.QuickSort_Lomuto(left, i)
self.QuickSort_Lomuto(i + 1, right)
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
# 先判断 nums 有无资料
if not nums:
return
# 开始 Quick Sort 的 Hoare 方法
self.QuickSort_Hoare(nums, 0 , len(nums) - 1)
return nums
def QuickSort_Hoare(self, nums, start, end):
# 把 start ~ end 之间要进行排序
if start >= end:
return
# 有两个指标,k 从左边往右,j 从右边往左
k, j = start, end
# pivot 为中位数
pivot = nums[(start + end) // 2]
# 当 k 与 j 会逐渐靠近,直到 k > j
while k <= j:
# 在 k 与 j 还没相遇的情况,k 会一直往右,直到停在比 pivot 大的位置
while k <= j and nums[k] < pivot:
k += 1
# 在 k 与 j 还没相遇的情况,j 会一直往左,直到停在比 pivot 小的位置
while k <= j and nums[j] > pivot:
j -= 1
# 在 k 与 j 还没相遇的情况,此时 k 停在比 pivot 大的位置,j 停在比 pivot 小的位置,将两者的值互换,并且两个互相接近一个位置
if k <= j:
nums[k], nums[j] = nums[j], nums[k]
k += 1
j -= 1
# print(nums)
# 当 k 与 j 相遇後,位置也排完,此时 k > j,那麽 start~j 是 左边比 pivot 小的,k ~ end 是 右边比 pivot 大的
self.QuickSort_Hoare(nums, start, j)
self.QuickSort_Hoare(nums, k, end)
前言 Hi, 我是鱼板伯爵今天要在我们的专案里面加入场景的路由,这样可以方便管理我们每个场景,教学内...
min-width 与 max-width 这两个属性跟 min-height 与 max-heig...
What is the Event? “HTML DOM events allow JavaScri...
把pod部署到特定node上面 k8s的特性来说,基本上部署到k8s一定是会挑资源最轻的那台node...
原来已经一个月了,想当初充满着犹豫要不要开赛,开赛後又想着会不会断赛,深知真的断赛肯定会後悔,庆幸挺...