java各种数组排序(插入,交换,选择,归类,基数排序)_第1页
java各种数组排序(插入,交换,选择,归类,基数排序)_第2页
java各种数组排序(插入,交换,选择,归类,基数排序)_第3页
java各种数组排序(插入,交换,选择,归类,基数排序)_第4页
java各种数组排序(插入,交换,选择,归类,基数排序)_第5页
已阅读5页,还剩5页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、importjava.util.Random;*排序算法的分类如下:*1.插入排序(直接插入排序、折半插入排序、希尔排序);*2.交换排序(冒泡泡排序、快速排序);*3.选择排序(直接选择排序、堆排序);*4.归并排序;*5.基数排序。* 关于排序方法的选择:* (1)若n较小(如n30),可采用直接插入或直接选择排序。*当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。* (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;* (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并

2、排序。*/publicclassSortTest/*初始化测试数组的方法* return一个初始化好的数组* /publicintcreateArray()Randomrandom=newRandom();intarray=newint10;for(inti=0;i0;i-)for(intj=0;jsourcej+1)swap(source,j,j+1);elseif(sortType.equals(desc)/倒排序,从大排到小for(inti=source.length-1;i0;i-)for(intj=0;ji;j+)if(sourcejsourcej+1)swap(source,j,j

3、+1);elseSystem.out.println(您输入的排序类型错误!);printArray(source);/输出冒泡排序后的数组值/*直接选择排序法-选择排序的一种*方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。*性能:比较次数O(nA2),nA2/2*交换次数O(n),n*交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。*但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。* paramsource要排

4、序的数组* paramsortType排序类型* return* /publicvoidselectSort(intsource,StringsortType)if(sortType.equals(asc)/正排序,从小排到大for(inti=0;isource.length;i+)for(intj=i+1;jsourcej)swap(source,i,j);elseif(sortType.equals(desc)/倒排序,从大排到小for(inti=0;isource.length;i+)for(intj=i+1;jsource.length;j+)if(sourceisourcej)swa

5、p(source,i,j);elseSystem.out.println(您输入的排序类型错误!);printArray(source);/输出直接选择排序后的数组值/*插入排序*方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。*性能:比较次数O(nA2),nA2/4*复制次数O(n),nA2/4*比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。* paramsource要排序的数组* paramsortType排序类型* /publicvoidinsertSort(intsource,S

6、tringsortType)if(sortType.equals(asc)/正排序,从小排到大for(inti=1;i0)&(sourcejsourcej-1);j-)swap(source,j,j-1);elseif(sortType.equals(desc)/倒排序,从大排到小for(inti=1;i0)&(sourcejsourcej-1);j-)swap(source,j,j-1);elseSystem.out.println(您输入的排序类型错误!);printArray(source);/输出插入排序后的数组值/*反转数组的方法* paramsource源数组* /

7、publicvoidreverse(intsource)intlength=source.length;inttemp=0;临时变量for(inti=0;ilength/2;i+)temp=sourcei;sourcei=sourcelength-1-i;sourcelength-1-i=temp;printArray(source);/输出到转后数组的值/*快速排序*快速排序使用分治法(Divideandconquer)策略来把一个序列(list)分为两个子序列(sub-lists)。*步骤为:* 1.从数列中挑出一个元素,称为“基准(pivot),* 2.重新排序数列,所有元素比基准值小的

8、摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。* 3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。*递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。* paramsource待排序的数组* paramlow* paramhigh* seeSortTest#qsort(int,int,int)* seeSortTe

9、st#qsort_desc(int,int,int)* /publicvoidquickSort(intsource,StringsortType)if(sortType.equals(asc)/正排序,从小排到大qsort_asc(source,0,source.length-1);* elseif(sortType.equals(desc)/倒排序,从大排到小qsort_desc(source,0,source.length-1);* elseSystem.out.println(您输入的排序类型错误!);快速排序的具体实现,排正序paramsource/* paramlow* param

10、high* /privatevoidqsort_asc(intsource,intlow,inthigh)inti,j,x;if(lowhigh)/这个条件用来结束递归1=low;j=high;x=sourcei;while(ij)while(ix)j-;/从右向左找第一个小于x的数if(ij)sourcei=sourcej;i+;while(ij&sourceix)i+;从左向右找第一个大于x的数if(ij)sourcej=sourcei;j-;sourcei=x;qsort_asc(source,low,i-1);qsort_asc(source,i+1,high);/*快速排序的

11、具体实现,排倒序* paramsource* paramlow* paramhigh* /privatevoidqsort_desc(intsource,intlow,inthigh)inti,j,x;if(lowhigh)/这个条件用来结束递归1=low;j=high;x=sourcei;while(ij)while(ij&sourcejx)j-;/从右向左找第一个小于x的数if(ij)sourcei=sourcej;i+;while(ix)i+;从左向右找第一个大于x的数if(ij)sourcej=sourcei;j-;sourcei=x;qsort_desc(source,low

12、,i-1);qsort_desc(source,i+1,high);/*二分法查找*查找线性表必须是有序列表* paramsource* paramkey* return* /publicintbinarySearch(intsource,intkey)intlow=0,high=source.length-1,mid;while(low1;/相当于mid=(low+high)/2,但是效if(key=sourcemid)returnmid;elseif(key=1;i-)for(intj=0;j=i-1;j+)if(pareTo(sj+1)0)Stringtemp=null;temp=sj;sj=sj+1;sj+1=temp;for(Stringa:s)System.out.print(a+);大家一起学习吧!!System.out.println(=sortTest.insertSort(array,asc);System.out.println(=sortTest.insertSort(array,desc);插入排序后(正序)=);插入排序后(倒序)=);array=sor

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论