快速排序实现 JavaScript-解网

问：

我正在尝试实现快速排序。我编写了返回数组的分区函数，其中第一个元素 - 小于枢轴的元素数，第二个元素 - 其余元素的数量。

我运行了一些测试，但我一直得到无限的递归。不知何故，数组只更改一次，仅此而已。

我尝试了一个多星期:(

const readline = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let c, arrSize;
let flagE = false;
let flagG = false;
let flagN = false;

function partition(arr, l, r, pivot){
  let E, G, pointerE, pointerG;
  let N = arr[l];
  while (l <= r){
    if (N > pivot & !flagG){
      G = N;
      pointerG = l;
      flagG = true;
    } else if (N === pivot & !flagE){
      E = N;
      pointerE = l;
      flagE = true;
      if (flagG) {
        arr[l] = G;
        arr[pointerG] = N;
        pointerE = pointerG;
        pointerG++;
      }
    }
     else if (N < pivot & !E & !G){
      flagN = true;
    } 
    else if (N > pivot & flagG) {
      N = arr[l];
    } else if (N < pivot) {
        if (E & G) {
            arr[l] = G;
            arr[pointerG] = E;
            arr[pointerE] = N;
            pointerG++;
            pointerE++;
        } else if (G){
            arr[l] = G;
            arr[pointerG] = N;
            pointerG++;
        } else if (E){
            arr[l] = E;
            arr[pointerE] = N;
            pointerE++;
        }
    }
    l++;
    N = arr[l];
    G = arr[pointerG];
    E = arr[pointerE];
  }

  if (!pointerE & !pointerG & !flagN) {
      return([0, arrSize]);
  } else if (!pointerE & !pointerG & flagN){
      return([arrSize - 1, 0]);
  } else if (pointerE){
      return ([pointerE, r - pointerE]);
  } else if (pointerG & !pointerE) {
      return ([pointerG, arrSize - pointerG]);
  } else {
      return ([pointerG, arrSize - pointerG]);
  }
}

function quickSort(arr, l, r) {
  if (l < r) {
    let x = Math.floor((l + r) / 2);
    let [p, j] = partition(arr, l, r, arr[x]);
    quickSort(arr, l, p);
    quickSort(arr, p + 1, r);
  }
}


readline.on('line', input => {
  let arr;
  if (!c) {
    arrSize = Number(input);
    c = 1;
  } else if (c === 1){
    arr = input.split(' ').map(Number);
    c++;
  }
  if (c === 2){
    quickSort(arr, 0, arrSize - 1);
    console.log(arr.join(' '));
    readline.close()
  }
})

JavaScript 数组快速排序

const readline = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let c, arrSize;

function partition(arr, l, r, pivot) {
  let i = l - 1;

  for (let j = l; j < r; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
  return i + 1;
}

function quickSort(arr, l, r) {
  if (l < r) {
    let x = Math.floor((l + r) / 2);
    let pivot = arr[x];
    let p = partition(arr, l, r, pivot);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
  }
}

readline.on('line', input => {
  if (!c) {
    arrSize = Number(input);
    c = 1;
  } else if (c === 1) {
    let arr = input.split(' ').map(Number);
    quickSort(arr, 0, arrSize - 1);
    console.log(arr.join(' '));
    readline.close();
  }
});

快速排序实现 JavaScript

Quick sort implementation JavaScript

评论

评论