算法_插入排序

插入排序

 插入排序的思想：每一步就是将待排序的数据插入到已经排好序的数据中，直到全部数据依次按照从小（或大）的顺序排列。

 例如：
 1，4，2，5，8，3，7，1
 第一次排序：1，4；2，5，8，3，7，1
 第二次排序：1，2，4；5，8，3，7，1
 第三次排序：1，2，4，5；8，3，7，1
 第四次排序：1，2，4，5，8；3，7，1
 第五次排序：1，2，3，4，5，8；7，1
 第六次排序：1，2，3，4，5，7，8；1

例一：

void insertionSort(T arr[],int n){
    for(int i=1;i<n;i++){
       T e=arr[i];
       int j;
       // 1.插入排序是从后向前比较的
       // 2.遇见相等的情况不用交换位置，直接放到后边即可
       // 3.优化的代码在例二
       for(j=i;j>0;j--){  
           if(arr[j-1]>e)
              arr[j]=arr[j-1];
       }

        arr[j]=e;
    }
}

例二：

template<typename T>
void insertionSort(T arr[],int n){
     for(int i=1;i<n;i++){ //从第二个元素开始
         T e=arr[i];
         int j;
         for(j=i;j>0&&arr[j-1]>e;j--) // 从小到大排列，
              arr[j]=arr[j-1];
         arr[j]=e;
      }
      return;