使用Java与Python十大排序算法之直接插入排序

直接插入排序 前面文章已经讲完了交换类排序，接下来开始学习插入类排序。顾名思义，所谓插入排序指我们会为每一个数据安排一个适合它的位置并将其插入，直到所有数据就位则排序完成。 直接插入法便是插入排序的典型方法，完全继承了插入排序的“脾气”：简单、粗暴，逮到就插入，毫无技术可言，耿直得可爱。 1. 算法思想 将待排序数组中的记录逐一插入已排序的子序列中，从而得到一个完整的有序数组。 2. 算法步骤 （1）将数组的第一个数据看成一个有序的子序列。 （2）从第二个数据开始，依次与前面的有序子序列进行比较，若待插入数据 array[i]大于或等于array[i-1] ，则原位插入：若待插入数据 array[i]小于数据 array[i-1]，则将数据array[i]临时存放在哨兵t emp中，将有序序列中大于哨兵的所有数据后移一位，然后将哨兵数据插入相应位置。 （3）重复步骤（2），直到整个数组变成有序数组。 3. 算法分析 也许有的读者看得有点糊涂了。为了便于理解，我们将步骤进行拆分讲解。假设我们要给数组［3，1,8，2,1,5］进行排序，由于有两个1，所以将第二个1标记为“1*”，排序