三向切分的快速排序代码

三向切分的快速排序是一种优化版的快速排序算法，它特别适用于有大量重复元素的数据集。基本思想将数组分为三部分：小于、等于和大于当前基准值的部分。以下是基于JavaScript的一个简单实现：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let lt = left,
        i = left + 1,
        gt = right;
    
    // 选择中间位置的元素作为基准
    const pivotValue = arr[left];
  
    while (i <= gt) {
      // 如果元素比基准小，移动到左侧
      if (arr[i] < pivotValue) {
        [arr[lt], arr[i]] = [arr[i], arr[lt]];
        lt++;
        i++;
      }
      // 如果元素等于基准，保持不变，继续查找下一个
      else if (arr[i] === pivotValue) {
        i++;
      }
      // 如果元素比基准大，移动到右侧
      else {
        [arr[i], arr[gt]] = [arr[gt], arr[i]];
        gt--;
      }
    }

    // 递归地对小于和大于基准的两部分进行排序
    quickSort(arr, left, lt - 1);
    quickSort(arr, gt + 1, right);
  }
  return arr;
}

// 使用示例
const array = [5, 3, 8, 2, 6, 3, 9, 2, 7, 3];
console.log(quickSort(array));  // 输出排序后的数组