Java数据结构与算法（二）插入排序法

妖狐艹你老母 2021-09-26 20:12 297阅读 0赞

# 一、图解插入排序法： #

![这里写图片描述][70]  
将当前元素插入到前面合适的位置，以元素2为例子：  
首先2 < 8 那么 2与8交换位置：  
![这里写图片描述][70 1]  
首先2 < 6 那么 2与6交换位置：  
![这里写图片描述][70 2]  
其他的元素也是依此类推：

# 二、代码分析 #

package paixu;
    
    /** * Created by KPL on 2018/6/29. */
    public class ChaRuPaiXu { 
        public static void main(String[] args) {
            int array[] = {
       1,2,4,3,9,7,8,6};
            int temp = 0;
            for( int i = 1;i < array.length;i++ ){
                //将当前元素插入到合适的位置
                for( int j = i ; j > 0 ; j-- ){
                    //如果比前一个元素小，就交换
                    if( array[j] < array[j-1] ){
                        temp = array[j];
                        array[j] = array[j-1];
                        array[j-1] = temp;
                    }
                    //如果已经放入了合适的位置了，直接跳出当前循环
                    else{
                        break;
                    }
                }
            }
            for( int i = 0 ; i < array.length ; i++ ){
                System.out.print(array[i]+" ");
            }
        }
    }

插入排序法在最差的情况下时间复杂度为O(n^2)，但是在排序对象几乎有序的情况下，效果是非常好的。

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916]  
> 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> ![这里写图片描述][70 3]**

[70]: /images/20210923/42ceb29a29434c4b8ad05e044dbd4748.png
[70 1]: /images/20210923/6b213da0ad8843d7afde80694da11c93.png
[70 2]: /images/20210923/989b75a0e82d48778f36a0cc25964507.png
[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916
[70 3]: /images/20210923/1e0c95a871474fc981eaec1977d01037.png