快速、归并、堆、希尔

快速排序（Quick Sort）：

• 思想：快速排序的核心操作是“哨兵划分”。选取一个基准元素作为哨兵，将数组分为比基准元素小和比基准元素大的两个部分，对这两个部分分别进行快速排序，重复进行直到整个数组排序完成。

• 不稳定排序

• 算法流程：

  1. 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
  2. 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
  3. 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

• 图解：

• 代码：

  /* 哨兵划分 */
  func (q *quickSort) partition(nums []int, left, right int) int {
      // 以 nums[left] 为基准数
      i, j := left, right
      for i < j {
          for i < j && nums[j] >= nums[left] {
              j-- // 从右向左找首个小于基准数的元素
          }
          for i < j && nums[i] <= nums[left] {
              i++ // 从左向右找首个大于基准数的元素
          }
          // 元素交换
          nums[i], nums[j] = nums[j], nums[i]
      }
      // 将基准数交换至两子数组的分界线
      nums[i], nums[left] = nums[left], nums[i]
      return i // 返回基准数的索引
  }
  
  /* 快速排序 */
  func (q *quickSort) quickSort(nums []int, left, right int) {
      // 子数组长度为 1 时终止递归
      if left >= right {
          return
      }
      // 哨兵划分
      pivot := q.partition(nums, left, right)
      // 递归左子数组、右子数组
      q.quickSort(nums, left, pivot-1)
      q.quickSort(nums, pivot+1, right)
  }