Golang实现插入排序算法

原创

已于 2024-05-24 20:37:24 修改 · 931 阅读

8 ·

CC 4.0 BY-SA版权

文章标签：

#排序算法 #算法 #数据结构 #golang

于 2024-05-24 20:36:38 首次发布

插入排序介绍

插入排序是一种简单直观的排序算法。它通过构建有序序列，对于未排序数据，将其插入到已排序序列的适当位置，使得插入后的序列仍然有序。具体实现上，插入排序每次从未排序数据中取出一个元素，然后将其与已排序序列中的元素进行比较，找到合适的位置插入。这个过程重复进行，直到所有元素都插入到有序序列中为止。

时间复杂度

插入排序的时间复杂度为O(n^2)，其中n为待排序数据的数量。最差情况下，当序列是逆序排列时，插入排序需要进行的比较次数为n(n-1)/2，交换次数也为n(n-1)/2。最好情况下，当序列已经有序时，插入排序只需要进行n-1次比较，没有交换操作。

算法思想

插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序码依次与有序表的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。

算法实现

算法讲解：我们首先完成第一次，也就是给第二个元素在有序表中找到合适的位置并插入，先定义一个insertVal代表数组中的第二个元素；insertIndex代表第二个元素的前一个元素的下标，然后进行循环判断，循环的必要条件是：1.insertIndex不能小于零，因为数组没有负值的下标（js中逆序除外）；2.arr[nsertIndex]必须小于insertVal，不然没有比较的意义（文中是按照从大到小的）满足这两个条件之后将有序数组后移一位，将.insertIndex--，然后进行将无序表中的元素插入到有序数组中，判断insertIndex+1