插入排序——直接插入排序

佚名 6年前 (2018-12-07) 算法 1220人围观抢沙发百度已收录

直接插入排序算法

基本思想：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

实例：

　　0.初始状态 3，1，5，7，2，4，9，6（共8个数）

　　有序表：3；无序表：1，5，7，2，4，9，6

　　1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，3；无序表：5，7，2，4，9，6

　　2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，3，5；无序表：7，2，4，9，6

　　3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，3，5，7；无序表：2，4，9，6

　　4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，2，3，5，7；无序表：4，9，6

　　5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，2，3，4，5，7；无序表：9，6

　　6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，2，3，4，5，7，9；无序表：6

　　7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序

　　有序表：1，2，3，4，5，6，7，9；无序表：（空）

package sort;
/**
 * 直接插入排序  的实现
 * 稳定算法
 * @author qimingwei
 *
 */
public class InsertSort {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {3,1,5,7,2,4,9,6};
        new InsertSort().insertSort(a);
    }
    /**
     * 直接插入排序算法的实现
     * @param a
     */
    private void insertSort(int[] a) {
        // TODO Auto-generated method stub
        System.out.println("———————————————————直接插入排序算法—————————————————————");
        int n = a.length;
        int i,j;
        for(i=1;i<n;i++){
            /**
             * temp为本次循环待插入有序列表中的数
             */
            int temp = a[i];
            /**
             * 寻找temp插入有序列表的正确位置
             */
            for(j=i-1;j>=0 && a[j]>temp;j--){
                /**
                 * 元素后移，为插入temp做准备
                 */
                a[j+1] = a[j];
            }
            /**
             * 插入temp
             */
            a[j+1] = temp;
            print(a,n,i);
        }
        printResult(a,n);
    }
    /**
     * 打印排序的最终结果
     * @param a
     * @param n
     */
    private void printResult(int[] a, int n){
        System.out.print("最终排序结果：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
    /**
     * 打印排序的每次循环的结果
     * @param a
     * @param n
     * @param i
     */
    private void print(int[] a, int n, int i) {
        // TODO Auto-generated method stub
        System.out.print("第"+i+"次：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
}