插入排序java

插入排序简述

　　插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

　第一个元素是有序队列，从第二个元素开始向有序队列中插入，插入完成后将第三个元素向有序队列中插入，依次进行，直到将最后一个元素插入完毕。

　　在将元素插入到有序队列中，要将这个元素与有序队列的元素依次比较，如果小于有序队列的某个元素，将其插入到该元素的前面，否则不做操作。依次比较完毕，没有比其大的，就将其放在有序队列的末尾。

　　图例介绍：

插入排序java

代码：

插入排序类

package com.dxx.order;

public class InsertSort {
private int arrs[];

    public InsertSort(int[] arrs) {
        super();
        this.arrs = arrs;
    }
    
    public void sortArrs(){
        int len = arrs.length;
        int temp = 0;
        //进行len-1次循环，每次循环都将下标为i的元素插入到它前面已经排好序的队列中
        for(int i=1;i<len;i++){
            //进行i次循环，每次循环都将下标为i的元素与下标为j的元素比较，找到比它小的元素，然后插入到那个元素前面，如果一直没有比它小的元素，就不做操作
            for(int j=0;j<i;j++){
                if(arrs[j]>arrs[i]){
                    temp = arrs[i];
                    for(int k = i;k>j;k--){
                        arrs[i] = arrs[i-1];
                    }
                    arrs[j] = temp;
                }

//另一种插入算法
public void sortArrs2(){
        int len = arrs.length;
        int temp = 0;
        //进行len-1次循环，每次循环都将下标为i的元素插入到它前面已经排好序的队列中
        for(int i=1;i<len;i++){
            if(arrs[i]<arrs[i-1]){
            temp = arrs[i];
                while( i>0 && temp<arrs[i-1]){
                    arrs[i]=arrs[i-1];
                    i--;
                }
                 arrs[i] = temp;
            
            }
        }
    }


            }
        }
    }
    
public void printArrs(){
        for(int i :arrs){
            System.out.print(i + "   ");
        }
        System.out.println();
    }

}

主程序类：

package com.dxx.order;

public class MainTest {

    public static void main(String[] args) {
        int arrs[] = {1,3,2,5,4,8,6,7};
        InsertSort insertSort = new InsertSort(arrs);
        insertSort.printArrs();
        insertSort.sortArrs();
        insertSort.printArrs();

    }
}

相关推荐