2014年12月9日 D5

[nunnly]

今天是一道算法题，不使用任何javascript内置函数、方法，实现_归并排序_的算法。 流程如下：

• 等分数组
• 若数组中元素不止2项，继续等分至每个数组只有2项
• 最后一个数组可以为单项
• 对长度为2的数组排序（正序）
• 与相邻的数组做合并、对比并排序（第一项和第一项做对比，第二项和第二项做对比）
• 返回排序完成的数组

/*
 * param Array
 * return Array
 */
function sortArray(){

}
var arr = [9,8,7,6,5,4,3,2,1]
sortArray(arr);  //  => [1, 2, 3, 4, 5, 6, 7, 8, 9]

昨天有些已经完成的朋友，也可以把答案贴出来哦~

[XadillaX]

非逼我，我就不用 sort 而已。

function sortArray(arr) {
    return arr.length <= 1 ?
        arr :
        (new Array(arr.length)).join("*").split("*").reduce(function(ans) {
            return ans[2].push(ans[((ans[0].length && ans[1].length) ? (ans[0] < ans[1]) : (!!ans[0].length)) ^ 1].shift()), ans;
        }, [ sortArray(arr.splice(0, parseInt(arr.length / 2))), sortArray(arr), [] ])[2];
}

var arr = [9,8,7,6,5,4,3,2,1]
console.log(sortArray(arr));  //  => [1, 2, 3, 4, 5, 6, 7, 8, 9]

以及了。

function sortArray(a){return a.length<=1?a:new Array(a.length).join("*").split("*").reduce(function(a){return a[2].push(a[1^(a[0].length&&a[1].length?a[0]<a[1]:!!a[0].length)].shift()),a},[sortArray(a.splice(0,parseInt(a.length/2))),sortArray(a),[]])[2]}

[zhanhongtao]

@XadillaX 不使用任何javascript内置函数、方法

join/split/reduce/push 你用的太多了.

[XadillaX]

@zhanhongtao -。 - 反正不用一样能写，权当看笑话了。

[xlitter]

function sortArray(){
    var arg=arguments,
        len,mid, first=[],second=[],i,
        arr = arg[0];
    if(!arr||!(arg[0] instanceof Array)){
        return;
    }

    len = arr.length;
    if(len === 1){
        return arr;
    }
    mid = parseInt(len/2);
    for(i=0;i<mid;i++){
        first[i] = arr[i];
    }
    for(i=mid;i<len;i++){
        second[i-mid] = arr[i];
    }

    function merge(first, second){
        var result =[];
            n = first.length,
            m= second.length,
            i=0,j=0;k=0;
        while(i<n&&j<m){
            result[k++] = first[i]<second[j] ? first[i++] : second[j++];        
        }
        while(i<n){
            result[k++]=first[i++];
        }
        while(j<m){
            result[k++] = second[j++];
        }

        return result;

    }

    return merge(sortArray(first), sortArray(second));

}

var arr =  [9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1] ;

console.log(sortArray(arr));

[backsapce]

没看到群信息，补撸一发，写的烂，见笑了（好吧，没看清，还是用了push）

// TODO: merge sord javasript implement

module.exports = mergeSort;

var mergeSort =function (array) {
  if(array.length <= 1)
    return array;
  var mid = Math.floor(array.length/2);
  // console.log(array.slice(mid,array.length));

  var arrayL = mergeSort(array.slice(0,mid));

  var arrayR = mergeSort(array.slice(mid,array.length));
  return merge(arrayL,arrayR);
};

function merge(array1,array2) {
  var array = [];
  for (var i = 0,j = 0; i < array1.length && j < array2.length;) {
    if(array1[i]>array2[j]){
      array.push(array2[j]);
      j++;
    }
    else{
      array.push(array1[i]);
      i++;
    }
  }
  while (i<array1.length) {
    array.push(array1[i]);
    i++;
  }
  while (j<array2.length) {
    array.push(array2[j]);
    j++;
  }
  return array;
}
var array = [5,4,3,2,1,1];
console.time('merge sort');
console.log(mergeSort(array));
console.timeEnd('merge sort');

[ghost]

function merger( a, b ){
    var array = [], m = a.length, n = b.length;
    for(var i = 0, j = 0; i < m && j <n ){
        if(a[i] > b[j]){
            array.push(b[j]);
            ++j;
        }else{
            array.push( a[i] );
            ++i;
        }
    }
    while( i < m ){
        array.push( ret[i] );
        ++i;
    }
    while( j < n ){
        array.push( ret[j] );
        ++j;
    }
    return array;
}
function mergerSort(arr){
    if(arr.length <= 1) return arr;
    var position = Math.floor(arr.length/2);
    var a = arr.slice(0 , position);
    var b = arr.slice (position);
    return merger( mergerSort(a), mergerSort(b) );
}

[zane277]

function merger(left,right){
        let lt=0;
        let rt=0;
        let result=[];
        while(lt<left.length&&rt<right.length){
            if(left[lt]<right[rt]){
                result.push(left[lt++])
            }else{
                result.push(right[rt++])
            }
        }
        while(lt<left.length){
            result.push(left[lt++])
        }
        while(rt<right.length){
            result.push(right[rt++])
        }
        return result
    }
    function sortArr(arr){
        if(arr.length===1){
            return arr;
        }
        let left=arr.slice(0,Math.floor(arr.length/2))
        let right=arr.slice(Math.floor(arr.length/2))
        return merger(sortArr(left),sortArr(right));

    }
    console.log(sortArr([89, 32, 1, 23, 3, 32, 131, 17]))

[Gxiangyu]

function sortArray(arr) {
  if (arr.length < 2) {
    return arr;
  }

  var middle = Math.floor(arr.length / 2),
    a = arr.slice(0, middle),
    b = arr.slice(middle),
    params = merge(sortArray(a), sortArray(b));

  params.unshift(0, arr.length);
  arr.splice.apply(arr, params);

  return arr;

  function merge(a, b) {
    var result = [],
      aa = 0,
      bb = 0;

    while (aa < a.length && bb < b.length) {
      if (a[aa] < b[bb]) {
        result.push(a[aa++]);
      } else {
        result.push(b[bb++]);
      }
    }
    return result.concat(a.slice(aa)).concat(b.slice(bb));
  }
}

[weichenguang]

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1);
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (pivot > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
}
console.log(quickSort(arr))

[SummerWind-July]

function sortArray (a,b,lastA,lastB) {
            var indexA=lastA-1;
            var indexB=lastB-1;
            var indexMerged=lastB+lastA-1;
            while(indexA>=0&&indexB>=0)
            {
                if(a[indexA]>b[indexB])
                {
                    a[indexMerged]=a[indexA];
                    indexMerged--;
                    indexA--;
                }
                else
                {
                    a[indexMerged]=b[indexB];
                    indexMerged--;
                    indexB--;
                }
            }
              while(indexB>=0)
            {
                a[indexMerged]=b[indexB];
                indexMerged--;
                indexB--;
            }
            return a;
        }
console.log(sortArray([10,18,20],[3,6,11],3,3));