学步园

算法导论视频第一集：

1、插入排序：

最坏的情况下： j 从2 到n 求和 => O(n²)

平均的情况下： j = n/2          => O(n²)

代码：

////////////////////////////插入排序////////////////<br /> void insert(int x[])<br /> {<br /> int i,j,num;<br /> int A[N];<br /> for (i=0;i<N;i++)<br /> A[i]=x[i]; //A【】为待排序数组<br /> for (i=1;i<N;i++)<br /> {<br /> if (A[i]<A[i-1])<br /> {<br /> num=A[i];<br /> j=i-1;<br /> while (j>=0&&num<A[j])<br /> {<br /> A[j+1]=A[j];<br /> j--;<br /> }<br /> A[j+1]=num;<br /> }<br /> }<br /> cout<<"*******************插入排序*****************"<<endl;<br /> for (i=0;i<N;i++)<br /> cout<<A[i]<<' ';<br /> cout<<endl;<br /> } 

2、归并排序：

最坏情况下： O(nlogn)

平均情况下： O(nlogn)

代码：

/////////////////////归并排序//////////////////////<br /> void merge(int A[],int left,int right,int k)<br /> {<br /> int i,j,m;<br /> m=left;<br /> int B[N];<br /> i=left;<br /> j=k+1;<br /> while ((i<=k)&&(j<=right))<br /> {<br /> if (A[i]<=A[j])<br /> {<br /> B[m]=A[i];<br /> i++;<br /> }<br /> else<br /> {<br /> B[m]=A[j];<br /> j++;<br /> }<br /> m++;<br /> }<br /> while (j<=right)<br /> B[m++]=A[j++];<br /> while (i<=k)<br /> B[m++]=A[i++];<br /> i=left;<br /> while (i<=right)<br /> {<br /> A[i]=B[i];i++;<br /> }<br /> }<br /> void mergesort(int A[],int left,int right)<br /> {<br /> int mid;<br /> if(left<right)<br /> {<br /> mid=(right+left)/2;<br /> mergesort(A,left,mid);<br /> mergesort(A,mid+1,right);<br /> merge(A,left,right,mid);<br /> }<br /> }