直接插入排序算法

 

　基本思想：

　　把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；无序表：（空）

　Java实现：

package sort; /** * 直接插入排序  的实现 * 稳定算法 * @author 那一季的银杏叶 * */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
     
      =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
     

 

　运行结果展示：

　

　　（本文仅供学习交流，如有更好的思路，欢迎留下意见供大家探讨学习~）