1.简单的选择排序 代码:bool selectionsort(int *array,int n) //array为存储数据的数组,n为数组元素个数{int k,temp; //k用来存储,临时最小数据的位置for(int i=0;i<n-1;i++) { k=i; for(int j=i+1;j<n;j++) //从第i个数开始选择最小数位置,存于k中if(array[j]<array[k])k=j; if(k!=i) //若最小数,不为array[i],则array[i]与array[k]进行交换 {temp=array[i];array[i]=array[k];array[k]=temp; }}return true;}思想:逐个找出,第一小,第二小....第n小的数...算法平均时间复杂度: O(n^2)2.插入排序 代码:bool insertionsort(int *array,int n){int temp; //用来存储,插入的数据for(int i=1;i<n;i++) { temp=array[i]; //用temp记录array[i] for(int j=i-1;j>=0;j--) //逐个向前寻找插入点 {if(temp>array[j]) //找到,跳出循环break;else //没找到,将前一个数据后移array[j+1]=array[j]; } array[j+1]=temp;}return true;}思想: 逐个取数,插入一个有序数组(从后向前插)算法平均时间复杂度: O(n^2)3.自底向上排序 代码:bool bottomupsort(int *array,int n){int length=1,temp_length,i; //temp_length表示单个合并数组的长度while(length<n){ temp_length=length; //length表示合并后数组的长度 length=2*temp_length; i=0; //i用于记录合并数组的起始位置 while(i+length-1<=n-1) {merge(array,i,i+temp_length,i+length-1); //合并i~i+temp_length-1 和 i+temp_length~i+length-1 段i=i+length; //取下一个合并段的起始位置 } if(i+temp_length<n-1)merge(array,i,i+temp_length,n-1); //对尾部剩余段合并}return true;}bool merge(int *array,int start1,int start2,int n) //合并两个有序数组{int temp_n=n-start1+1, //两合并数组的长度和 *temp_array, n1=start2-1, //第一个有序数组的末端位置 temp_start1=start1; //记录start1的初始位置temp_array=(int *)malloc(sizeof(int)*temp_n); //申请长度为temp_n的整形空间,用于临时存储合并后的数组for(int i=0;start1<=n1&&start2<=n;i++) //对两个有序数组进行合并,存储于temp_array{ if(array[start1]<=array[start2]) {temp_array[i]=array[start1];start1++; } else {temp_array[i]=array[start2];start2++; }}if(start1<=n1) { while(start1<=n1) {temp_array[i++]=array[start1];start1++; }}else{ while(start2<=n) {temp_array[i++]=array[start2];start2++; }}for(i=0,start1=temp_start1;i<temp_n;start1++,i++) //将合并后的有序数组,复制到array数组中{ array[start1]=temp_array[i];}free(temp_array);return true;}思想: 将数组的个部分,两两有序数组进行合并算法平均时间复杂度: O(nlogn)4.快速排序 代码:void QuickSort(int low,int high,int *array){int pos;if(low<high){ pos=SPLIT(low,high,array); //以array[low]进行划分,pos最为划分点 //前一部分<array[low],后一部分,反之 QuickSort(low,pos-1,array); //对划分后的前一部分递归处理 QuickSort(pos+1,high,array); //对划分后的后一部分递归处理 }}int SPLIT(int low,int high,int *array){int temp=array[low]; //用temp来记录划分数while(low<high){ while(array[high]>temp&&low<high) //寻找小于temp的数high--; if(low==high)break; else {array[low]=array[high]; low++; } while(array[low]<temp&&low<high) //寻找大于temp的数low++; if(low==high)break; else {array[high]=array[low];high--; }}array[low]=temp; //最终low=high作为划分点,并将划分数存于array[low]return low;}思想:就是你 从数组中 任取一个元素 p (可随机取,现在以取第一个为例)以P作为主元,对数组 进行划分 ,前一部分小于 P,后一部分 大于p最后 划分处 存储 p然后分别对划分后的前一部分 和 后一部分 递归调用算法平均时间复杂度: O(nlogn)5.归并排序 代码:bool MergeSort(int low,int high,int *array){int middle=(high+low)/2; //将数组划分为2分if(low<high){ MergeSort(low,middle,array); //对前一部分进行递归处理 MergeSort(middle+1,high,array); //对后一部分进行递归处理 HeBing(low,middle,middle+1,high,array); //将排序后的,前后两部分,进行合并}return true;}bool HeBing(int low1,int high1,int low2,int high2,int *array){int *temp, i=low1, j=low2, k=0;temp=(int *)malloc((high2-low1+1)*sizeof(int)); //temp用于临时存储合并后的数组while(i<=high1&&j<=high2) //对两个有序数组进行合并{ if(array[i]<array[j]) {temp[k++]=array[i];i++; } else {temp[k++]=array[j];j++; } }if(i<=high1){ while(i<=high1)temp[k++]=array[i++];}else{ while(j<=high2)temp[k++]=array[j++];}for(i=low1,j=0;i<=high2;i++,j++) //将合并后的数组,复制到array中{ array[i]=temp[j];}free (temp);return true;}思想: 将数组划分为小数组,通过局部的有序合并,解决问题算法平均时间复杂度: O(nlogn)6.冒泡排序 代码:bool bubblesort(int *array,int n){int flag=1, //用来标记是否发生交换 temp;for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++) {if(array[j]<array[j-1]) {temp=array[i];array[i]=array[j];array[j]=temp;flag=0;} } if(flag) //如果flag为真,及没发生交换,直接跳出循环break; elseflag=1;}return true;}思想: 相邻两数比较,小数放前面算法平均时间复杂度: O(n^2)7.堆排序 代码:bool slipdown(int *array,int cur,int n){for(int next=2*cur;next<=n;next=2*cur) //next表示cur的左孩子{ if(next<n&&array[next]<array[next+1]) //取cur的两个孩子的大者next++; if(array[next]<array[cur]) break; int temp=array[cur]; //交换cur和他孩子中的大者 array[cur]=array[next]; array[next]=temp; cur=next; //令当前需要调整的关键字的位置cur=next}return true; }bool heapsort(int *array,int n){ int temp;for(int i=n/2;i>0;i--) //将数组调整为大顶堆 slipdown(array,i,n);for(int N=n;N>1;N--) //选出堆中最大元,存于N位置,循环进行{ temp=array[N]; array[N]=array[1]; array[1]=temp; slipdown(array,1,N-1);}return true;}思想: 用二叉树的结构来表示数组,及用数组来表示二叉树的结构,比如i为父节点其孩子为,2i,和2i+1 其中,大顶堆中 父节点大于其两个孩子算法平均时间复杂度: O(nlogn)8.基数排序 代码:bool radixsort(int *array,int n){L TENL[10]; //其中TENL[m].number中存储,数据的第i位为m的数据int k;for(int i=0;i<10;i++) TENL[i].n=0;for(i=1;i<=5;i++) //这里假设 数据都 小于100000,对数据进行五次分配{ for(int j=0;j<n;j++) //对数据进行分配 {k=getnum(array[j],i);TENL[k].number[TENL[k].n]=array[j];TENL[k].n++; } j=0; for(k=0;k<10;k++) //将此次分配后的数据,按顺序重新置入array中 {for(int m=0;m<TENL[k].n;m++)array[j++]=TENL[k].number[m];TENL[k].n=0; }}return true;}int getnum(int num,int i) //从个位起,获得num的第i为数据{int temp=1;for(int j=0;j<i;j++) temp=temp*10;return (num%temp-num%(temp/10))/(temp/10);}思想:先从数据的低位开始,进行分配,分成10个空间,分别存储位为,0,1,2,3...9 重复的对次地位操作,知道预定的高位,排序完成
