老师，我想问一下我这样实现好吗？

/**
 * @description 选择排序算法
 * @author 星光
 */

class SelectionSort {
  private constructor() {}

  static sort<T>(arr: T[], fn?: (item1: T, item2: T) => number): void {
    let minIndex: number
    for (let i = 0, len = arr.length; i < len; i++) {
      minIndex = i
      for (let j = i; j < len; j++) {
        // 自己实现不可比较的逻辑函数
        if (fn) {
          minIndex = fn(arr[i], arr[j])
          continue
        }

        if (arr[i] > arr[j]) {
          minIndex = j
        }
      }

      SelectionSort.swap(arr, i, minIndex)
    }
  }

  private static swap<T>(arr: T[], i: number, j: number): void {
    const mid = arr[j]
    arr[j] = arr[i]
    arr[i] = mid
  }
}

export default SelectionSort

我是使用Typescript来学习这一门课课程的，因为Typescript虽然有泛型约束，但是它的类的功能还是没有java的好，所以我只能这样，当然不能比较的类型，让使用的人来就行定制，就是一个函数回调来实现。

老师你觉得这样实现好吗？

星光荡开宇宙 2023-03-10

源自：排序基础 1-3 使用带约束的泛型

收起

1回答

liuyubobobo 2023-03-11 07:09:20

首先声明一下，我没有接触过 Typescript，所以我只能从“大致的实现思路”的角度做一个简单的点评，而不能提供一个“更好的” Typescript 版本的实现。对于某一个特定语言对于一个算法的具体实现，怎么做是更好的，确实有可能因为语言本身的特性原因有很大的区别，所以应该在具体的这个语言的社区中去讨论，而非在“算法和数据结构”的相关社区中讨论。

这本身其实也是学习算法和数据结构的一个很重要的 mindset，你应该更多的聚焦于算法和数据结构背后的逻辑和原理是什么，而非具体某一个语言如何“最优”的实现某一个算法或者数据结构。不是说后者不重要，而是前者是基础，是算法和数据结构这门课程的学习目标（不单指我的这个课程，所有大学设立的算法和数据结构课程都是如此，无论国内外。）。后者是进一步学习的一个方向（偏软件工程，设计模式，而非算法）。

举一个简单的例子，在大多数语言的标准库中，对于大多数数据结构的实现，都要引入“迭代器”这样一个概念。但你会发现，绝大多数的算法和数据结构的教材中，都不会介绍这一概念（包括大名鼎鼎的《算法导论》）。为什么？因为迭代器是设计模式层面的一个内容，迭代器这一概念的引入，并没有从算法的角度去做任何优化（甚至可能一定程度拖慢了算法的性能），但是，他让算法更易用，代码质量更高，可维护性更强，等等等等（其实都是从软件工程角度出发引入的概念。）

我的这个课程在设计中，尽量引入了一些我认为相对比较简单，不会过于“喧宾夺主”的这类设计模式层面的内容，因此我会大量使用泛型，包括对一些抽象数据结构的介绍（Map 和 Set），但对于一些我认为需要花时间过多，但又不是算法和数据结构这个领域需要重点讨论的内容，我也省略了（比如迭代器的实现）。如果对这部分内容感兴趣，我的建议是，在学完算法和数据结构这个课程以后，去专门学习任何一个语言的标准库（特别是算法和数据结构相关的库）的源码，届时，你已经理解了这些算法和数据结构的原理，你讲更多的聚焦于“为什么这个库是这样实现的？”这个问题。

==========

说回你的问题，其实，在排序过程中，传入一个函数来规定排序方式（什么叫小）是一个很标准的接口设计方式，Java 本身的排序算法也设计了这个接口。

但是，非常重要的，你设计的这个接口的调用方式是： minIndex = fn(arr[i], arr[j])，相当于是用自定以的 fn 比较了 arr[i] 和 arr[j] 两个元素，将较小的元素的索引返回。但实际上在你的这个设计下，这是做不到的。比如 fn 接到了链各个元素 99 和 166，不管你的 fn 的逻辑是怎样的，请问假如在你的定义下，99 更小，那么返回多少？166 更小，又要返回多少？相信你已经看出来问题了，问题的关键是，这个函数不知道传来的两个元素的索引是谁，即使能判断出谁大谁小，也不知道返回什么索引。

所以，fn 应该只负责判断大小。你的 fn 的设计后的调用应该更类似于：

if(fn(arr[i], arr[j])){
    minIndex = i
}

此时，fn 的语义是，判断传来的两个元素 a 和 b，是否 a < b，如果 a < b，返回 true，否则返回 false。所以，这个函数的名字使用 less 更合适一些，更有语义：

if(less(arr[i], arr[j])){
    minIndex = i
}

请再体会一下，这个接口设计，本质和课程里在自定义类中设计的 compare 是回事儿，只不过我们在课程中把这个 compare 函数和类绑定在了一起而已。

更进一步，在你的实现中，做了一个判断，看用户是否传来了 fn，如果传来了，则用 fn 作比较，否则用“默认”的 < 作比较，实际上，< 本身就是一种比较方式。 < 相当与调用了这样的一个 fn:

bool fn(int a, int b){
    return a < b
}

所以，这两个逻辑完全可以统一，而不需要再排序内部做 if 判断。如果 Typescript 支持默认参数的话，相当于 fn 应该有一个默认参数，用标准的比较方式，而用户可以覆盖这个默认参数（C++ 使用这种方式）；如果不支持的话，可以提供两个接口，其中一个接口比第二个接口多一个自定义的函数参数，可以做自定义的比较（Java 采用这种方式）。

继续加油！：）

收起回答