归并排序


题:完成merge方法
在工程问题中,当对大量数据进行排序的时候,数据往往是放在数组中的。
这时进行排序需要一些腾挪的技巧。一般是使用一个临时的数组空间保存中间结果,排好序以后,再拷贝回原来的数组。
下面的代码是采用递归的思想进行递归排序的。请完成merge方法。

// 对data数组中的 [a,b) 区间的数据进行归并排序,
// 排序结束后,[a,b)间数据处于升序有序状态
static void mergeSort(int[] data, int a,int b)
{
if (a >= b) return;
int mid=(a+b)/2;
mergeSort(a,mid);
mergeSort(mid+1,b);
merge(a,mid,b);
}
// data中的数据, [low,mid), [mid,high) 是两段待归并数据。归并后,[low,high) 整体有序
static void merge(int[] data, int low,int mid,int high)
{
int[] tmp = new int[high-low];
}

源码MSort.java


package MSort;

public class MSort {
    
    public static void mergeSort(int[] data, int a, int b) {
        if (a>=b) return;
        int mid = (a+b)/2;
        mergeSort(data, a, mid);
        mergeSort(data, mid+1, b);
        merge(data, a, mid+1, b);
    }

    private static void merge(int[] data, int low, int mid, int high) {
        int[] tmp = new int[high-low+1];
        int left = low;
        int right = mid;
        int k = 0;
        while (left<mid && right<high+1) {
            if (data[left] < data[right]) {
                tmp[k++] = data[left++];
            }
            else {
                tmp[k++] = data[right++];
            }
        }

        for (int i=left; i<mid; i++) {
            tmp[k++] = data[left++];
        }
        for (int i=right; i<high+1; i++) {
            tmp[k++] = data[right++];
        }
/*      System.out.println("-------");
        for (int i=0; i<tmp.length; i++) {
            System.out.println(tmp[i]);
        }
*/
        for (int i=0; i<tmp.length; i++) {
            data[low+i] = tmp[i];
        }
    }
    
    static void show(int[] data) {
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] a = {26, 5, 98, 108, 28, 99, 100, 56, 34, 1};
        mergeSort(a, 0, a.length-1);
        show(a);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注