插入排序使用的是增量（incremental）方法；在排好子数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]。

更多信息请参考：

C语言代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 void init(int *array, int count) 7 { 8     int n = 0; 9     srand((unsigned int)time(NULL));10 11     for (n=0; n
         
          =0&&array[j]>temp)  43             {  44                 array[j+1]=array[j];  45                 j--;  46             }  47 48             array[j+1]=temp;  49         }  50     }  51     else52     {   53         //倒排序，从大排到小  54         //比较的轮数  55         for (i = 1; i
          
           =0&&array[j]
          
         
        
       
      
     

运行结果如下：

data before sort:         71   68   58   93   32   80  100   73   10   18

data after sort(asc):     10   18   32   58   68   71   73   80   93  100

data after sort(desc):   100   93   80   73   71   68   58   32   18   10

Java代码：

1 import java.util.Random;    2     3 /**   4 * 插入排序   5 * 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。        6 * 性能：比较次数O(n^2),n^2/4   7 * 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。   8 */    9    10 public class Sort    11 {   12     /*  13      * 输出数组中的数据  14      */   15     public static void OutputArray(int[] array)    16     {   17         for (int data : array)    18         {   19             System.out.print(data + "\t");   20         }   21            22         System.out.println();   23     }   24        25     /*  26      * 生成需要排序的数组  27      */   28     public static int[] createArray(int count)    29     {   30         int array[] = new int[count];   31         Random r = new Random();   32            33         for (int i = 0; i < count; i++)    34         {   35             array[i] = r.nextInt(100);   36         }   37            38         System.out.println("");   39         System.out.print("data before sort:\t");   40            41         OutputArray(array);   42            43         return array;   44     }   45        46     /**  47     * 插入排序  48     */   49     public static void insertSort(int[] array, String sortType)    50     {   51         int insertValue;   52         if (sortType.equals("asc"))    53         {   //正排序，从小排到大   54             //比较的轮数   55             for (int i = 1; i 
     
      =0&&array[index]>insertValue)   61                 {   62                     array[index+1]=array[index];   63                     index--;   64                 }   65                    66                 array[index+1]=insertValue;   67             }   68         }   69         else if (sortType.equals("desc"))    70         {   //倒排序，从大排到小   71             //比较的轮数   72             for (int i = 1; i 
      
       =0&&array[index]
      
     

运行结果如下：

data before sort:    33    99    96    91    85    97    85    82    58    86    

data after sort(asc):    33    58    82    85    85    86    91    96    97    99    

data after sort(desc):    99    97    96    91    86    85    85    82    58    33