插入排序、选择排序、合并排序几种排序比较

1、 插入排序，时间复杂度O(n^2)

一个数组A[0,...,n-1],将A[j]插入到子数组A[0,...,j-1]中，其中数组A[0,...,j-1]是排好序的（假如为非降序），把A[j]和A[j-1]->A[0]逐个进行比较，大的数往后移位，将A[j]插入适当的位置（找到最后一个比它大的，放在前面）。

递归法，为排序A[0,...,n-1],先排序A[0,...,n-2],然后把A[n-1]插入到已经排序的数组A[0,...,n-2]中去。如下：

?

int binary_search(int num,int num_arr[],int start,int end){int mid=0;    if(start>=end&&num_arr[start]!=num){//注意递归终止条件return 0;   }mid=(start+end)/2;   if(num==num_arr[mid]){   return mid;         }   else if(num<num_arr[mid]){      binary_search(num,num_arr,start,mid);   }   else{      binary_search(num,num_arr,mid,end);   }}

?