龙空技术网

排序算法-插入排序-golang实现

读万卷书行万里路2020 33

前言:

此时小伙伴们对“java sort排序算法”都比较着重,我们都需要了解一些“java sort排序算法”的相关知识。那么小编同时在网上网罗了一些有关“java sort排序算法””的相关资讯,希望兄弟们能喜欢,大家一起来学习一下吧!

插入排序是一种简单直观的排序算法,其基本思想是将待排序的元素逐个插入到已排序序列中的合适位置,使得插入后的序列仍然有序。

具体实现步骤如下:

假设待排序序列的第一个元素已经是有序序列,称为已排序序列。从待排序序列中取出下一个元素,将其插入到已排序序列中的合适位置。重复步骤2,直到待排序序列中的所有元素都插入到已排序序列中。

插入排序的实现通常使用两层循环:

外层循环用于遍历待排序序列,从第二个元素开始,依次与已排序序列中的元素进行比较。

内层循环用于将待排序元素插入到已排序序列中的合适位置,具体步骤如下:

将待排序元素保存到临时变量temp中。从已排序序列的最后一个元素开始,依次与temp进行比较,如果已排序元素大于temp,则将已排序元素后移一位。如果已排序元素小于或等于temp,则将temp插入到该位置。重复步骤2和步骤3,直到找到合适的位置插入temp。

最终,待排序序列中的所有元素都会被插入到已排序序列中,完成排序。

插入排序的时间复杂度为O(n^2),其中n为待排序序列的长度。由于插入排序是一种稳定的排序算法,且在小规模数据和基本有序的数据上表现较好,因此在这些情况下,插入排序是一种简单有效的排序算法。

golang实现

/* *  实现一 */func InsertSort(list []int) {   n := len(list)   for i := 1; i <= n-1; i++ {      deal := list[i] // 待排序的数      j := i - 1      // 待排序的数左边的第一个数的位置      // 如果第一次比较,比左边的已排好序的第一个数小,那么进入处理      if deal < list[j] {         // 一直往左边找,比待排序大的数都往后挪,腾空位给待排序插入         for ; j >= 0 && deal < list[j]; j-- {            list[j+1] = list[j]         }      }      list[j+1] = deal   }}/* *  实现二---更简洁 */func InsertSortTwo(list []int) {   n := len(list)   for i := 1; i <= n-1; i++ {      deal := list[i]      if deal < list[i-1] {         for j := i - 1; j >= 0 && deal < list[j]; j-- {            list[j+1], list[j] = list[j], list[j+1]         }      }   }}

标签: #java sort排序算法