js如何实现数组快速排序 3种快速排序算法实现方案分享

function quickSortLomuto(arr, low, high) {
  if (low < high) {
    let partitionIndex = partitionLomuto(arr, low, high);

    quickSortLomuto(arr, low, partitionIndex - 1);
    quickSortLomuto(arr, partitionIndex + 1, high);
  }
  return arr;
}

function partitionLomuto(arr, low, high) {
  let pivot = arr[high];
  let i = (low - 1); // Index of smaller element

  for (let j = low; j <= high - 1; j++) {
    // If current element is smaller than or equal to pivot
    if (arr[j] <= pivot) {
      i++;    // increment index of smaller element
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return (i + 1);
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 示例
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSortLomuto(arr, 0, n - 1);
console.log("排序后的数组: " + arr);

function quickSortHoare(arr, low, high) {
  if (low < high) {
    let partitionIndex = partitionHoare(arr, low, high);

    quickSortHoare(arr, low, partitionIndex);
    quickSortHoare(arr, partitionIndex + 1, high);
  }
  return arr;
}

function partitionHoare(arr, low, high) {
  let pivot = arr[low]; // 选择第一个元素作为基准
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do {
      i++;
    } while (arr[i] < pivot);

    do {
      j--;
    } while (arr[j] > pivot);

    if (i >= j) {
      return j;
    }

    swap(arr, i, j);
  }
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 示例
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSortHoare(arr, 0, n - 1);
console.log("排序后的数组: " + arr);

function quickSortRandomized(arr, low, high) {
  if (low < high) {
    let partitionIndex = randomizedPartition(arr, low, high);

    quickSortRandomized(arr, low, partitionIndex - 1);
    quickSortRandomized(arr, partitionIndex + 1, high);
  }
  return arr;
}

function randomizedPartition(arr, low, high) {
    let randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    swap(arr, randomIndex, high); // 将随机选择的元素与最后一个元素交换
    return partitionLomuto(arr, low, high); // 使用 Lomuto 分区方案
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 示例
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSortRandomized(arr, 0, n - 1);
console.log("排序后的数组: " + arr);