尝试转换我的 Quicksort 函数，使其可以处理对象数组并按对象内的值排序

Question

我目前正在尝试修改我的 Quicksort 函数，以便在存在具有相同排序目标但不同 ID 的对象数组时测试现实生活中的问题。

下面是我的两个不同的代码，其中枢轴选择机制彼此不同。

//first Code


function quickSort(array) {
  if (array.length === 1) return array; // base case
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];

  for(let el of array) {
      if (el.num < pivot.num) {
          leftArr.push(el); 
      } else {
          rightArr.push(el); 
      }
  }
  console.log(rightArr);
  console.log(leftArr);

  if (leftArr.length > 0 && rightArr.length > 0) {
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)] 
  } else if (leftArr.length > 0) {
    return [...quickSort(leftArr), pivot]
  } else {
    return [pivot, ...quickSort(rightArr)] 
  }
}

// second Code 

function quickSort2(arr) {
  if (!arr.length) {
    return arr;
  }
  let pivotIdx = Math.floor(Math.random() * (arr.length));
  let pivot = arr[pivotIdx];
  let head = [];
  let tail = [];
  let exceptPivot = arr.slice(0, pivotIdx).concat(arr.slice(pivotIdx + 1));
  for (let el of exceptPivot) {
    if (el.num <= pivot.num) {
      head.push(el)
    } else {
      tail.push(el)
    }
  }
  // return quickSort1(head).concat([pivot].concat(quickSort1(tail)));
  return [...quickSort1(head), pivot, ...quickSort1(tail)];
};

下面是测试：

let test = [
  {id: 4, num: 21},
  {id: 7, num: 22},
  {id: 12, num: 24},
  {id: 5, num: 100},
  {id: 6, num: 100},
  {id: 32, num: 14},
  {id: 19, num: 15},
  {id: 23, num: 16},
  {id: 1, num: 15},
  {id: 42, num: 100},
  {id: 56, num: 100},
  {id: 74, num: 100}
]

对于第一个代码，我得到了很多堆栈作为结果。最后根本不排序。对于第二个代码，我只得到数组结果。

你能指出我没有考虑到的逻辑和代码中的错误吗？提前谢谢你。

Answer 1

对于第一个代码，您的代码生成 infinite-loop 因为您没有考虑 el.num === pivot.num 时会发生什么.例如，

array = [
  {id: 4, num: 21},
  {id: 7, num: 22},
  {id: 12, num: 24},
  {id: 19, num: 15},
  {id: 23, num: 16},
  {id: 1, num: 15}
]

会永远else-logic。

else {
    return [pivot, ...quickSort(rightArr)] 
}

现在，解决方案很简单，检查 2 元素的 num 键何时相等。例如：

function quickSort(array) {
  if (array.length <= 1) return array; // note that array.length === 0 is also base case
  
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];
  let sameArr = []; // to save elements with same num value
  for(let el of array) {
      if (el.num < pivot.num) {
          leftArr.push(el); 
      } else if(el.num > pivot.num) {
          rightArr.push(el); 
      } else {
          sameArr.push(el);
      }
  }

  return [...quickSort(leftArr), ...sameArr, ...quickSort(rightArr)]
}

但是当 2 个元素具有相同的 num-value 但不同的 id-value 时会发生什么？那要看你的use-case，哪一个有更高的优先级？ num 或 id?

如果要先根据id-value排序，然后num-value second:

function quickSort(array) {
  if (array.length <= 1) return array; // base case
  
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];
  let sameArr = [];
  for(let el of array) {
      if (el.id < pivot.id) {
          leftArr.push(el); 
      } else if(el.id > pivot.id) {
          rightArr.push(el); 
      } else {
        if (el.num < pivot.num) {
          leftArr.push(el);
        } else if (el.num > pivot.num) {
          rightArr.push(el);
        } else {
          sameArr.push(el);
        }
      }
  }

  return [...quickSort(leftArr), ...sameArr, ...quickSort(rightArr)]
}

如果要先根据num-value排序，然后id-value second:

function quickSort(array) {
  if (array.length <= 1) return array; // base case
  
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];
  let sameArr = [];
  for(let el of array) {
      if (el.num < pivot.num) {
          leftArr.push(el); 
      } else if(el.num > pivot.num) {
          rightArr.push(el); 
      } else {
        if (el.id < pivot.id) {
          leftArr.push(el);
        } else if (el.id > pivot.id) {
          rightArr.push(el);
        } else {
          sameArr.push(el);
        }
      }
  }

  return [...quickSort(leftArr), ...sameArr, ...quickSort(rightArr)]
}

当有很多对象键要比较时，您可以通过创建一个额外的优先级数组并比较其键优先级的元素 in-order 来进一步简化此操作。

尝试转换我的 Quicksort 函数，使其可以处理对象数组并按对象内的值排序

Trying to convert my Quicksort function such that it can process array of objects and sort by the value inside the object

javascript

algorithm

quicksort