插入排序：對一個擁有n個記錄的有序序列旬蟋，插入一個記錄后油昂，得到一個記錄為n+1的有序序列的過程。
其中 n>=1;
我們升序排序

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

不斷將后續(xù)的每個記錄插入到已經(jīng)排好序的序列之中咖为，使之成為新的有序系列

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

#pragma mark--插入排序 升序排序
void insertSort(int a[],int n){
    int i = 1;
    int j = 0;                         //代價       次數(shù)
    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]待插入的數(shù)
            temp = a[i];//存儲較小的數(shù)   //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
 
      當(dāng)?shù)趙hile行代碼對每個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的線性函數(shù)   時間復(fù)雜度O(n)
        
        所以當(dāng)序列基本有序時躁染，應(yīng)采用直接插入排序
 
        當(dāng)?shù)趙hile行代碼對每個j = 0,1,2...,n-1時鸣哀，始終有a[j]<temp,則是最壞情況，∑求和公式中(c5+c6+c7)(n-1)*n/2
 
      最后整理得 T(n) = an^2 +bn+c ,它是n的二次函數(shù)  時間復(fù)雜度O(n^2)
 
 */
#pragma mark --打印數(shù)組元素
void print(int a[],int n){
    
    printf("\n");
    for (int i = 0; i<n; i++) {
        
        printf("%5d",a[i]);
    }
    printf("\n");
}
#pragma mark--產(chǎn)生隨機(jī)數(shù)組
void randomArray(){
    
    for (int i = 0; i < N ; i++) {
        
        array[i] = arc4random()%N;
    }
}

main函數(shù)調(diào)用如下：

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;
}