插入排序：对一个拥有n个记录的有序序列，插入一个记录后，得到一个记录为n+1的有序序列的过程。
其中 n>=1;
我们升序排序

65FDF4A3-8817-4137-AF52-A83F8D1956D3.png

不断将后续的每个记录插入到已经排好序的序列之中，使之成为新的有序系列

#define N 10
static int array[N] ={0};

#pragma mark--插入排序 升序排序
void insertSort(int a[],int n){
    int i = 1;
    int j = 0;                         //代价       次数
    int temp = 0;
    for (; i< n; i++) {                //c1        n-1
        
        if (a[i]<a[i-1]) {             //c2        n-1
            
            j = i-1;                   //c3        n-1
            
            //a[i]待插入的数
            temp = a[i];//存储较小的数   //c4        n-1
            
    //每一个记录都和这个待插入的记录比较                //n-1
    while (j>=0&&a[j]>temp) {          //c5      // ∑j   //∑求和符号 j的取值范围[0,n-1]
                                                 //j=0
        

                                                 //n-1
                a[j+1] =a[j];         //c6          ∑j
                                                 //j=0
        
        
                                                // n-1
                j--;                  //c7      //  ∑j
                                                // j=0
            }
            a[j+1] = temp;            //c8          n-1

        }
    }
    
}
/*
                                                        n-1
      T(n) = c1(n-1) +c2(n-1)+c3(n-1)+c4(n-1) +(c5+c6+c7)∑j + c8(n-1)
                                                        j=0
 
      当第while行代码对每个j = 0,1,2...,n-1时，始终有a[j]>=temp,则是最佳情况，∑求和公式中j=1;
 
     从而得 T(n) = (c1+c2+c3+c4+c5+c6+c7+c8)(n-1) 
 
                = (c1+c2+c3+c4+c5+c6+c7+c8)n -(c1+c2+c3+c4+c5+c6+c7+c8)
 
        可以表示为=an+b  它是n的线性函数   时间复杂度O(n)
        
        所以当序列基本有序时，应采用直接插入排序
 
        当第while行代码对每个j = 0,1,2...,n-1时，始终有a[j]<temp,则是最坏情况，∑求和公式中(c5+c6+c7)(n-1)*n/2
 
      最后整理得 T(n) = an^2 +bn+c ,它是n的二次函数  时间复杂度O(n^2)
 
 */
#pragma mark --打印数组元素
void print(int a[],int n){
    
    printf("\n");
    for (int i = 0; i<n; i++) {
        
        printf("%5d",a[i]);
    }
    printf("\n");
}
#pragma mark--产生随机数组
void randomArray(){
    
    for (int i = 0; i < N ; i++) {
        
        array[i] = arc4random()%N;
    }
}

main函数调用如下：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        NSLog(@"Hello, World!");
        randomArray();
        printf("排序前\n");
        print(array, N);
        insertSort(array, N);
        printf("排序后\n");
        print(array, N);
        
    }
    return 0;
}