合并排序
package algorithm;/** * May 26, 2009 * version 1.1 * @author qinshuangping */public class MergeSort { /** * 合并排序(也称归并排序) * 归并操作的工作原理如下(网上找的这个原理和这个例子似乎对不大上，不过大体上差不多吧)： * 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 * 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置 * 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 * 4. 重复步骤3直到某一指针达到序列尾 * 5. 将另一序列剩下的所有元素直接复制到合并序列尾 */ /** * 主要是对数组进行细分，应用了递归 * @param ia 待排序的数组 * @param p 数组的开始位置（第一次调用时为0） * @param r 数组的结束位置(第一次调用时为数组长度-1) */ void mergeSort(int ia[], int p, int r){ if(p<r ){ int q = (p+r)/2; mergeSort(ia, p, q); mergeSort(ia, q+1, r); merge(ia, p, q, r);//排序主方法 } } /** * 对已排序数组的两段合并成一段最终的排序 * 如：数组a[] = {8,9,14,17,1,2,3,4,7};p=0;r=8;q=3; * 则调用该方法为merge(a,0,3,8) * 通过merge()方法后数组a变成{1,2,3,4,7,8,9,14,17} * 排序步骤： * 1.新建两个数组 * 2.对两个数组赋值， * a.ia1为ia[p]--ia[q],为前段数组，数组长度为[q-p+1] * b.ia2为ia[q+1]--ia[r],为后段数组,数组长度为[r-q] * 3.设置k=p,主要是为了对待排序的数组进行赋值 * 4.当k<r时进行循环，即带排序的数组还没有排好序 * 5.对ia1中的数组和ia2中的数组进行比较，即是进行排序，并把结果放进ia中，k++ * @param ia 需要进行排序的数组 * @param p 数组的开始位置 * @param q 数组的中间位置(p+r)/2 * @param r 数组的结束位置 */ public void merge(int ia[], int p, int q, int r){ int n1 = q - p + 1; // n1 = [p, q] int n2 = r - q; // n2 = (q, r] int ia1[]=new int[n1+1]; int ia2[]=new int[n2+1]; for(int i=0; i<n1; i++){ ia1[i] = ia[p+i]; } //哨兵？ ia1[n1] = 0x7FFFFFFF; // sentinel for(int i=0; i<n2; i++){ ia2[i] = ia[q+1+i]; } ia2[n2] = 0x7FFFFFFF; // sentinel int i, j, k; i = j = 0; k = p; while( k <= r ){ if( ia1[i]<=ia2[j] ){ ia[k] = ia1[i]; i++; }else{ ia[k] = ia2[j]; j++; } k++; } } public static void main(String[] args){ int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; MergeSort ms=new MergeSort(); ms.mergeSort(a, 0, a.length-1); for(int i=0; i<a.length; i++){ System.out.print(a[i]+","); }// int a[] = {8,9,14,17,1,2,3,4,7};// MergeSort ms=new MergeSort();// ms.merge(a, 0, 3, a.length-1);// for(int i=0; i<a.length; i++){// System.out.print(a[i]+",");// } }}
