【第九天 - Quick Sort 题目分析】

先简单回顾一下,今天预计分析的题目:

  • 题目叙述:

    题目叙述

    • 测资的 Input/Output:
    • 会拿到 nums 的变数,须回传排序好的资料
      题目I/O
  • 题目的条件:

    • 可能会有 1~ 50000 个数字要进行排序
    • 每个数字会在 - 0.0005 ~ 50000 之间

    题目限制

  • 如何利用 Quick sort 进行排序

  • 上次说到 Quick Sort 有两种实作方法,分别为

    • Lomuto:两个指标都是指向开始
    • Hoare :一个指标会指向开始,一个指标指向结尾
  • 接下来我们会分别介绍两种方式的实作

1. Lomuto

  • 如昨日所提及,Lomuto 会将两指针放於左边。排序时,指针向右边扫描,将小於 pivot 的元素交换於左边,大於 pivot 的元素交换至右边,同时可找出当前 pivot 的正确位置。
  1. 首先,我们取正中间的元素作为 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。

初始

  1. 接着用回圈将 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。
    i停在0,j停在1

  2. 回圈结束,此时 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
    

    交换数值

  3. 用回圈重复执行 2 ~ 3 步,直到指标扫完所有元素

    while(i < right and j < right)
    

    此时数列左侧都是小於 pivot 的数,而右侧都是大於 pivot 的数。由於我们第二步实作大小比较时,让 i 指向大於或「等於」pivot 的元素,因此两侧的交界就在於 i ,若先前是让 j 指向小於或等於 pivot 的元素,则此时交界会在於 j 。下图是扫完、交换完一轮後,指标的最终位置。
    最终位置

  4. 将 Pivot 交换至正确位置,也就是上述的交界处。下图是将 Pivot 与 i 交换,放到正确位置。而在此例中,正好 i 和 Pivot 在同一处。

    # Put pivot to the correct location
    nums[i], nums[pivot] = nums[pivot], nums[i]
    

    i和pivot

  5. 至此,我们已经成功找到一个数的正确位置,并将数列切分为小於该数的左侧子数列,和大於该数的右侧子数列。此处我们用递回方式,再将划分出的两个子数列继续进行排序。下图是经过一轮扫描,可确定 3 的正确位置在 index = 2 处,而左右可分为两个子数列,透过递回继续进行排序。

    # Recursion
    self.QuickSort_Lomuto(left, i)
    self.QuickSort_Lomuto(i + 1, right)
    

    排列

  6. 最後,设置递回函式的终止条件

    # 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)

2. Hoare

  • 首先,我们会选择一个 pivot ,k 与 j 会逐渐靠近,k 会向右移动停在比 pivot 大的数字位置,j 会向左移动停在比 pivot 小的位置,当 k 与 j 都停止後,就做交换,直到 k 与 j 擦肩而过 ( k > j )

初始

  • 当 k 与 j 都交换完毕,左边就是 < pivot 的 ( start ~ j ),右边会有 ≥ pivot 的 ( k ~ end )

左右边

  • 因此,我们可以知道,每次我们会给一段要比较的开始与结尾,也就是 start 与 end,接下来就是决定 pivot,并且将比较小的放左边,大的放右边,不断重复这样的行为,需要比较的数字就会越来越小群,直到开始与结尾相同(就是剩下一个数字),代表这个数字位置就能固定下来了
  • python 实作如下
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)

<<:  Day 9 | 清单元件类型

>>:  【Day09】陈述式与表达式

[Day21] Flutter - Presentation AutoRouter(part5)

前言 Hi, 我是鱼板伯爵今天要在我们的专案里面加入场景的路由,这样可以方便管理我们每个场景,教学内...

min-width & max-width - 金鱼都能懂的CSS必学属性

min-width 与 max-width 这两个属性跟 min-height 与 max-heig...

#23 JS: HTML DOM Events - Part 1

What is the Event? “HTML DOM events allow JavaScri...

[DAY14]Label进阶使用-Affinity and anti-affinity

把pod部署到特定node上面 k8s的特性来说,基本上部署到k8s一定是会挑资源最轻的那台node...

Day 30 - 莫忘初衷

原来已经一个月了,想当初充满着犹豫要不要开赛,开赛後又想着会不会断赛,深知真的断赛肯定会後悔,庆幸挺...