【第八天 - Quick Sort 介绍】

Q1. Quick Sort是什麽

• 与前天介绍的 bubble sort 一样，是一种计算排序的方法，但是此种演算法比起 bubble sort 平均所花费的时间更少

• 
  (表格来源 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html )

• 时间复杂度，越小代表效率越好，关於详细的时间复杂度，可以参考此篇文章：https://ithelp.ithome.com.tw/articles/10203082

• Quick Sort 拥有许多种变形，所以在网路上找相关文章时，有些文章 Quick Sort 方式有些微不同，但是他们整体概念基本上都是

1. 先从一串要排序的资料中，找出一个值，将他定为 Pivot
   
2. 然後比 pivot 小的放左边，比 pivot 大的放右边
   
3. 排序好一轮 pivot 的位置就会固定下来，重复第1与第2步骤，从剩下的数字选 pivot，将比较小的放左边，比较大的放右边
   

• 所以 Quick Sort 在实作上，有两个要考虑的重点
  1. 在排序上，可能会有极端状况导致效能不佳，所以 pivot 有很多选法：
     a. 每次选第一个元素
     b. 每次选最後一个元素
     c. 选择特定位置（如中位数）的元素
     d. 随机选择任意元素
     • 假设有一个序列恰好「已/接近排序完成」，此时若选择 第一个或是最後一个元素 作为 pivot，则会遇到极端情况，每次都要比较 N、N-1、N-2 .... 个数字
       • 
     • 若是能够选择中位数做为 pivot ，那麽就只要比较 N/2 与 N/2-1 的数量，类似二分搜的概念
       • 
  2. 如何将比较小的排左边，比较大的排右边，算法主要分为两种：
     • Lomuto (较易实作与理解，常被做为教材，所以网路上教学文章主要都是使用此种方法)
       • 排序方法：
         • Lomuto 的 pivot 时常选定最後一个
         • 会有两个指标指向开始
         • 
         • 指针分别：
           • j 指标专门停在比 pivot 大的位置
           • k 指标专门在 j 指标停之後(遇到比 pivot 大的值後)，停在比 pivot 小的位置
           • 当 k 与 j 指标都停止後，两者的值就会做交换
           • 
           • 
         • 你会发现，比 pivot 大的数字，逐渐被往後放，最终 pivot 左边都是比较小的，右边都是比 pivot 大的值
         • Lomuto 影片连结：https://www.youtube.com/watch?v=86WSheyr8cM
       • Hoare (效率比 Lomuto 更好一些，交换次数更少)
         • 排序方法
           • Hoare 的 pivot 时常选定中位数
           • 会有两个指标，一个指向开始，一个指向结尾
           • 
         • 指针分别：
           • k 指标逐渐往後，专门停在比 pivot 大的数字
           • j 指标逐渐往前，专门停在比 pivot 小的数字
           • 当 k 与 j 指标都停止後，两者的值就会做交换 (把大的丢到右边，把小的丢到左边)
           • 
         • Hoare 影片连结：https://www.youtube.com/watch?v=NuQYFXmLUrM

Q2. 学会 Quick Sort 可以做什麽?

• 生活中时常会需要使用到排序好的资料 (尤其是可以处理资料量相对较多的)，例如
  • 全国基测分数从低到高排序
  • 世界财富排行榜

Lab. 明天要解的题目：912. Sort an Array

• 题目连结：https://leetcode.com/problems/sort-an-array/

• 我们上次使用 bubble sort 的算法解这一题，但是发现会效率不高，会出现 Time Limit Exceeded 的情况，我们这次使用今天介绍的 Quick Sort 的方法来解这一题

• 为了避免新加入的读者需要往前翻题目，我们再将题目叙述一遍：

• 题目叙述：

  • 会有一个 nums 变数，里面储存着要排序的内容，我们要将内容由小到大进行排序
  • 

• 测资的 Input/Output：

  • 会拿到 nums 的变数，须回传排序好的资料
  • 

• 题目的条件：

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

• 看完题目你需要思考的是：

  • 使用 Quick sort 这个算法，会不会可能造成超时?
  • 有没有其他排序方法可以使用 ?