首页 / 算法 / 十大排序算法-插入排序
十大排序算法-插入排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了十大排序算法-插入排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2167字,纯文字阅读大概需要4分钟。
内容图文
![十大排序算法-插入排序](/upload/InfoBanner/zyjiaocheng/606/d82c832f83604599af4f015d37d9beb0.jpg)
1. 算法步骤
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
2. 时间复杂度
最好是O(n),最坏是O(n^2)
3、代码实现
import java.util.Arrays; /** * Created with IntelliJ IDEA. * User: Andrew * Date: 2021/02/10 * Time: 20:33 * Description: No Description */ public class InsertSort { public static void main(String[] args) { int[] arr = new int[]{3,4,5,7,1,2,0,3,6,8}; // 排序前数组 System.out.println(Arrays.toString(arr)); insertSort(arr); // 排序后的数组 System.out.println(Arrays.toString(arr)); } public static void insertSort(int[] arr){ // 遍历所有的数字 for (int i = 1;i< arr.length;i++){ // 如果当前数字比前一个数字小 if (arr[i] < arr[i-1]){ // 就把当前遍历的数存起来 int temp = arr[i]; int j; // 遍历当前数字前面的所有数字 for (j = i-1;j >= 0 && temp < arr[j];j --){ // 把前一个数字赋值给后一个 arr[j+1] = arr[j]; } // 把临时变量赋给不满足条件的后一个元素 arr[j+1] = temp; } } } }
/**
* Created with IntelliJ IDEA.
* User: Andrew
* Date: 2021/02/10
* Time: 20:42
* Description: No Description
*/
object InsetSortDemo {
def swap(array: Array[Int],index1:Int,index2:Int): Unit ={
val temp = array(index1)
array(index1) = array(index2)
array(index2) = temp
}
/**
* 插入排序:
* 本质:
* 1. 类似于玩扑克牌, 手里的牌总是有序的.
* 每取一张牌, 只需要从后向前比较即可,一旦碰到比新牌小的, 新牌只需要插入到这张小牌的后面即可
*
* 2. 具体排序: 第 1 个元素是有序的, 第 2 个元素以前与前面的进行比较, 如果碰到大的就交互, 碰到小的停下来. 然后前 2 个元素排序完成
* 然后第 3 个元素....
*
* 3. n 个元素, 只需要排 n-1 次即可
*
* @param arr
*/
def insertSortDemo(arr: Array[Int]): Unit = {
for (i <- 0 until arr.length-1){
// 从i+1的位置开始向前比较
for (j <- i+1 until (0,-1)){
// 后面的元素比前一个小就交换位置
if (arr(j) < arr(j-1)) swap(arr,j,j-1)
}
}
}
def main(args: Array[String]): Unit = {
val array = Array(3, 4, 5, 7, 1, 2, 0, 3, 6, 8)
println(array.toBuffer)
insertSortDemo(array)
println(array.toBuffer)
}
}
内容总结
以上是互联网集市为您收集整理的十大排序算法-插入排序全部内容,希望文章能够帮你解决十大排序算法-插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。