c语方学习笔记六

排序
sb东西
算法（alorithm） 解决一类计算问题




插入排序
示例代码：
#include <stdio.h>
#define LEN 5
int a[LEN]={10,5,2,4,7};
void insertion_sort(void){
int i,j,key;
for(i=1;i<LEN;i++){
printf("element:%d,%d,%d,%d,%d\n",a[0],a[1],a[2],a[3],a[4]);
key=a[i];
j=i-1;
while(j>=0&&a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
printf("end:%d,%d,%d,%d,%d\n",a[0],a[1],a[2],a[3],a[4]);
}
int main(void){
insertion_sort();
return 0;
}




算法的时间复杂度

常见：
o(lgn) o(sqrt(n)) o(n) o(nlgn) o(n2) o(2n) o(n!)



归并排序
首先把长度为len的序列分为两个子序列
对两个子序列分别进行归并排序
两个序列合并为一个

#include<stdio.h>
#define LEN 8
int a[LEN]={5,2,4,7,1,3,2,6};
void merge(int start,int mid,int end){
int n1=mid-start+1;
int n2=end-mid;
int left[n1],right[n2];
int i,j,k;
for(i=0;i<n1;i++){
left[i]=a[start+i];
}
for(j=0;j<n2;j++){
right[j]=a[mid+1+j];
}
i=j=0;
k=start;
while(i<n1&&j<n2){
if(left[i]<right[j]){
a[k++]=left[i++];
}else{
a[k++]=right[j++];
}
}
while(i<n1){
a[k++]=left[i++];
}
while(j<n2){
a[k++]=right[j++];
}
}
void sort(int start,int end){
int mid;
if(start<end){
mid=(start+end)/2;
printf("sort (%d=%d,%d=%d) %d %d %d %d %d %d %d %d


\n",start,mid,mid+1,end,a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]);
sort(start,mid);
sort(mid+1,end);
merge(start,mid,end);
printf("sort (%d=%d,%d=%d) %d %d %d %d %d %d %d %d


\n",start,mid,mid+1,end,a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]);
}

}
int main(void){
sort(0,LEN-1);
return 0;
}