文档详情

程序员必知的8大排序(四)-------归并排序,基数排序(java实现).doc

发布:2017-09-21约4.14千字共6页下载文档
文本预览下载声明
7、归并排序 (1)基本排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 (2)实例: (3)用java实现 [plain] view plaincopy import java.util.Arrays; public class mergingSort { int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; public mergingSort(){ sort(a,0,a.length-1); for(int i=0;ia.length;i++) System.out.println(a[i]); } public void sort(int[] data, int left, int right) { // TODO Auto-generated method stub if(leftright){ //找出中间索引 int center=(left+right)/2; //对左边数组进行递归 sort(data,left,center); //对右边数组进行递归 sort(data,center+1,right); //合并 merge(data,left,center,right); } } public void merge(int[] data, int left, int center, int right) { // TODO Auto-generated method stub int [] tmpArr=new int[data.length]; int mid=center+1; //third记录中间数组的索引 int third=left; int tmp=left; while(left=centermid=right){ //从两个数组中取出最小的放入中间数组 if(data[left]=data[mid]){ tmpArr[third++]=data[left++]; }else{ tmpArr[third++]=data[mid++]; } } //剩余部分依次放入中间数组 while(mid=right){ tmpArr[third++]=data[mid++]; } while(left=center){ tmpArr[third++]=data[left++]; } //将中间数组中的内容复制回原数组 while(tmp=right){ data[tmp]=tmpArr[tmp++]; } System.out.println(Arrays.toString(data)); } } [plain] view plaincopy /prepre class=plain name=code 8、基数排序 (1)基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 (2)实例: (3)用java实现 [plain] view plaincopy import java.util.ArrayList; import java.util.List; public class radixSort { int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51}; public radixSort(){
显示全部
相似文档