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

《数据结构各种排序算法总结.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构各种排序算法总结计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。1.冒泡排序BubbleSort最简单的一个publicvoidbubbleSort(){intout,in;for(out=nElems-1;out>0;out--)//outerloop(backward)for(in=0;ina[in+1])//outoforder?swap(in,in+1);//swapthem}//end

2、bubbleSort()效率：O(N2)2.选择排序selectSortpublicvoidselectionSort(){intout,in,min;for(out=0;out

3、插入排序insertSort在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。publicvoidinsertionSort(){intin,out;for(out=1;out0&&a[in-1]>=temp)//untiloneissmaller,{a[in]=a[in-1];//shiftitemtoright--in;//goleftoneposi

4、tion}a[in]=temp;//insertmarkeditem}//endfor}//endinsertionSort()效率：比冒泡排序快一倍，比选择排序略快，但也是O(N2)如果数据基本有序，几乎需要O(N)的时间4.归并排序mergeSort利用递归，不断的分割数组，然后归并有序数组效率为O(N*logN),缺点是需要在存储器中有一个大小等于被排序的数据项数目的数组。publicvoidmergeSort()//calledbymain(){//providesworkspacelong[]workSpace=newlong[nElems];recMergeSort(wo

5、rkSpace,0,nElems-1);}//-----------------------------------------------------------privatevoidrecMergeSort(long[]workSpace,intlowerBound,intupperBound){if(lowerBound==upperBound)//ifrangeis1,return;//nousesortingelse{//findmidpointintmid=(lowerBound+upperBound)/2;//sortlowhalfrecMergeSort(workSp

6、ace,lowerBound,mid);//sorthighhalfrecMergeSort(workSpace,mid+1,upperBound);//mergethemmerge(workSpace,lowerBound,mid+1,upperBound);}//endelse}//endrecMergeSort()//-----------------------------------------------------------privatevoidmerge(long[]workSpace,intlowPtr,inthighPtr,intupperBound){intj

7、=0;//workspaceindexintlowerBound=lowPtr;intmid=highPtr-1;intn=upperBound-lowerBound+1;//#ofitemswhile(lowPtr<=mid&&highPtr<=upperBound)if(theArray[lowPtr]