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

• 题目叙述：

  • 题目连结：https://leetcode.com/problems/sort-an-array/
  • 会有一个 nums 变数，里面储存着要排序的内容，我们要将内容由小到大进行排序

  

  • 测资的 Input/Output：
  • 会拿到 nums 的变数，须回传排序好的资料
    

• 题目的条件：

  • 可能会有 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。

2. 接着用回圈将 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。
   

3. 回圈结束，此时 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
   

   

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

   while(i < right and j < right)
   

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

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

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

   

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

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

   

7. 最後，设置递回函式的终止条件

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