插入排序：的基本思想是：每次将一个特排序的记录，按其关键字大小插入到前面已经拍好序的子文件中的适当位置，直到全部记录插入完成为止。

两种排序的算法：

直接插入排序：

希尔排序:

 

直接插入排序：

 

直接插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

 

改进的方法 　　一种查找比较操作和记录移动操作交替地进行的方法。 具体做法：     　将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较：     　① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；       ②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。     　关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。

 

一，复杂度： O(n

²)

#include 
      
       void InsertSort(int *a, int size){    int temp,j;    for(int start=1;start
       
        0&&(temp < a[j-1]);j--)        {            a[j] = a[j-1];                    }        a[j]=temp;            }}void print_content(int *a, int size){        for(int i=0;i
       
      

 

二，排序----插入排序 插入排序的思路是：新插入的数与比它前面的数进行比较，如果新插入的数比它前面的数小，那么比它前面的数后移；否则，就找到了新插入的数的位置插入排序的时间复杂度是：O(n^2)#include
     
      #include
      
       #define N 100int array[N];void init_array(int a[],int n);void print_array(int a[],int n);void insert_sort(int a[],int n);int main(){ init_array(array,N); insert_sort(array,N); print_array(array,N); } void init_array(int a[],int n){ int i; for(i=0;i
       
        =0&& temp
       
      
     

　　

 

2

插入排序原理：将第i个元素与前i-1个元素从右向左开始比较，若第i个元素小，则将前面的元素向后移，直到找到可以插入的位置。

比较次数为1+2+3+...+n=(1+n)*n/2，因此时间复杂度也是O(n^2)

 

插入排序#include 
     
      using namespace std;//元素交换void swap(int &a,int &b){    int temp=a;    a=b;    b=temp;}/*///插入排序*/void InsertSort(int *a,int len){    int i,j,key;    for(i=1;i
      
       =0 && a[j]>key )        {            if(a[j]>key)            {                a[j+1]=a[j];                j--;            }        }        a[j+1]=key;         //    a[j+1]=key; j++;    }    for(i=0;i
       
        >n;    cout<<"请输入"<
        
         <<"个元素:"<
         
          >a[i];    InsertSort(a,n);    return 0;}
         
        
       
      
     

 

 

4，

 

C 插入排序 插入算法描述1.从第一个元素开始，该元素可以认为已经被排序2.取出下一个元素，在已经排序的元素序列中从后向前扫描3.如果该元素（已排序）大于新元素，将该元素移到下一位置4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置5.将新元素插入到该位置中6.重复步骤2示例代码示例代码为C语言，输入参数中，需要排序的数组为arr[]，排序长度为length。示例代码的函数采用in-place排序，调用完成后，arr[]中从0到length处于升序排列。复制代码 1 #include 
     
       2 #include 
      
        3  4 char *insertion_sort_char(char arr[], int length) 5 { 6     int i; 7     for(i = 1; i < length; i ++) { 8         int key = arr[i]; 9         int j = i - 1 ;10         while((j >= 0) && (arr[j] > key)) {11             arr[j + 1] = arr[j];12             j --;13         }14         arr[j + 1] = key;15     }16     return arr;17 }18 19 int main()20 {21     char arr[] = {
   'a','c','p','e','q','d'};22     printf("%s\n", arr);23     char *result= insertion_sort(arr, 6);24     printf("%s\n", result);25     exit(0);26 }复制代码输出结果gcc -o insert_sort insert_sort.c./insert_sortacpeqdacdepq 算法分析　　如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 原理 　　插入排序：已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）优劣　　优点：稳定，快；缺点：比较次数不一定，比较次数越多，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。