算法原理：依次对比每个位置上的元素与之前元素的大小，并进行交换，直道之前元素不大于目标元素

算法复杂度：O(n^2)

c++实现整形数组排序

1 void insertionSort(int arr[],int n) 2 { 3     for(int i=1;i
     
      0;j--) 5         { 6             if(arr[j-1]>arr[j]) 7                 swap(arr[j],arr[j-1]); 8             else 9                 break;10         }11     return;12 }
     

每次swap经过了三次赋值运算，可通过改写语句优化算法，建立一个临时变量存储当前元素数据，用一次赋值运算代替swap函数。

1 void insertionSort(int arr[],int n) 2 { 3     for(int i=1;i
     
      0&&arr[j-1]>e;j--) 8             arr[j]=arr[j-1]; 9         arr[j]=e;10     }11     return;12 }
     

将第二层循环内的判断语句加入到了for循环判断中，省去了break，需注意的是，与j-1元素对比的是存储当前元素的临时变量e。

转化为范型

1 template 
     
       2 void insertionSort(T arr[],int n) 3 { 4     for(int i=1;i
      
       0&&arr[j-1]>e;j--) 9             arr[j]=arr[j-1];10         arr[j]=e;11     }12     return;13 }
      
     

算法特点是经过排序的部分顺序确定，而第一个元素自然有序，所以第一层循环从i=1开始，第二层循环内，判断之前元素不大于当前元素时，说明已经找到当前元素位置，可用break跳出本次循环。

因为存在跳出循环的情况，所以插入排序更适合基本有序的数组排序。