【数组】快速排序 - 《leetcode算法题》

原链接：https://leetcode-cn.com/problems/sort-an-array/

题目：给你一个整数数组 nums，请你将该数组升序排列。

示例1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

解法：快速排序
每次我们选择一个参照数，然后将数组中小于这个参照数的数放在其左边，大于参照数的数放在其右边。当然，这样放置以后参考数自身也在合适的位置了。

先简单选择第一个数作为我们的参考数。
定义两个指针i和j，分别指向除了参考数之外的第一个和最后一个元素。
对i指针从左往右扫描，直到碰到第一个比5大的数停下来。可以看到，9是大于5的，所以i在9的位置停下来。

类似的，对 j 指针从右往左扫描，直到碰到第一个比 5 小的数停下来，我们会在 4 这个位置停下来。最后，现在 i 指向的数比目标大，j 指向的数比目标小，那么我们把 i 和 j 交换一下。交换以后，i 指针左边的都比目标小，j 指针右边的都比目标大了。

继续上述的操作，这一次 i，j 会在 7 和 3 停下来并交换。

继续上述过程，这次挪动 i 的时候，我们发现 i 和 j 重合了。

现在我们重新来观察图中格子的颜色，绿色部分都是比目标小的，红色都是比目标大的！这时，我们最后交换一下目标数和 i-1 指向的数，就变成了：

可以看到，我们已经达到了原先的要求，5 在其应在的位置，且比他小的都在左边，比他大的都在右边。

刚才 i 和 j 重合的时候，指向的位置比参考数要大。那如果是 j 指针向左移动和 i 重合，有可能会导致重合指向的位置比参照数要小的情况。这种情况下，我们显然不应该再交换 a[0] 和 a[i-1] 了，而应该是 a[0] 和 a[i]，即：

如果重合位置大于参考数，交换 a[i-1] 和 a[0]。

如果重合位置小于等于参考数，交换 a[i] 和 a[0]。

/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
  const pivot = (nums,l,r) => {
      if(l >= r)return;
      let mid = Math.round(Math.random() * (r - l)) + l;
      [nums[l],nums[mid]] = [nums[mid],nums[l]];
      let x = nums[l];
      let i = l + 1, j = r;
      while(i < j){
          while(i < j && nums[i] <= x)i++;
          while(i < j && nums[j] >= x)j--;
          if(i===j)break;
          [nums[i],nums[j]] = [nums[j],nums[i]];
      }
      if(nums[i] <= x){
          [nums[l],nums[i]] = [nums[i],nums[l]];
      }else{
          [nums[l],nums[i-1]] = [nums[i-1],nums[l]];
          i-=1;
      }
      pivot(nums, i+1, r)
      pivot(nums, l, i-1)
  }
  pivot(nums,0,nums.length - 1);
  return nums;
};

降序排序：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 var quickSort = function(nums){
    var pivot = (nums,l,r) => {
        if(l >= r)return;
        var mid = Math.round(Math.random() * (r - l) + l);
        [nums[l],nums[mid]] = [nums[mid],nums[l]];
        var x = nums[l];
        var i = l+1,j=r;
        while(i < j){
            while(i < j && nums[i] >= x)i++;
            while(i < j && nums[j] <= x)j--;
            if(i===j)break;
            [nums[i],nums[j]] = [nums[j],nums[i]];
        }
        if(nums[i] < x){
            [nums[i-1],nums[l]] = [nums[l], nums[i-1]];
            i -= 1;
        }else{
            [nums[i],nums[l]] = [nums[l], nums[i]];
        }
        pivot(nums,l,i-1);
        pivot(nums,i+1,r);
    }
    pivot(nums,0,nums.length-1);
    return nums;
}