快速排序算法

前言

LeetCode 2545题，我的思路是用冒泡排序，但是时间开销比较大，学习了一下更高效的算法：快速排序算法。

题解链接：

• Github
• LeetCode

什么是快速排序

快速排序是一种基于分治思想的排序算法。其基本思想是选择一个基准值，然后将数组分成两部分：一部分小于基准值，一部分大于基准值。然后对这两部分进行递归排序。

快排的使用

1. 选择基准值
2. 分割数组
3. 递归排序

关键：基准值的选择

下边是快速排序的基本模板

// 以数组元素为例
class QuickSort {
  // 递归方式实现快速排序
  private void quickSort(int[] nums, int start, int end) {
    if (start < end) {
      int pivotIndex = partition(nums, start, end);
      quickSort(nums, start, pivotIndex - 1);
      quickSort(nums, privotIndex + 1, end);
    }
  }

  // 选择基准值（关键）
  private int partition(int[] nums, int start, int end) {
    // 根据需求，调用 swap 方法，最后返回基准值
  }

  // 交换数组中的元素
  private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}