首页 > 代码库 > 算法学习-1 插入排序

算法学习-1 插入排序

2024-09-16 14:23:27   206人阅读

算法学习-1  插入排序

一、描述：

　　比如说我们玩扑克牌，规定每抓一张牌都要保证左边数字最小；抓第一张牌直接放手里就可以，抓第二张时如果比第一张小，则把它放到第一张牌的左边，假如每张抓来的牌放到手中都有固定位置，第一张为A[0],第二张为A[1],第三张为A[2],如果抓的第三张牌比第一张抓来的牌小，则将其放在A[0]处，对应的第二张牌就应该放在A[1],以此类推。

技术分享

二、java代码实现

public class InsertSort {    //排序后的数组    int sorted[];    public static void main(String[] args) {        //定义一个待排序的数组        final int value[]={1,2,3,5,4,1,5,9,6,2,1,4,5,2,35,8,5};        InsertSort is = new InsertSort();        is.initArray(value.length);        for(int i = 0 ; i < value.length;i++){        is.sort(i,value[i]);        }        is.display();            }    //初始化数组    public void initArray(int size){        this.sorted = new int[size];    }    public void sort(int pos,int value){        //当前“指针”位置        int i = pos;        //i=0时，直接插入sorted数组        if(i==0){            sorted[i]=value;        }else{            //进入这里的i的最小值为1，数组从0开始，sorted[0]的值与新来的value值对比            while(i>0 && sorted[i-1]>value){                //向后移位 并                sorted[i]=sorted[i-1];                sorted[i-1]=value;                i--;            }            sorted[i]=value;        }    }    //显示    public void display(){        for(int i : sorted){            System.out.print(i+" ");        }    }}

三、总结

插入排序依靠插入完成排序功能。

优点：

  • 当待排序数组是顺序有序的情况下，插入排序是最优性能。
  • 插入排序插入相等数据时，效率很高。

缺点：

  • 待排序数组的数据是随机数据时，插入排序的效率很低。

 

转载注明出处：http://www.cnblogs.com/xiemubg/p/6748698.html

算法学习-1 插入排序


联系
我们