归并排序

1、Java 代码

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {

    // 1、分解到最小需要解决的地步,无法再分解了
    if (start >= end){
        // 需要开始解决问题
        return;
    }

    // 2、解决

    // 计算数组 arr 的中间位置    
    int mid = (start + end ) / 2;

    // start1 为左区间的开始位置
    int start1 = start;

    // end1 为左区间的结束位置
    int end1 = mid;

    // start2 为右区间的开始位置
    int start2 = mid + 1;

    // end2 为右区间的结束位置
    int end2 = end;

    // 调用 merge_sort_recursive 函数,将 arr 数组中的 start1 到 end1 这一区间的数字排序后,并存放到 result 中
    merge_sort_recursive(arr, result, start1, end1);

    // 调用 merge_sort_recursive 函数,将 arr 数组中的 start2 到 end2 这一区间的数字排序后,并存放到 result 中
    merge_sort_recursive(arr, result, start2, end2);

    // 3、合并

    // 将左右区间中较小的数字存放到 result 中,从 k 开始
    int k = start;

    while (start1 <= end1 && start2 <= end2){
        // 如果 arr[start1] < arr[start2])
        if(arr[start1] < arr[start2]){
            // result[k] 存放的是 arr[start1]
            result[k] = arr[start1] ;
            start1++;
            k++;
        }else{
            // 否则,result[k] 存放的是 arr[start2]
            result[k] = arr[start2] ;
            start2++;
            k++;
        }

    }

    // 如果左区间中还有元素,那么把它都添加到 result 中
    while (start1 <= end1){
        result[k] = arr[start1];
        k++;
        start1++;
    }

    // 如果右区间中还有元素,那么把它都添加到 result 中
    while (start2 <= end2){
        result[k] = arr[start2];
        k++;
        start2++;
    }

    // 最后,把结果赋值到 arr 中
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

2、C++ 代码

// 归并排序(C++-递归版)
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

// merge_sort
template<typename T>
void merge_sort(T arr[], const int len) {
    T reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

3、Python 代码

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

发表评论

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