Kotlin程序员插入排序实战

【出自TX面试题】

难度系数：★★★☆☆ 被考察系数：★★★☆☆

题目描述：

给定一个无序整型数组，请用插入排序对数组进行升序排列。

分析与解答：

对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。以数组{38，65，97，76，13，27，49}为例（假设要求为升序排列），直接插入排序具体步骤如下：

第一步插入38以后：[38]65 97 76 13 27 49

第二步插入65以后：[38 65]97 76 13 27 49

第三步插入97以后：[38 65 97]76 13 27 49

第四步插入76以后：[38 65 76 97]13 27 49(www.xing528.com)

第五步插入13以后：[13 38 65 76 97]27 49

第六步插入27以后：[13 27 38 65 76 97]49

第七步插入49以后：[13 27 38 49 65 76 97]

代码示例如下：

程序的输出结果如下：

0 1 2 3 4 5 6 7 8 9

算法性能分析：

插入排序是一种稳定的排序方法，最好情况下的时间复杂度为O（n），最坏情况下的时间复杂度为O（n^2），平均情况下的时间复杂度为O（n^2）。空间复杂度为O（1）。