描述

插入排序是一种常用的算法，一些面试官喜欢问它。正如您将在本课程中看到的，这是一种易于理解和实现的算法。您将了解算法的复杂性，并理解为什么很少使用该算法。

我将给出源代码的演练，我也在我的存储库中提供:github.com

也可以看一下我的二分搜索课程，插入排序使用了那个算法。

项目

我想让你写一个插入排序函数。选择你最喜欢的语言，或者面试时使用的语言，并实现一个对值列表进行排序的函数。使用我在这门课上介绍的算法。

在示例Python实现中，签名看起来像这样:

' ' ' py def insertion_sort(items: List[ComparableT]) -> List[ComparableT]: ' ' '

验证排序算法

作为一个奖励项目，编写验证排序算法。这是单元测试的基本代码。它还探讨了一些概念，这些概念将在面试中对你有所帮助。

Verify sort接受一个未排序列表和一个已排序列表。它验证已排序的列表确实是未排序列表的已排序版本。