归并排序（JAVA）
并归排序：将两个或两个以上的有序数组组合成一个新的有序数组，叫并归排序
排序过程
1、 设初始数组有n个数据，则可看成n个有序的子数组， 每个子数组长度为1；
2、 两两合并，得到n/2或n/2+1 个长度为2 或1 的有序子数组；
3、 再两两合并，…… 如此重复，直至得到一个长度为n 的有序数组为止。
下面是归并排序的一个简单的例子:
初始值 【49】 【38】 【65】 【97】 【76】 【13】 【27】
http://dl.iteye.com/upload/attachment/0072/9064/6e311971-9a7b-3c9b-8d35-bbe3c800e499.jpg
public class MergeSort { public static void sort(int[] arr) { //创建临时数组 int[] tempArr =new int; msort(arr, tempArr, 0, arr.length); } private static void msort(int[] arr, int[] tempArr, int first,int last) { if (first+1< last) { int midpt = (last + first) / 2; msort(arr, tempArr, first, midpt); msort(arr, tempArr, midpt, last); if (arr<=arr)//如果前半部分与后半部分正好形成了顺序 return; int indexA, indexB, indexC;//前半部分的索引,后半部分的索引,临时数组的索引 indexA = first; indexB = midpt; indexC = first; while (indexA < midpt && indexB < last) { if (arr<arr) { tempArr = arr; //copyto tempArr indexA++; } else { tempArr = arr; //copyto tempArr indexB++; } indexC++; } //copy the tail of the sublist that is not exhausted while (indexA < midpt) { tempArr = arr; } while (indexB < last) { tempArr = arr; } 将临时数组的所有元素复制到原数组 for (int i = first; i < last; i++) arr = tempArr; } } public static void main(String[] args){ inta[]={100,7,10,19,56,25,12,7,17,21,-1,30,48}; sort(a); for(int i:a) System.out.print(i+","); }}
页:
[1]