使用合并排序定位特定属性

Question

在我的 javascript 代码中实现了归并排序算法。

我想知道如何在调用 mergeSort(array); 之类的合并排序时针对特定属性（如 date、title、name 等）在数组中进行排序。

function mergeSort(arr){
    var len = arr.length;
    if(len <2)
        return arr;
    var mid = Math.floor(len/2),
        left = arr.slice(0,mid),
        right =arr.slice(mid);

    return merge(mergeSort(left),mergeSort(right));
}

function merge(left, right){
    var result = [],
        lLen = left.length,
        rLen = right.length,
        l = 0,
        r = 0;
    while(l < lLen && r < rLen){
        if(left[l] < right[r]){
            result.push(left[l++]);
        }
        else{
            result.push(right[r++]);
        }
    }  

    return result.concat(left.slice(l)).concat(right.slice(r));
}

在排序选项方法中使用它。我想要的是打印一个排序列表。列表的排序方式将由用户选择的排序选项定义。

function sortConfig(array, sortOption){
 if(sortOption == 'title') mergeSort(array.Title);
 //..etc
}

Answer 1

为简洁起见，这些示例展示了如何根据具有字符串值的属性对对象数组进行排序。您很可能需要创建一些额外的逻辑来处理不同类型的属性。

1. Array.sort()

您可以使用 Array.sort() 方法

Fiddle Example

myThings = [
  { alpha: 'a' },
  { alpha: 'x' },
  { alpha: 'p' },
  { alpha: 'orange' },
  { alpha: 'c' },
  { alpha: 'w' }
];

myThings.sort(function(a, b) {
  var alphaA = a.alpha.toUpperCase();
  var alphaB = b.alpha.toUpperCase();
  if (alphaA < alphaB) return -1;
  if (alphaA > alphaB) return 1;
  return 0;
});

console.log(myThings);

2。或者，比较数组项属性值而不是数组项值

Fiddle Example

function mergeSort(arr, prop) {
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left, prop), mergeSort(right, prop), prop);
}

function merge(left, right, prop) {
    var result = [];

    while (left.length && right.length) {
        if (left[0][prop] <= right[0][prop]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

myThings = [
  { alpha: 'a' },
  { alpha: 'x' },
  { alpha: 'p' },
  { alpha: 'orange' },
  { alpha: 'c' },
  { alpha: 'w' }
];

console.log(mergeSort(myThings, 'alpha'));

Answer 2

要使用可选参数实现行为，您可以按以下方式进行：

function mergeSort(arr, compare = (item => item))

当运行合并

时，这会将比较函数设置为项目本身

然后我们更新 merge 和 mergeSort 本身的调用，它们现在都获得比较参数

return merge(mergeSort(left, compare), mergeSort(right, compare), compare);

当然还有合并函数本身的声明

function merge(left, right, compare)

然后在比较时调用比较函数，如下所示：

if (compare(left[l]) < compare(right[r]))

这让您可以选择在调用 mergeSort 函数时是否要给出参数，例如：

console.log(mergeSort(nrs).join(','));
console.log(mergeSort(nrs, n => -n).join(','));

console.log(mergeSort(arr, i => i.id));
console.log(mergeSort(arr, i => i.title));

function mergeSort(arr, compare = (item => item)) {
  var len = arr.length;
  if (len < 2)
    return arr;
  var mid = Math.floor(len / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid);

  return merge(mergeSort(left, compare), mergeSort(right, compare), compare);
}

function merge(left, right, compare) {
  var result = [],
    lLen = left.length,
    rLen = right.length,
    l = 0,
    r = 0;
  while (l < lLen && r < rLen) {
    if (compare(left[l]) < compare(right[r])) {
      result.push(left[l++]);
    } else {
      result.push(right[r++]);
    }
  }

  return result.concat(left.slice(l)).concat(right.slice(r));
}
var arr = [{
  title: 'test 5',
  id: 4
}, {
  title: 'test',
  id: 0
}, {
  title: 'test 3',
  id: 2
}, {
  title: 'test 4',
  id: 3
}];
var nrs = [5, 3, 7, 156, 15, 6, 17, 9];

// and call like
console.log(mergeSort(nrs).join(','));
console.log(mergeSort(nrs, n => -n).join(','));

// or like
console.log(mergeSort(arr, i => i.id));
console.log(mergeSort(arr, i => i.title));

使用合并排序定位特定属性

Target specific attributes with merge sort

javascript

sorting

mergesort