十六种经典排序算法

//头文件定义#includestdafx.h#includestdio.h#includegraphics.h#includestdlib.h#includetime.h#includemalloc.hvoidbubbleSort(int*a,intlen);//冒泡算法voidUpdBubbleSort1(int*a,intlen);//改进冒泡算法1----找到一次循环的已排好序位置voidUpdbubbleSort2(int*a,intlen);//改进冒泡算法2--一次循环找到最大\最小值voidquickSort_update(int*a,intlen,intk);//改进快速排序--先使8的块基本有序--实测比一般快速排序节约28%时间(59秒,1亿条随机数据，逆序数时间较长)voidqsort_improve(int*a,intlow,inthigh,intk);//改进快速排序子算法voidInsertSort(int*a,intn);//直接插入排序voidshellSort(int*a,intn);//直接插入排序威力加强版本--希尔排序(适用逆序数，1亿逆序数据93s1亿随机数据223s)voidShellSort_local(int*a,intlen,intdk);voidHeapSort(int*H,intlength);//堆排序-step1:建堆2：n/2个父节点堆有序3、从堆尾元素依次和堆顶交换voidBuildingHeap(int*H,intlength);//堆排序---子函数(逆序数据50s,1亿条随机数据133秒)voidHeapAdjust(int*H,ints,intlength);//堆排序---子函数unsignedlongulrand(void);//产生大的随机数voidselectSort(int*a,intn);//选择排序intSelectMinKey(int*a,intn,inti);voidSelectSort_double(int*r,intn);typedefintElemType;voidMergeSort(ElemType*r,ElemType*rf,intlenght);//归并排序(1亿逆序：30s1亿随机：46s)voidMerge(ElemType*r,ElemType*rf,inti,intm,intn);//65148-65149/*总结提升算法效率方法1、减小循环次数，大循环在里面，小循环再外面-----循环次数多的话切换用时多，2、侦测已完成任务，提前结束3、递归算法占用的空间较大，容易溢出,优点是算法复杂度低*/voidQuickSort(int*a,intlow,inthigh);//(全完逆序100w数据40分钟---已验证)intLocalQuickSort(int*a,intlow,inthigh);voidSwap(int*p1,int*p2);voidPrintArray(int*a,intlen);voidInitArray(int*a,intlen);intfirst_posi=0;intprivotKey=0;intSortOkSign=0;//无//需交换的标志#definelenArr100000000intlastChangePos=lenArr-1;//最后一次交换的位置intgloData=0;intk=0,m=0,n=0,x=0;int*p=(int*)malloc(lenArr*sizeof(int));intb[lenArr];intmain(){//intlen=5;if(p==NULL){printf(mallocError);return0;}clock_tstart_2,end_2;//InitArray(p,lenArr);//start_1=clock();//开始时间start_1,end_1,//InsertSort(p,lenArr);//UpdbubbleSort2(p,lenArr);//QuickSort(p,0,lenArr-1);//PrintArray(p,lenArr);//quickSort_update(p,lenArr-1,10);//InsertSort(p,lenArr);//HeapSort(p,lenArr);//MergeSort(p,b,lenArr);//end_1=clock();//结束时间InitArray(p,lenArr);//PrintArray(p,lenArr);start_2=clock();//结束时间//shellSort(p,lenArr);//bubbleSort(p,lenArr);HeapSort(p,lenArr);end_2=clock();//PrintArray(p,lenArr);doubledb2=(double)(end_2-start_2)/CLOCKS_PER_SEC;printf(\n排序时间%lf,db2);return0;}//改进冒泡算法---检测已排序好的尾部段，不再排序voidUpdBubbleSort1(int*a,intlen){inttempInt=0;for(intj=len;j0;j--){intmin_posi=(j-1)lastChangePos?(j-1):lastChangePos;for(inti=0;imin_posi;i++){if(a[i]a[i+1]){tempInt=a[i];a[i]=a[i+1];a[i+1]=tempInt;SortOkSign=1;lastChangePos=i+1;}}if(0==SortOkSign){break;}}}//将r[i…m]和r[m+1…n]归并到辅助数组rf[i…n]voidMerge(ElemType*r,ElemType*rf,inti,intm,intn){intj,k;for(j=m+1,k=i;i=m&&j=n;++k){if(r[j]r[i])rf[k]=r[j++];elserf[k]=r[i++];}while(i=m)rf[k++]=r[i++];while(j=n)rf[k++]=r[j++];}voidMergeSort(ElemType*r,ElemType*rf,intlenght){for(intg=0;glenArr;g++)rf[g]=r[g];intlen=1;ElemType*q=r;//ElemType*tmp;while(lenlenght){ints=len;len=2*s;inti=0;while(i+len=lenght){Merge(q,rf,i,i+s-1,i+len-1);//对等长的两个子表合并i=i+len;}if(i+s-1=lenght-1){Merge(q,rf,i,i+s-1,lenght-1);//对不等长的两个子表合并}//tmp=q;q=rf;rf=tmp;//交换q,rf，以保证下一趟归并时，仍从q归并到rffor(intg=0;glenArr;g++)q[g]=rf[g];}rf=q;}voidHeapSort(int*H,intlength)//堆排序-{//初始堆BuildingHeap(H,length);//从最后一个元素开始对序列进行调整for(inti=length-1;i0;--i){//交换堆顶元素H[0]和堆中最后一个元素inttemp=H[i];H[i]=H[0];H[0]=temp;//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整HeapAdjust(H,0,i);//printf(\n第%d次排序结果:,length-i);//PrintArray(p,lenArr);}}voidBuildingHeap(int*H,intlength)//堆排序----子函数{//最后一个有孩子的节点的位置i=(length-1)/2for(inti=(length-1)/2;i=0;--i)HeapAdjust(H,i,length);}voidHeapAdjust(int*H,ints,intlength)//堆排序---子函数{inttmp=H[s];intchild=2*s+1;//左孩子结点的位置。(i+1为当前调整结点的右孩子结点的位置)while(childlength){if(child+1length&&H[child]H[child+1]){//如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)++child;}if(H[s]H[child]){//如果较大的子结点大于父结点H[s]=H[child];//那么把较大的子结点往上移动，替换它的父结点s=child;//重新设置s,即待调整的下一个结点的位置child=2*s+1;}else{//如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出break;}H[s]=tmp;//当前待调整的结点放到比其大的孩子结点位置上}}intSelectMinKey(int*a,intn,inti){intk=i;for(intj=i+1;jn;++j){if(a[k]a[j])k=j;}returnk;}voidSelectSort_double(int*r,intn){inti,j,min,max,tmp;for(i=0;i=n/2;i++){//做不超过n/2趟选择排序min=i;max=i;//分别记录最大和最小关键字记录位置for(j=i+1;jn-i;j++){if(r[j]r[max]){max=j;continue;}if(r[j]r[min]){min=j;}}//该交换操作还可分情况讨论以提高效率if((max==i)&&(min=n-i-1)){tmp=r[min];r[min]=r[max];r[max]=tmp;}else{tmp=r[i];r[i]=r[min];r[min]=tmp;tmp=r[n-i-1];r[n-i-1]=r[max];r[max]=tmp;}}}/***选择排序**/voidselectSort(int*a,intn){intkey,tmp;for(inti=0;in;++i){key=SelectMinKey(a,n,i);//选择最小的元素if(key!=i){tmp=a[i];a[i]=a[key];a[key]=tmp;//最小元素与第i位置元素互换}}}voidShellSort_local(int*a,intlen,intdk){for(k=0;kdk;k++){for(n=dk+k;nlen;n=n+dk){x=a[n];m=n-dk;while((m=0)&&(xa[m])){a[m+dk]=a[m];m=m-dk;}a[m+dk]=x;}}}voidshellSort(int*a,intn){intdk=n/2;while(dk=1){ShellSort_local(a,n,dk);dk=dk/2;}}voidquickSort_update(int*a,intlen,intk){qsort_improve(a,0,len,k);//先调用改进算法Qsort使之基本有序//再用插入排序对基本有序序列排序for(inti=1;i=len;i++){inttmp=a[i];intj=i-1;while(tmpa[j]){a[j+1]=a[j];j=j-1;}a[j+1]=tmp;}}voidqsort_improve(int*a,intlow,inthigh,intk){if(high-lowk){//长度大于k时递归,k为指定的数intpivot=LocalQuickSort(a,low,high);//调用的Partition算法保持不变qsort_improve(a,low,p