算法导论：主要关注的是程序的性能；速度令人渴望！！！

排序算法是经典算法

1、插入排序

(1)、算法模型


(2)、代码实现

#include<stdio.h>voidinsertSort(int*a,intcount);voidshowArray(int*a,intcount);voidshowArray(int*a,intcount){inti;for(i=0;i<count;i++){printf("%d",a[i]);}printf("\n");}voidinsertSort(int*a,intcount){inti;intj;intn;inttmp;for(i=1;i<count;i++){tmp=a[i];for(j=0;a[i]>a[j]&&j<i;j++){;}if(i!=j){for(n=i;n>j;n--){a[n]=a[n-1];}a[j]=tmp;}}}voidmain(void){inta[]={2,5,7,1,11,0,6,9};intcount=sizeof(a)/sizeof(int);printf("排序前输出如下:");showArray(a,count);insertSort(a,count);printf("排序后输出如下:");showArray(a,count);}

(3)、结果截图



(4)、算法分析

插入排序最坏的情况：数组中所有元素全部逆序排列；

时间复杂度：O(n^2);


2、归并排序

(1)、算法思想：

i、if n = 1; done

ii、递归排序，分2部分，在[0, n/2]和[n/2, n]

iii、将2部分归并排序

(2)、核心代码实现

#include<stdio.h>#include<malloc.h>voidmergerSort(int*a1,int*a2,int**a3,intcount1,intcount2,int*count3);voidshowArray(int*a3,intcount);voidshowArray(int*a3,intcount){inti;for(i=0;i<count;i++){printf("%d",a3[i]);}printf("\n");}voidmergerSort(int*a1,int*a2,int**a3,intcount1,intcount2,int*count3){intcount;inti=0;intj=0;intn=0;count=*count3=count1+count2;*a3=(int*)malloc(sizeof(int)*count);//以下的都是<，因为传过来的是数组长度；while(i<count1&&j<count2){if(a1[i]<a2[j]){(*a3)[n++]=a1[i];i++;}elseif(a1[i]==a2[j]){(*a3)[n++]=a1[i];(*a3)[n++]=a2[j];i++;j++;}else{//刚才写程序else(a1[i]>a2[j]),后发现else语句后面是没有条件的!!!(*a3)[n++]=a2[j];j++;}}while(i<count1){(*a3)[n++]=a1[i];i++;}while(j<count2){(*a3)[n++]=a2[j];j++;}}/*归并排序核心算法就是：将已经排好序的2个数组进行最终的排序过程；*/voidmain(void){inta1[]={1,3,5,7};inta2[]={0,2,4,6,8,9,10};intcount1=sizeof(a1)/sizeof(int);intcount2=sizeof(a2)/sizeof(int);int*a3=NULL;intcount3=0;mergerSort(a1,a2,&a3,count1,count2,&count3);showArray(a3,count3);free(a3);}

(3)、结果截图


(4)、完整代码实现

#include<stdio.h>#include<malloc.h>voidmergeSort(int*a,intlow,inthigh);voidmerge(int*a,intlow,intmid,inthigh);voidmerge(int*a,intlow,intmid,inthigh){inti=low;intj=mid+1;intn=0;int*a2;a2=(int*)malloc(sizeof(int)*(high-low+1));if(a2==NULL){return;}//以下都是<=,因为传过来的都是下标；while(i<=mid&&j<=high){if(a[i]<a[j]){a2[n++]=a[i];i++;}elseif(a[i]==a[j]){a2[n++]=a[i];i++;j++;}else{a2[n++]=a[j];j++;}}while(i<=mid){a2[n++]=a[i];i++;}while(j<=high){a2[n++]=a[j];j++;}for(n=0,i=low;i<=high;n++,i++){//将a2中的元素复制回a中;a[i]=a2[n];}free(a2);}voidmergeSort(int*a,intlow,inthigh){intmid;if(low<high){mid=(low+high)/2;mergeSort(a,low,mid);mergeSort(a,mid+1,high);merge(a,low,mid,high);}}voidmain(void){inta[]={2,4,1,7,5,6,9,10};intcount=sizeof(a)/sizeof(int);inti;mergeSort(a,0,count-1);for(i=0;i<count;i++){printf("%d",a[i]);}printf("\n");}

(5)、结果截图

(6)、算法分析

归并排序的时间复杂度:树高度log(n)，一共要对n个元素进行排序，所以为：O(nlogn);

在30个元素以内，插入排序性能更好，超过30个元素之后归并排序的性能更加优秀；