从头开始自定义排序方法需要比较器？

Question

我的任务是编写一个完全自定义的排序方法（不能使用

Array.sort()

），该方法采用比较器并根据所述比较器对列表进行排序。

const people = [
  {name: 'Bill', age: 30, likes: 'food'},
  {name: 'Andrew', age: 17, likes: 'games'},
  {name: 'Kyle', age: 59, likes: 'cats'},
]

function sortArr(comparator, array) {
  // code goes here
}

function exampleComparator(int1, int2) {
  if (int1 > int2) {
    return true;
  } else {
    return false;
  }
}

我必须构建的比较器的一个示例是按名称排序的比较器和按年龄排序的另一个比较器。

我会这样调用该函数：

sortArr(ageComparator, people)

，然后它会按人们的年龄对数组进行排序。

但是，我正在为排序数组而苦苦挣扎。我最初以为我可以使用内置的数组排序方法，但我的教授说这是不允许的。我不知道如何处理

sortArr

函数来利用传入的比较器，该比较器返回布尔值，然后根据该值进行排序。

我可以轻松实现类型的插入排序，但随后我陷入了如何使用比较器的困境。

有人可以指出我正确的方向吗？是否有更好的排序算法可以使这个过程变得更容易？

谢谢你。

Answer 1

仔细查看示例比较器

function exampleComparator(int1, int2) {
  if (int1 > int2) {
    return true;
  } else {
    return false;
  }
}

人们可以注意到，主要目标是有一个排序算法，其中通过比较器来评估

int1

和

int2

（或一般意义上的

object1

与

object2

）。让我们以冒泡排序算法为例：

function sortArr(inputArr) {
  let len = inputArr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (inputArr[j] > inputArr[j + 1]) { // this is where the comparison happens
        let tmp = inputArr[j];
        inputArr[j] = inputArr[j + 1];
        inputArr[j + 1] = tmp;
      }
    }
  }
}

因此我们需要传递自定义比较器并让它进行比较，例如（按年龄升序排列）

const people = [{
    name: 'Bill',
    age: 30,
    likes: 'food'
  },
  {
    name: 'Andrew',
    age: 17,
    likes: 'games'
  },
  {
    name: 'Kyle',
    age: 59,
    likes: 'cats'
  },
]

function ageComparator(a, b) {
  if (a.age > b.age) {
    return true;
  } else {
    return false;
  }
}

function sortArr(comparator, inputArr) {
  let len = inputArr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (comparator(inputArr[j], inputArr[j + 1])) {
        let tmp = inputArr[j];
        inputArr[j] = inputArr[j + 1];
        inputArr[j + 1] = tmp;
      }
    }
  }
}

sortArr(ageComparator, people)
console.log(people)

Answer 2

通过使用 O(n^2)，在这种情况下使用

sort()

方法不是一个不错的选择吗？！