快速排序

对于子数组nums[left…right],我们将nums[left]排到正确的位置上

每次排好一个元素,然后以这个元素作为分割,递归解决子问题

双指针法

• 对于右指针向左寻找第一个小于等于nums[left]的元素
• 对于左指针向右寻找第一个大于nums[left]的元素
• 将两个指针所指向的元素进行交换

注意到左指针自始至终满足小于等于nums[left] ,也就是说当指针相遇l=r时,都满足nums[left…l] ≤ nums[left],我们可以让nums[left]和nums[l]交换,也就排好nums[left]这个元素,然后递归处理子数组nums[left…l-1]和nums[l+1,right]

为什么是右指针先移动?

确保了指针相遇时指针以及指针左侧的元素都小于nums[left]

• 如果右指针向左移动遇到了左指针,左指针再次之前必定是小于等于nums[left] 的
• 如果左指针向右移动遇到了右指针,右指针再次之前必定是小于等于nums[left] 的

void quickSort(vector<int>& nums, int left, int right) {
      if (left >= right) return ;
      swap(nums[(left+right)/2], nums[left]);
      int pivot = nums[left];
      int l = left, r = right;
      while (l < r) {
          while (l<r && nums[r]>pivot) r--;
          while (l<r && nums[l]<=pivot) l++; 
          swap(nums[l], nums[r]);
      }
      swap(nums[l], nums[left]);
      quickSort(nums, left, l-1);
      quickSort(nums, l+1, right);
  }

挖坑法

先取出nums[left]保留到临时变量pivot上,空位在左指针上,然后每一轮:

• 从右侧开始寻找小于pivot的元素,将其移动到左指针空位上,现在空位在右指针上.
• 从左侧开始寻找大于pivot的元素,将其移动到右指针空位上,现在空位又回到左指针上.

最后左右指针相遇,将pivot移动到空位l上

为什么右指针先移动?

因为空位最开始在左边