算法随笔 — 排序算法 — 快速排序

r囧r小猫 2022-10-09 12:07 294阅读 0赞

# 快速排序实现原理 #

在不同的实现方法中，按照交换值的方法可以分为 `赋值` 和 `两数值交换`，这个现在理解不了没关系，先带着这个观点继续往后看

## 普通快排 ##

以升序为例，实现步骤如下图所示  
![快排1实现步骤][1]  
![快排1原理][1 1]

function quick_sort_v1(arr: number[], l: number, r: number) { 
      if (l >= r) return
      let x = l, y = r, base = arr[l] // 选择操作区间第一位作为基准值
      while(x < y) { 
        while(x < y && arr[y] > base) y--
        if (x < y) arr[x++] = arr[y]
    	while(x < y && arr[x] <= base) x++
    	if (x < y) arr[y--] = arr[x]
      }
      arr[x] = base
      // 此时数组已被基准值分为大小两部分，接着对其进行递归操作
      quick_sort_v1(arr, l, x - 1)
      quick_sort_v1(arr, x + 1, r)
    }

## 单边递归快排 ##

从上面的实现方法可以看到，每次操作需要进行两次递归操作，通过单边递归我们可以将递归操作减少至1次，从而减少空间的使用

![单边递归原理][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]

function quick_sort_v2(arr: number[], l: number, r: number) { 
      let x: number, y: number, base: number
      while(l < r) { 
    	x = l
    	y = r
    	base = arr[l]
    	while(x < y) { 
    	  while(x < y && arr[y] > base) y--
    	  if (x < y) arr[x++] = arr[y]
    	  while(x < y && arr[x] <= base) x++
    	  if (x < y) arr[y--] = arr[x]
    	}
    	arr[x] = base
    	quick_sort_v2(arr, x + 1, r)
    	r = x - 1
      }
    }

从以上代码可以看出，原来需要的两次递归操作现在只要一次就可以了

**总结一下**，以上两种方法，在交换值时是直接赋值的，这意味着在程序运行时，数组是缺了一个元素的，这就意味着**阈值**(或者说基准值)不能随便选，只能取操作区间的头部或者尾部

以上两段代码的基准值选择都是选择了操作空间的第一个

如果随机选阈值，最后极可能会出现“吞数字”的情况，如下图所示  
![吞数字][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 1]

## 分区快排 ##

分区快排结合了快排和插入排序的优点

从上面介绍的两种快排方法来看，最终运行的效率取决于中间值选得好不好(看脸)  
 快 排 时 间 复 杂 度 = \{ O ( n l o g n ) 一般 O ( l o g n ) 理想 O ( n 2 ) 最差 快排时间复杂度=\\begin\{cases\}O(nlogn) & \\text\{一般\} \\\\ O(logn) & \\text\{理想\}\\\\ O(n^2) & \\text\{最差\} \\end\{cases\} 快排时间复杂度=⎩⎪⎨⎪⎧O(nlogn)O(logn)O(n2)一般理想最差  
而插入排序的时间复杂度如下  
 插 入 排 序 时 间 复 杂 度 = \{ O ( n 2 ) 一般 O ( n ) 相对有序 插入排序时间复杂度=\\begin\{cases\} O(n^2) & \\text\{一般\} \\\\ O(n) & \\text\{相对有序\} \\end\{cases\} 插入排序时间复杂度=\{ O(n2)O(n)一般相对有序  
因此，我们可以结合两种排序方法的优点，对原数组进行分区，以16为步长进行划分，多于16时使用快排使数组相对有序，然后再用插入排序进行收尾

当初始的数组大小不大于16位时，直接使用插入排序

**为什么分区大小选16？**

在计算机中，CPU的运算速度是最快的，这里选16位是为了命中CPU的内存，使得程序运行时可以直接在CPU内部完成

**基准值的选择**

在分区快排中，使用交换的方式进行值交换，因此不会存在“吞数字”的情况，所以为了尽量选择一个较好的基准值，对原数组的头尾和中部进行判断，选择值在中间的那个数作为基准值

![分区快排原理][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 2]

// 分区大小
    const threshold = 16
    // 基准值选择
    const median(a: number, b: number, c: number) { 
      if (a > b) [a, b] = [b, a]
      if (a > c) [a, c] = [c, a]
      if (b > c) [b, c] = [c, b]
      return b
    }
    // 快排
    function __quick_sort(arr: number[], l: number, r: number) { 
      while(l - r > threshold) { 
    	let x = l, y = r, base = median(arr[l], arr[r], arr[(l + r) >> 1])
        do { 
          while(x < y && arr[y] > base) y--
          while(x < y && arr[x] <= base) x++
          if (x <= y) { 
    		[arr[x], arr[y]] = [arr[y], arr[x]]
    		x++
    		y--
    	  }
    	} while (x <= y)
    	__quick_sort(arr, x, r)
    	r = y
      }
    }
    // 插入排序
    function __insert_sort(arr: number[], l: number, r: number) { 
      // 找到最小值，并将其移到首位
      let ind = l	// 最小值的下标
      for (let i = l + 1; i < arr.length; i++) { 
    	if (arr[i] < arr[ind]) ind = i
      }
      while(ind > l) { 
    	[arr[ind], arr[ind - 1]] = [arr[ind - 1], arr[ind]]
    	ind--
      }
      // 插入排序
      let j: number
      for (let i = l + 2; i <= r; i++) { 
    	j = i
    	while(arr[j] < arr[j - 1]) { 
    	  [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
    	  j--
    	}
      }
    }
    
    function quick_sort_v3(arr: number[], l: number, r: number) { 
      __quick_sort(arr, l, r)
      __insert_sort(arr, l, r)
    }

**注意！注意！注意！**

快排之后数组只是变得相对有序，即使是处理过的区域也不能保证就是有序的

`__quick_sort()` 处理后的结果有可能如下图所示  
![\_\_quick\_sort()结果][quick_sort]  
因此，此方法的快排的作用是使得数组整体相对有序，便于插入排序进行操作

--------------------

# 相关习题 #

> ## leetCode 912 排序数组 ##

这道题就是最简单的快排应用，这里直接用分区快排，这里就不上代码了，具体代码参考上文  
![leetCode912结果1][leetCode912_1]  
![leetCode912结果2][leetCode912_2]  
![leetCode912结果3][leetCode912_3]

> ## 剑指Offer 21 调整数组顺序使奇数位于偶数前面 ##

这道题的解法可以参考分区快排的数字交换方法

function exchange(nums: number[]): number[] { 
      let x = 0, y = nums.length - 1
      while (y > x) { 
        do { 
          while (x < y && nums[x] % 2 === 1) x++
          while (x < y && nums[y] % 2 === 0) y--
          if (x < y) { 
            [nums[x], nums[y]] = [nums[y], nums[x]]
            x++
            y--
          }
        } while (x < y)
      }
      return nums
    }

![leetCode剑指offer21结果][leetCode_offer21]

> ## leetCode 148 链表排序 ##

这里可以定义两个链表，链表1用来放小值，链表2用来放大值

最后再使链表1的尾部连到链表2的头部，返回链表1的头部即可

此处基准值的选择是遍历链表获得最大最小值，然后取其平均作为基准值

function sortList(head: ListNode | null): ListNode | null { 
      if (!head) return null
      if (!head.next) return head
      let min = head.val, max = head.val, avg: number
      let p: ListNode | null, h1 = null, h2 = null, q = null
      p = head
      // 找到最大和最小值同时获得其平均值
      while (p) { 
        min = Math.min(min, p.val)
        max = Math.max(max, p.val)
        p = p.next
      }
      if (min === max) return head
      avg = (min + max) >> 1
      // 遍历链表，小数接链表1，大数接链表2
      p = head
      while (p) { 
        q = p.next
        if (p.val <= avg) { 
          p.next = h1
          h1 = p
        } else { 
          p.next = h2
          h2 = p
        }
        p = q
      }
      h1 = sortList(h1)
      h2 = sortList(h2)
      // 至此两条链表已是有序链表，接下来使p指针指向链表1的头并连接链表2
      p = h1
      while (p?.next) p = p!.next
      p!.next = h2
      return h1
    }

这里定义的两个链表也可以用虚拟头，具体操作请参考[链表篇][Link 1]  
![leetCode148结果][leetCode148]

> ## leetCode 75 颜色分类 ##

![leetCode75题目][leetCode75]  
这道题是快排的三路分类变种，由题可得我们可以直接将基准值设置为1

function three_partition(arr: number[], l: number, r: number, mid: number) { 
      if (l >= r) return
      let x = 0, y = r, i = l
      while (i <= y) { 
        if (arr[i] === mid) i++
        else if (arr[i] < mid) { 
          [arr[x], arr[i]] = [arr[i], arr[x]]
          x++
          i++
        } else if (arr[i] > mid) { 
          [arr[y], arr[i]] = [arr[i], arr[y]]
          y--
        }
      }
    }
    function sortColors(nums: number[]): void { 
      three_partition(nums, 0, nums.length - 1, 1)
    }

注意这里和大值交换的时候并没有执行 i++，这是因为这个交换只能保证在原来大值的位置上的数字没错，但是交换后的`位置i`上的数字并不能保证就是符合要求的，因此需要在下一次遍历再判断  
![leetCode75结果][leetCode75 1]

> ## 面试题17.14 最小k个数 ##

这个在堆排序那一章已经做过了，这里使用快排对数组进行排序然后再取前k个数字

![面试题17.14结果][17.14]

> ## leetCode 95 不同的二叉搜索树II ##

![leetCode95题目][leetCode95]  
首先需要定义一个函数，通过输入节点区间返回树的结构

对于每一个根，首先找到其左右子树，然后用其生成一颗树，这颗树就是其中一种解法

function getTrees(l: number, r: number) { 
      if (l > r) return [null]
      const ans: Array<TreeNode | null> = []
      let leftTrees: Array<TreeNode | null>, rightTrees: Array<TreeNode | null>
      // 找到每一种情况的左子树和右子树
      for (let i = l; i <= r; i++) { 
        leftTrees = getTrees(l, i - 1)
        rightTrees = getTrees(i + 1, r)
        // 对左右子树进行排列组合
        leftTrees.forEach(leftTree => { 
          rightTrees.forEach(rightTree => { 
            ans.push(new TreeNode(i, leftTree, rightTree))
          })
        })
      }
      return ans
    }
    function generateTrees(n: number): Array<TreeNode | null> { 
      if (!n) return []
      return getTrees(1, n)
    }

![leetCode95结果][leetCode95 1]

--------------------

# 复习题 #

> ## leetCode 394 字符串解码 ##

![leetCode394题目][leetCode394]

这道题适合用栈进行解题，首先定义两个栈，一个是操作栈、另一个是行为栈

和用栈实现计算器类似，不同行为用不同的符号表示

这里用 0表示重复数字，1表示 \[ ，2表示操作字符

![leetCode394结果][leetCode394 1]

> ## leetCode 239 滑动窗口最大值 ##

![leetCode239题目][leetCode239]  
这道题比较适合用队列去解，不过这个队列有一个性质，就是队列头部必须是当前窗口的最大值

我们用下标位置来表示不同组的关系

function maxSlidingWindow(nums: number[], k: number): number[] { 
      const res: number[] = [], queue: number[] = []
      let index = 0
      while (index < nums.length) { 
        // 维护队列的长度
        if (queue.length && queue[0] + k <= index) queue.shift()
        // 维护队列的最大值，保证队列头部是窗口的最大值
        while (queue.length && nums[queue[queue.length - 1]] < nums[index]) { 
          queue.pop()
        }
        queue.push(index)
        index++
        if (index >= k) res.push(nums[queue[0]])
      }
      return res
    }

![leetCode239结果][leetCode239 1]

--------------------

# 智力发散题 #

> ## leetCode 11 盛最多水的容器 ##

![leetCode11题目][leetCode11]  
这道题使用双指针方法

矩形的面积是长×宽，这里的长是两指针的距离，宽是两指针所指柱形中最小的那个值

移动的方式是较小的指针往中间靠

function maxArea(height: number[]): number { 
      let i = 0, j = height.length - 1, ans = 0
      while (i < j) { 
        ans = Math.max(ans, (j - i) * Math.min(height[i], height[j]))
        if (height[i] < height[j]) i++
        else j--
      }
      return ans
    }

![leetCode11结果][leetCode11 1]

> ## leetCode 470 用rand7()实现rand10() ##

![leetCode470题目][leetCode470]  
先看一下如何用 rand2() 实现 rand4()  
![rand2到rand4][rand2_rand4]  
从图中可以看到，直接使用 rand2() + rand2() 得到的结果不对

因此现在的问题转化为如何使 rand2() 转化为右图的第一列

rand2() 生成的数字是 \[1, 2\]

1.  我们对其进行减1，得到的结果是 \[0, 1\]
2.  对上步结果进行乘2，就能得到 \[0, 2\]
3.  再将其和 rand2() 进行相加，得到的就是 rand4() 的结果  
     r a n d 4 = ( r a n d 2 − 1 ) × 2 + r a n d 2 rand4 = (rand2 - 1) × 2 + rand2 rand4=(rand2−1)×2\+rand2

通过 rand2 和 rand3 生成 rand6 也是同理  
![通过rand2和rand3生成rand6][rand2_rand3_rand6]  
通过观察可得  
 r x ⋅ y = ( r x − 1 ) ⋅ y + r y r\_\{x·y\}=(r\_x-1)·y+r\_y rx⋅y=(rx−1)⋅y\+ry

有了以上公式之后再回到题目，通过 rand7 生成 rand10

当只有 rand7 的时候，我们可以组合的随机数组合是  r a n d 7 ⋅ 7 rand\_\{7·7\} rand7⋅7，即 r a n d 49 rand\_\{49\} rand49

rand49 等价生成的数字分为两部分，\[1-40\] \[41-49\]，当数字在\[1-40\]中时，使其对10求余加1即所求，而\[41-49\]是等概率生成的，相当于 rand9

通过 rand7 和 rand9 组合可以得到 rand63，在 rand63 中，如果生成数字位于\[1-60\]，则返回其对10求余加1的结果；此时\[61-63\]也是等概率生成的，相当于 rand3

同理，rand7 和 rand3 又可组合成 rand21，分为 \[1-20\] 和 \[21\]，如果这时数字不幸就是21，那就只能从头开始重复以上过程了

function rand10(): number { 
      let num = 0
      while (true) { 
        num = (rand7() - 1) * 7 + rand7() // rand49() [1-40] [41-49]
        if (num <= 40) return (num % 10) + 1
        // 此时 num - 40 代表rand9()
        num = (num - 40 - 1) * 7 + rand7()  // rand63() [1-60] [61-63]
        if (num <= 60) return (num % 10) + 1
        // 此时 num - 60 代表rand3()
        num = (num - 60 - 1) * 7 + rand7()  // rand21() [1-20] [21]
        if (num <= 20) return (num % 10) + 1
      }
    }

![leetCode470结果][leetCode470 1]

--------------------

# 结语 #

终于，明天就是毕业典礼了，祝愿自己一帆风顺！

[1]: /images/20221005/c05e10be37214128b92e927f8dc81a47.png
[1 1]: /images/20221005/67b45d74dd594258b12406edfe2ea846.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]: /images/20221005/2c4731e9b9ff4a8e9d7f4c9136d7ff6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 1]: /images/20221005/b07bfdd93a2c43e789d62488f4e12bf9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 2]: /images/20221005/2367ca6460474a019563f898beff60a7.png
[quick_sort]: /images/20221005/73e00c8910284bc5aeba18c3daeddb00.png
[leetCode912_1]: /images/20221005/925cea272c6d4bc197324d31199dda75.png
[leetCode912_2]: /images/20221005/a090d7453042433daebdf3043ea70e76.png
[leetCode912_3]: /images/20221005/10766ddd0e484f4ba0bd9eb6d7fb301a.png
[leetCode_offer21]: /images/20221005/9758bec34b194016a7b5b63c9a6f5576.png
[Link 1]: https://blog.csdn.net/TM_Godspeed/article/details/114497771
[leetCode148]: /images/20221005/a1e231fd175746619d0c9ab58a812236.png
[leetCode75]: /images/20221005/f35fcb975cee4fc1a4a4619eda21b29b.png
[leetCode75 1]: /images/20221005/954f1d0e8f2042608f70a3223d2392ab.png
[17.14]: /images/20221005/40d83fd874b34d789faf7e09d24348d2.png
[leetCode95]: /images/20221005/f9f234d4b1814bb6ae4b090e68d0afc9.png
[leetCode95 1]: /images/20221005/a7d82b7f5c7c48c48b700322c85d107d.png
[leetCode394]: /images/20221005/9c733d28db234721855804da00ff9b31.png
[leetCode394 1]: /images/20221005/730b20fee4a74c6e8246f0addfd1083f.png
[leetCode239]: /images/20221005/3703a0251e18498c86ad5666bd2401c4.png
[leetCode239 1]: /images/20221005/949ec05448b44b3c981e6ff6775e2040.png
[leetCode11]: /images/20221005/2cab707db5634f2c909b525ab8e56c71.png
[leetCode11 1]: /images/20221005/d2633b3a61384d26a1df30aeef6f2a00.png
[leetCode470]: /images/20221005/5c5ce57d396e4968b06419da9967bc4c.png
[rand2_rand4]: /images/20221005/4bc4448f3bca4d69a164c3fe4def7201.png
[rand2_rand3_rand6]: /images/20221005/db3089fe05e3413e90de5e5108d90d6e.png
[leetCode470 1]: /images/20221005/e03983d7297d4fe4a8e2dd7f5be84aeb.png