#分治

插入排序

 void insertSort(keytype k[ ],int n){
int i, j;
keytype temp;
for(i=1;i<n;i++){
temp=k[i];
for(j=i-1; j>=0 && temp<k[j]; j--)
k[j+1]=k[j];
k[j+1]=temp;
}
}

最好情况 T(n) = an+b

最差情况T(n) = an^2+bn+c

归并排序

 #include <stdio.h>  
 #include <ctype.h>  
 #include <string.h>  
 #include <math.h>  
 #include <stdlib.h>  
 #define MAX 1000  
 ​  
 int temp[MAX], ans[MAX] = {50, 10, 20, 30, 70, 40, 80, 60};  
 ​  
 void Mergesort(int startId, int endId);  
 void Merge(int startId, int midId, int endId);  
 ​  
 int main() {  
     Mergesort(0, 7);  
     for(int i=0; i<8; i++)  
         printf("%d ", ans[i]);  
 ​  
     return 0;  
 }  
 void Mergesort(int startId, int endId){  
     int midId = startId + (endId - startId)/2;  
     if(startId < endId){  
         Mergesort(startId, midId);  
         Mergesort(midId+1, endId);  
         Merge(startId, midId, endId);  
     }  
 }  
 ​  
 void Merge(int startId, int midId, int endId){  
     int i=startId, j=midId+1, k=startId;  
     while(i <= midId && j<=endId){  
         if(ans[i] < ans[j]){  
             temp[k] = ans[i];  
             k++; i++;  
         }else{  
             temp[k] = ans[j];  
             k++; j++;  
         }  
     }  
     while(i <= midId){  
         temp[k] = ans[i];  
         k++; i++;  
     }  
     while(j <= endId){  
         temp[k] = ans[j];  
         k++; j++;  
     }  
     for(i=startId; i<=endId; i++){  
         ans[i] = temp[i];  
     }  
 }