JAVA十大排序算法之插入排序详解
目录
- 插入排序
- 代码实现
- 动图演示
- 代码实现
- 时间复杂度
- 算法稳定性
- 总结
插入排序 当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。
插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。
1.对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入。
2.为了给要插入的元素腾出空间,需要将插入位置之后的已排序元素在都向后移动一位。
【JAVA十大排序算法之插入排序详解】
![JAVA十大排序算法之插入排序详解](https://img.it610.com/image/info11/faebf07a3b2a4991a4d2dd21a50f9e4c.png)
文章图片
代码实现
对下面数组实现排序
:{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}
动图演示
代码实现
public class InsertionSort {public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}; public static int[] sort(int[] array) {if (array.length == 0) {return array; }//待排序数据,改数据之前的已被排序int current; for (int i = 0; i < array.length - 1; i++) {//已被排序数据的索引int index = i; current = array[index + 1]; //将当前元素后移一位while (index >= 0 && current < array[index]) {array[index + 1] = array[index]; index--; }//插入array[index + 1] = current; }return array; }public static void print(int[] array) {for (int i : array) {System.out.print(i + ""); }System.out.println(""); }public static void main(String[] args) {print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); }}
时间复杂度
在上面图示中,第一趟循环比较一次,第二趟循环两次,依次类推,则最后一趟比较n-1次:
1 + 2 + 3 +… + n-1 = n*(n-1)/2也就是说,在最坏的情况下(逆序),比较的时间复杂度为O(n2)
在最优的情况下,即while循坏总是假的,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n-1次,时间复杂度为O(n)。
算法稳定性
在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变,所以插入排序是稳定的。
总结 本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注脚本之家的更多内容!
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 一个选择排序算法
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用(一)
- java之static、static|java之static、static final、final的区别与应用