前言:
此时小伙伴们对“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排序算法