直接插入排序算法

数据结构中的排序算法有好几种，对其中的直接插入排序算法总结如下所示：

直接插入排序即是：顺序地把待排序的各个记录按其关键字插入到已排序后的适当位置处。

实例如下所示：

定义的数组： {23,34,56,78,65,90,88,92,18,21}

过程如下所示：

【23】 34 56 78 65 90 88 92 18 21

第 1 次排序结果：【23 34】 56 78 65 90 88 92 18 21 　　

——用34插入到【23】序列中，34>23，故插入后的顺序是【23，34】

第 2 次排序结果：【 23 34 56 】78 65 90 88 92 18 21 　　

——用56插入到【23，34】序列中，56>34，故插入后的顺序是【23，34，56】

第 3 次排序结果：【23 34 56 78】65 90 88 92 18 21 　　

——用78插入到【23，34，56】序列中，78>56，故插入后的顺序是【23，34，56，78】

第 4 次排序结果：【23 34 56 65 78 】90 88 92 18 21 　

——用65插入到【23，34，56，78】序列中，65<78，所以78后移一位，和56比较，65>56,故插入后的顺序是【23，34，56，65, 78】

第 5 次排序结果：【23 34 56 65 78 90 】 88 92 18 21

——用90插入到【23，34，56，65, 78】序列中，78<90 ,故插入后的顺序是【23 34 56 65 78 90 】

第 6 次排序结果： 23 34 56 65 78 88 90 92 18 21

——用88插入到【23 34 56 65 78 90 】序列中，90>88 ,所以90后移一位,故插入后的顺序是【23 34 56 65 78 88 90】

第 7 次排序结果： 23 34 56 65 78 88 90 92 18 21

——用92插入到【23 34 56 65 78 90 】序列中，90<92 ,故插入后的顺序是【23 34 56 65 78 90 92 】

第 8 次排序结果： 18 23 34 56 65 78 88 90 92 21

——用18插入到【23 34 56 65 78 90 92 】序列中，18<92，所以92后移一位，和90比较，90>18,依次后移，直到第一位23，因为18<23, 故插入后的顺序是【18 23 34 56 65 78 88 90 92】

第 9 次排序结果： 18 21 23 34 56 65 78 88 90 92

——用21插入到【23 34 56 65 78 90 92 】序列中，21<92，故92后移一位，和90比较，90>21,依次后移，直到第一位18，因为18<21, 故插入后的顺序是【18 21 23 34 56 65 78 88 90 92】

----------------

以上为直接插入排序算法的具体实例分析：

使用java语言实现的程序如下：

package com.three.twelen;

public class TestInsert01 {

    /**
     * 实现直接插入排序算法
     */public static void showData(int a[]) {
        for(int i=0;i<a.length;i++) {
            System.out.print("   "+a[i]);
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        //定义一个长度为10的数组
        int a[] = {23,34,56,78,65,90,88,92,18,21};
        int i,j;
        System.out.println("排序前的数据是：");
        showData(a);
        System.out.println();
        System.out.println("------------------排序开始-------------------");
        
          for( i=1;i<a.length;i++) {
             int temp=a[i];
             for(  j=i-1;j>=0&&temp<a[j];j--) 
                    a[j+1]=a[j]; 
             a[j+1]=temp;
             System.out.print("第 "+i+" 次排序结果：");
             showData(a);
         }
         System.out.println();
         System.out.println("------------------排序结束-------------------");
         System.out.println("排序后的数据是：");
         showData(a);
    }
 }

以上为程序实现：

代码精简之后如下所示：

         for( i=1;i<a.length;i++) {
             int temp=a[i];
             for(  j=i-1;j>=0&&temp<a[j];j--) 
                    a[j+1]=a[j]; 
             a[j+1]=temp;
           }

程序具体运行结果为：

至此，直接插入排序结束！