如何在不使用排序方法(排序)或排序算法(冒泡排序、快速排序)的情況下對兩個已排序數組進行排序

新人舞會

我在面試中被問到,我的回答與此類似,由於最後的循環而錯誤。

const newSortArrays = (arr1, arr2) => {
     let output = [];
     while (arr1.length && arr2.length) {
        if (arr1[0] < arr2[0]) 
         output.push(arr1[0] < arr2[0] ? arr1.shift() : arr2.shift())
     }
     return [...output, ...arr1, ...arr2]
 }

尼古拉斯·凱里

你在說什麼——“排序”兩個本身已經排序的數組——被稱為合併這就是你這樣做的方式:

function merge( left = [] , right = [] )  {
  const merged = new Array( left.length + right.length );

  let i = 0 ;
  let j = 0 ;
  let k = 0 ;

  // while both lists have items
  while ( i < left.length && j < right.length ) {
    const x = left[i];
    const y = right[j];

    if ( x <= y ) {
      merged[k++] = x;
      ++i;
    } else {
      merged[k++] = y;
      ++j;
    }

  }

  // if the left list still has items, take them
  while ( i < left.length ) {
    merged[k++] = left[ i++ ];
  }

  // if the right list still has items, take them
  while ( j < right.length ) {
    merged[k++] = right[ j++ ];
  }

  return merged;
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章