数据结构各种排序算法总结.doc

数据结构各种排序算法总结计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。1.冒泡排序BubbleSort最简单的一个publicvoidbubbleSort(){intout,in;for(out=nElems-1;out>0;out--)//outerloop(backward)for(in=0;in<out;in++)//innerloop(forward)if(a[in]>a[in+1])//outoforder?swap(in,in+1);//swapthem}//endbubbleSort()效率：O(N2)2.选择排序selectSortpublicvoidselectionSort(){intout,in,min;for(out=0;out<nElems-1;out++)//outerloop{min=out;//minimumfor(in=out+1;in<nElems;in++)//innerloopif(a[in]<a[min])//ifmingreater,min=in;//wehaveanewminswap(out,min);//swapthem}//endfor(out)}//endselectionSort()效率：O(N2)3.插入排序insertSort在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。publicvoidinsertionSort(){intin,out;for(out=1;out<nElems;out++)//outisdividingline{longtemp=a[out];//removemarkeditemin=out;//startshiftsatoutwhile(in>0&&a[in-1]>=temp)//untiloneissmaller,{a[in]=a[in-1];//shiftitemtoright--in;//goleftoneposition}a[in]=temp;//insertmarkeditem}//endfor}//endinsertionSort()效率：比冒泡排序快一倍，比选择排序略快，但也是O(N2)如果数据基本有序，几乎需要O(N)的时间4.归并排序mergeSort利用递归，不断的分割数组，然后归并有序数组效率为O(N*logN),缺点是需要在存储器中有一个大小等于被排序的数据项数目的数组。publicvoidmergeSort()//calledbymain(){//providesworkspacelong[]workSpace=newlong[nElems];recMergeSort(workSpace,0,nElems-1);}//-----------------------------------------------------------privatevoidrecMergeSort(long[]workSpace,intlowerBound,intupperBound){if(lowerBound==upperBound)//ifrangeis1,return;//nousesortingelse{//findmidpointintmid=(lowerBound+upperBound)/2;//sortlowhalfrecMergeSort(workSpace,lowerBound,mid);//sorthighhalfrecMergeSort(workSpace,mid+1,upperBound);//mergethemmerge(workSpace,lowerBound,mid+1,upperBound);}//endelse}//endrecMergeSort()//-----------------------------------------------------------privatevoidmerge(long[]workSpace,intlowPtr,inthighPtr,intupperBound){intj=0;//workspaceindexintlowerBound=lowPtr;intmid=highPtr-1;intn=upperBound-lowerBound+1;//#ofitemswhile(lowPtr<=mid&&highPtr<=upperBound)if(theArray[lowPtr]<theArray[highPtr])workSpace[j++]=theArray[lowPtr++];elseworkSpace[j++]=theA