快速排序（快速选择）优化：双指针、打乱数组、随机基准元素（随机数、中间数、中位数）、三路划分三指针：求解《462. 最少移动次数使数组元素相等 II》

代码数据结构:数组技巧:双指针技巧:三指针排序:快速排序算法:快速选择算法:洗牌算法语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:TypeScript 语言:Java 数学:随机数

2022-05-19 19:03:47

快速排序（快速选择）的优化：双指针、打乱数组（Fisher–Yates shuffle 洗牌算法）、随机基准元素（随机数、中间数、中位数）、三路划分（三切分 / 三指针 / 三分查找）。求解《462. 最少移动次数使数组元素相等 II》。

快速排序，快速选择三指针三路划分解法示意图

快速排序 · 快速选择

双指针 · 基准元素：固定选取开始元素

const quickSelect= (nums, start, end, k) => { // 快速选择
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}

const quickSort = (nums, start, end) => { // 快速排序
  if (start >= end) return
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  quickSort(nums, l + 1, end)
  quickSort (nums, start, l - 1)
}

const swap = (nums, a, b) => { // 交换变量
  const t = nums[a]
  nums[a] = nums[b]
  nums[b] = t
}

双指针 · 基准元素：先打乱数组，固定选第 0 个

固定选择基准元素：当数组完全升序或降序，每次都选择最小值或最大值，快排速度减慢
为保证基准元素选取的随机性：可以先打乱数组

使用 Knuth-Durstenfeld Shuffle 的 Fisher–Yates shuffle 的洗牌算法
PHP 使用 shuffle(array &$array): bool API：从 7.1 起，由伪随机数改为梅森旋转算法（Mersenne twister）

const shuffle = nums => { // 用 Fisher-Yates shuffle 洗牌算法
  let i = nums.length
  while (i--) swap(nums, i, Math.random() * i | 0)
}

双指针 · 基准元素：随机元素

为保证基准元素选取的随机性：在 [start, end] 随机选取元素，与开始元素交换

const i = start + Math.floor(Math.random()*(end - start + 1)) // 随机选取元素
swap(nums, start, i) // 与开始元素交换

const quickSelect = (nums, start, end, k) => { // 快速选择
  swap(nums, start, start + Math.random() * (end - start + 1) | 0) // 随机选取元素与开始元素交换
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}

const quickSort = (nums, start, end) => { // 快速排序
  if (start >= end) return
  swap(nums, start, start + Math.random() * (end - start + 1) | 0) // 随机选取元素与开始元素交换
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  quickSort(nums, l + 1, end)
  quickSort(nums, start, l - 1)
}

双指针 · 基准元素：中间数

为保证基准元素选取的随机性：取中间数，与开始元素交换

swap(nums, start, start + end >> 1)

const quickSelect = (nums, start, end, k) => { // 快速选择
  swap(nums, start, start + end >> 1) // 取中间数与开始元素交换
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}

const quickSort = (nums, start, end) => { // 快速排序
  if (start >= end) return
  swap(nums, start, start + end >> 1) // 取中间数与开始元素交换
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  quickSort(nums, l + 1, end)
  quickSort(nums, start, l - 1)
}

双指针 · 基准元素：中位数

为保证基准元素选取的随机性：取中位数，与开始元素交换

基准元素是中位数时，排序最快。三数取中，最容易
三数取中法模拟中位数：最左端元素 + 最中间元素 + 最右端元素取平均值

swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0) // 三数取中法模拟中位数

const quickSelect = (nums, start, end, k) => { // 快速选择
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0) // 三数取中法模拟中位数与开始元素交换
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}

const quickSort = (nums, start, end) => { // 快速排序
  if (start >= end) return
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0) // 三数取中法模拟中位数与开始元素交换
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  quickSort(nums, l + 1, end)
  quickSort(nums, start, l - 1)
}

三路划分（三指针 / 三分查找） · 中位数

新增一个指针，选择等于基准值的元素 减少重复元素的交换

const quickSelect = (nums, start, end, k) => { // 快速选择
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
  const pivot = nums[start]
  let l = start, i = start + 1, r = end
  while (i <= r) {
    if (nums[i] > pivot) swap(nums, i, r--)
    else if (nums[i] < pivot) swap(nums, i++, l++)
    else i++
  }
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}

const quickSort = (nums, start, end) => { // 快速排序
  if (start >= end) return
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
  const q = nums[start]
  let l = start, i = start + 1, r = end
  while (i <= r) {
    if (nums[i] > q) swap(nums, i, r--)
    else if (nums[i] < q) swap(nums, i++, l++)
    else i++
  }
  quickSort(nums, l + 1, end)
  quickSort (nums, start, l - 1)
}

例题

462. 最少移动次数使数组元素相等 II

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。
在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。

答案

快速选择 · 三指针（三路划分） · 中位数

var minMoves2 = function(nums) {
  const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
  let r = 0
  for (let i = 0; i < n; i++) {
    r += Math.abs(nums[i] - median)
  }
  return r
};
const quickSelect = (nums, start, end, k) => {
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
  const pivot = nums[start]
  let l = start, i = start + 1, r = end
  while (i <= r) {
    if (nums[i] > pivot) swap(nums, i, r--)
    else if (nums[i] < pivot) swap(nums, i++, l++)
    else i++
  }
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums, a, b) => {
  const t = nums[a]
  nums[a] = nums[b]
  nums[b] = t
}

function minMoves2(nums: number[]): number {
  const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
  let r = 0
  for (let i = 0; i < n; i++) r += Math.abs(nums[i] - median)
  return r
};
const quickSelect = (nums: number[], start: number, end: number, k: number) => {
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
  const pivot = nums[start]
  let l = start, i = start + 1, r = end
  while (i <= r) {
    if (nums[i] > pivot) swap(nums, i, r--)
    else if (nums[i] < pivot) swap(nums, i++, l++)
    else i++
  }
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums: number[], a: number, b: number) => {
  const t = nums[a]
  nums[a] = nums[b]
  nums[b] = t
}

func minMoves2(nums []int) int {
  n := len(nums)
  median, r := quickSelect(nums, 0, n - 1, n >> 1), 0
  for _, num := range nums {
    r += int(math.Abs(float64(num - median)))
  }
  return r
}
func quickSelect(nums []int, start int, end int, k int) int {
  swap(nums, start, (start + end + (start + end) >> 1) / 3 | 0)
  l, i, r, pivot := start, start + 1, end, nums[start]
  for i <= r {
    if nums[i] > pivot {
      swap(nums, i, r)
      r--
    } else if nums[i] < pivot {
      swap(nums, i, l)
      i++
      l++
    } else {
      i++
    }
  }
  if l == k {
    return nums[l]
  } else if l < k {
    return quickSelect(nums, l + 1, end, k)
  } else {
    return quickSelect(nums, start, l - 1, k)
  }
}
func swap(nums []int, a int, b int) {
  nums[a], nums[b] = nums[b], nums[a]
}

class Solution {
  function minMoves2($nums) {
    $n = count($nums);
    $median = $this->quickSelect($nums, 0, $n - 1, $n >> 1);
    $r = 0;
    foreach ($nums as $num) $r += abs($num - $median);
    return $r;
  }
  function quickSelect(&$nums, $start, $end, $k) {
    $this->swap($nums, $start, ($start + $end + ($start + $end >> 1)) / 3 | 0);
    $pivot = $nums[$start];
    $l = $start;
    $i = $start + 1;
    $r = $end;
    while ($i <= $r) {
      if ($nums[$i] > $pivot) $this->swap($nums, $i, $r--);
      else if ($nums[$i] < $pivot) $this->swap($nums, $i++, $l++);
      else $i++;
    }
    if ($l === $k) return $nums[$l];
    return $l < $k ? $this->quickSelect($nums, $l + 1, $end, $k) : $this->quickSelect($nums, $start, $l - 1, $k);
  }
  function swap(&$nums, $a, $b) {
    list($nums[$a], $nums[$b]) = array($nums[$b], $nums[$a]);
  }
}

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    def swap(nums, a, b):
      nums[a], nums[b] = nums[b], nums[a]
    def quickSelect(nums, start, end, k):
      swap(nums, start, int((start + end + (start + end >> 1)) / 3))
      pivot, l, i, r = nums[start], start, start + 1, end
      while i <= r:
        if nums[i] > pivot:
          swap(nums, i, r)
          r -= 1
        elif nums[i] < pivot:
          swap(nums, i, l)
          i += 1
          l += 1
        else:
          i += 1
      if l == k: return nums[l]
      return quickSelect(nums, l + 1, end, k) if l < k else quickSelect(nums, start, l - 1, k)
    n, r = len(nums), 0
    median = quickSelect(nums, 0, n - 1, n >> 1)
    for num in nums: r += abs(num - median)
    return r

class Solution {
  public int minMoves2(int[] nums) {
    int n = nums.length;
    int median = quickSelect(nums, 0, n - 1, n >> 1);
    int r = 0;
    for (int num : nums) r += Math.abs(num - median);
    return r;
  }
  private int quickSelect(int[] nums, int start, int end, int k) {
    swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0);
    int pivot = nums[start];
    int l = start;
    int i = start + 1;
    int r = end;
    while (i <= r) {
      if (nums[i] > pivot) swap(nums, i, r--);
      else if(nums[i] < pivot) swap(nums, i++, l++);
      else i++;
    }
    if (l == k) return nums[l];
    return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
  }
  private void swap(int[] nums, int a, int b) {
    nums[a] = nums[b] + (nums[b] = nums[a]) * 0;
  }
}

快速选择 · 双指针 · 中位数

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
  const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
  let r = 0
  for (let i = 0; i < n; i++) {
    r += Math.abs(nums[i] - median)
  }
  return r
};
const quickSelect= (nums, start, end, k) => { // 快速选择
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums, a, b) => {
  const t = nums[a]
  nums[a] = nums[b]
  nums[b] = t
}

function minMoves2(nums: number[]): number {
  const n = nums.length, median = quickSelect(nums, 0, n - 1, n >> 1)
  let r = 0
  for (let i = 0; i < n; i++) r += Math.abs(nums[i] - median)
  return r
};
const quickSelect = (nums: number[], start: number, end: number, k: number) => {
  swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
  const pivot = nums[start]
  let l = start, r = end
  while (l < r) {
    while (l < r && nums[r] >= pivot) r--
    while (l < r && nums[l] <= pivot) l++
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if (l === k) return nums[l]
  return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k)
}
const swap = (nums: number[], a: number, b: number) => {
  const t = nums[a]
  nums[a] = nums[b]
  nums[b] = t
}

func minMoves2(nums []int) int {
  n := len(nums)
  median, r := quickSelect(nums, 0, n - 1, n >> 1), 0
  for _, num := range nums {
    r += int(math.Abs(float64(num - median)))
  }
  return r
}
func quickSelect(nums []int, start int, end int, k int) int {
  swap(nums, start, (start + end + (start + end) >> 1) / 3 | 0)
  l, r, pivot := start, end, nums[start]
  for l < r {
    for l < r && nums[r] >= pivot {
      r--
    }
    for l < r && nums[l] <= pivot {
      l++
    }
    swap(nums, l, r)
  }
  swap(nums, l, start)
  if l == k {
    return nums[l]
  } else if l < k {
    return quickSelect(nums, l + 1, end, k)
  } else {
    return quickSelect(nums, start, l - 1, k)
  }
}
func swap(nums []int, a int, b int) {
  nums[a], nums[b] = nums[b], nums[a]
}

class Solution {
  function minMoves2($nums) {
    $n = count($nums);
    $median = $this->quickSelect($nums, 0, $n - 1, $n >> 1);
    $r = 0;
    foreach ($nums as $num) $r += abs($num - $median);
    return $r;
  }
  function quickSelect(&$nums, $start, $end, $k) {
    $this->swap($nums, $start, ($start + $end + ($start + $end >> 1)) / 3 | 0);
    $pivot = $nums[$start];
    $l = $start;
    $r = $end;
    while ($l < $r) {
      while ($l < $r && $nums[$r] >= $pivot) $r--;
      while ($l < $r && $nums[$l] <= $pivot) $l++;
      $this->swap($nums, $l, $r);
    }
    $this->swap($nums, $l, $start);
    if ($l === $k) return $nums[$l];
    return $l < $k ? $this->quickSelect($nums, $l + 1, $end, $k) : $this->quickSelect($nums, $start, $l - 1, $k);
  }
  function swap(&$nums, $a, $b) {
    list($nums[$a], $nums[$b]) = array($nums[$b], $nums[$a]);
  }
}

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    def swap(nums, a, b):
      nums[a], nums[b] = nums[b], nums[a]
    def quickSelect(nums, start, end, k):
      swap(nums, start, int((start + end + (start + end >> 1)) / 3))
      pivot, l, r = nums[start], start, end
      while l < r:
        while l < r and nums[r] >= pivot: r -= 1
        while l < r and nums[l] <= pivot: l += 1
        swap(nums, l, r)
      swap(nums, l, start)
      if l == k: return nums[l]
      return quickSelect(nums, l + 1, end, k) if l < k else quickSelect(nums, start, l - 1, k)
    n, r = len(nums), 0
    median = quickSelect(nums, 0, n - 1, n >> 1)
    for num in nums: r += abs(num - median)
    return r

class Solution {
  public int minMoves2(int[] nums) {
    int n = nums.length;
    int median = quickSelect(nums, 0, n - 1, n >> 1);
    int r = 0;
    for (int num : nums) r += Math.abs(num - median);
    return r;
  }
  private int quickSelect(int[] nums, int start, int end, int k) {
    swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0);
    int pivot = nums[start];
    int l = start;
    int r = end;
    while (l < r) {
      while (l < r && nums[r] >= pivot) r--;
      while (l < r && nums[l] <= pivot) l++;
      swap(nums, l, r);
    }
    swap(nums, l, start);
    if (l == k) return nums[l];
    return l < k ? quickSelect(nums, l + 1, end, k) : quickSelect(nums, start, l - 1, k);
  }
  private void swap(int[] nums, int a, int b) {
    nums[a] = nums[b] + (nums[b] = nums[a]) * 0;
  }
}

排序 · 中位数

var minMoves2 = function(nums) {
  nums.sort((a, b) => a - b)
  const n = nums.length, median = n & 1 ? nums[n >> 1] : (nums[n >> 1] + nums[(n >> 1) - 1]) >> 1
  let r = 0
  for (let i = 0; i < n; i++) {
    r += Math.abs(nums[i] - median)
  }
  return r
};

function minMoves2(nums: number[]): number {
  nums.sort((a, b) => a - b)
  const n = nums.length, median = n & 1 ? nums[n >> 1] : nums[n >> 1] + nums[(n >> 1) - 1] >> 1
  let r = 0;
  for (let i = 0; i < n; i++) {
    r += Math.abs(nums[i] - median)
  }
  return r
};

func minMoves2(nums []int) int {
  sort.Ints(nums)
  n, r, median := len(nums), 0, 0
  if n & 1 == 1 {
    median = nums[n >> 1]
  } else {
    median = (nums[n >> 1] + nums[n >> 1 - 1]) >> 1
  }
  for _, num := range nums {
    r += int(math.Abs(float64(num - median)))
  }
  return r
}

class Solution {
  function minMoves2($nums) {
    usort($nums, function($a, $b) {
      return $a > $b;
    });
    $n = count($nums);
    $median = $n & 1 ? $nums[$n >> 1] : $nums[$n >> 1] + $nums[($n >> 1) - 1] >> 1;
    $r = 0;
    foreach($nums AS $num) {
      $r += abs($num - $median);
    }
    return $r;
  }
}

class Solution:
  def minMoves2(self, nums: List[int]) -> int:
    nums.sort()
    n, r = len(nums), 0
    median = nums[n >> 1] if n & 1 else nums[n >> 1] + nums[(n >> 1) - 1] >> 1
    for num in nums:
      r += abs(num - median)
    return r

class Solution {
  public int minMoves2(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int median = (n & 1) == 1 ? nums[n >> 1] : nums[n >> 1] + nums[(n >> 1) - 1] >> 1;
    int r = 0;
    for (int num : nums) {
      r += Math.abs(num - median);
    }
    return r;
  }
}

小宇

Github　力扣　 M站　全部原创，请勿转载

回溯 + 动态规划（掩码 · 状态压缩）：2 方法求解《473. 火柴拼正方形》

回溯 + 动态规划（掩码 · 状态压缩），2 方法求解《473. 火柴拼正方形》

排序、最小值，基于排序获取中位数：求解《1887. 使数组元素相等的减少操作次数》《453. 最小操作次数使数组元素相等》和《462. 最少移动次数使数组元素相等 II》

排序、最小值，基于排序获取中位数，求解《1887. 使数组元素相等的减少操作次数》《453. 最小操作次数使数组元素相等》和《462. 最少移动次数使数组元素相等 II》

5 种方法交换变量，用绝对值和求模标记，用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法：求解《442. 数组中重复的数据》

利用 5 种方法交换变量，用绝对值和求模标记，用位图、掩码、哈希集合、哈希映射、正则、排序和暴力法求解《442. 数组中重复的数据》